Путаница в понимании подстановки / сигнатуры типа `ap` и различных реализаций (функциональное программирование)

Question

Я изучаю функциональное программирование, извините, если мой вопрос звучит странно - я пытаюсь сосредоточиться на заданных типовых сигнатурах функций и способах их реализации.

Глядя на подпись ap (Замена)

https://gist.github.com/Avaq/1f0636ec5c8d6aed2e45

(a → b → c) → (a → b) → a → c

Дается здесь как

const S = f => g => x => f(x)(g(x));

Что я думаю, я понимаю. f это функция, которая принимает два параметра, a а также b и возвращается c, g это функция, которая принимает a и возвращается b, Так g(a) возвращается b и поэтому f(a)(b) можно записать как f(a)(g(a)), который возвращает c,

g(a) является заменой b?

Хорошо, теперь я смотрю на другую реализацию, которая все еще имеет смысл:

https://github.com/sanctuary-js/sanctuary-type-classes/tree/v7.1.1#ap--applyf--fa-bfa---fb

ap(Identity(Math.sqrt), Identity(64))

Тип подписи

1. (f (a -> b), f a) -> f b

Похоже на

2. (a → b → c) → (a → b) → a → c

Переписав второе, используя a = f, b = a и c = b, я получаю

3. (f -> a -> b) -> (f -> a) -> f -> b

Предполагая, что ap принимает два параметра, где в первом f может быть некоторый функтор, который содержит функцию a -> b а во втором f какой-то функтор, который содержит a возвращая функтор, который заменяет функцию первого функтора конечной точкой b данный тогда функтор, содержащий a,

Ладно, отступая, эти две вещи выглядят совершенно по-разному, и я не могу понять, как они почему-то говорят одно и то же.

1. const S = f => g => x => f(x)(g(x))

2. ap(Identity(Math.sqrt), Identity(64))

Из моего понимания, ap(F(g),F(a)) можно выразить как F(a).map(g) что, опять же, мне все еще трудно приравнять к const S = f => g => x => f(x)(g(x)), Возможно, я что-то неправильно понимаю.

... может быть, мое недоразумение связано с выражением ap и как это соотносится с f => g => x => f(x)(g(x)) потому что я вижу, как они выражают одну и ту же подпись, но я не вижу их как одно и то же.

Любой, кто может оказать некоторую познавательную помощь здесь, я был бы очень признателен

Answer 1

ap имя для преобразования, которое ведет себя одинаково на большом количестве типов контейнеров, известных как Applicative Functors. Одним из таких типов контейнеров является функция: она может рассматриваться как контейнер с возвращаемым значением.

S комбинатор, который вы нашли в моей сущности, происходит из нетипизированного лямбда-исчисления и является преобразованием функции. Это также является действительной реализацией Applicative Functor для Function, и это является предпочтительной реализацией как для Ramda, так и Sanctuary. Вот почему вы можете использовать ap как S,

Чтобы понять, как ap является S, давайте посмотрим на подпись для ap:

Apply f => (f (a -> b), f a) -> f b

И давайте избавимся от запятой, карри функции. Это должно немного облегчить выполнение следующих шагов:

Apply f => f (a -> b) -> f a -> f b

Apply f часть показывает, что везде, где мы видим f a, мы можем использовать контейнер Applicative Functor, который содержит a, Давайте специализируем эту подпись для контейнера Function, заменив f с (Function x), x является входом для функции, а то, что следует, является выходом.

(Function x) (a -> b) -> (Function x) a -> (Function x) b

Это читается как: учитывая функцию из x в функцию от a в b и функция от x в a , возвращает функцию из x в b,

Мы можем снять скобки вокруг Function x из-за того, как работает ассоциативность конструктора:

Function x (a -> b) -> Function x a -> Function x b

И еще один способ написать Function a b использует обозначение стрелки: (a -> b) Итак, на следующем шаге мы делаем именно это:

(x -> (a -> b)) -> (x -> a) -> (x -> b)

И, наконец, мы можем снова избавиться от дополнительных скобок и обнаружить, что это наш S комбинатор:

(x -> a -> b) -> (x -> a) -> x -> b
(a -> b -> c) -> (a -> b) -> a -> c

Answer 2

Прежде всего, я думаю, что нет простого объяснения того, почему аппликативный функтор для типа функции в нетипизированном лямбда-исчислении называется заменой. AFAIK, Schönfinkel первоначально назвал эту комбинаторную функцию слияния или объединения.

Для специализации общего аппликативного типа функтора (f (a -> b), f a) -> f b (нетуная форма), нам нужно знать, что такое переменная параметризованного типа f точно представляет в контексте типа функции.

Как и каждый функтор, аппликативные функторы параметризованы по одному типу. Однако конструктору функционального типа требуется два типа - один для аргумента и другой для возвращаемого значения. Чтобы функции были экземплярами (аппликативных) функторов, мы должны поэтому игнорировать тип возвращаемого значения. Как следствие, f представляет собой (a -> )т.е. сам тип функции и тип ее аргумента. Правильное обозначение для частично примененного конструктора типа функции на самом деле является префиксом (->) aтак что давайте придерживаться этого.

Далее я перепишу общий аппликативный тип в форме карри и подставлю f с (->) r, Я использую другое письмо, чтобы отделить параметр типа аппликативного от других переменных типа:

(f (a -> b), f a) -> f b
f (a -> b) -> f a -> f b // curried form

// substitution
(->) r (a -> b) -> (->) r a -> (->) r b // prefix notation
(r -> a -> b) -> (r -> a) -> (r -> b) // infix notation

// omit unnecessary parenthesis
(r -> a -> b) -> (r -> a) -> r -> b

Это именно тот тип S комбинатор.