Понимание `ap` в функции точечным бесплатно в Haskell

Question

я в состоянии понять основы точечных свободных функций в Haskell:

addOne x = 1 + x 

Как мы видим, х по обе стороны уравнения, мы упрощаем это:

addOne = (+ 1) 

---

Невероятно получается, что функции, где тот же самый аргумент используется дважды в разных частях можно записать точку бесплатно!

Позвольте мне взять в качестве основного примера функцию average записать в виде:

average xs = realToFrac (sum xs)/genericLength xs 

Это может показаться невозможным, чтобы упростить xs, но http://pointfree.io/ выходит с:

average = ap ((/) . realToFrac . sum) genericLength 

Это работает.

Насколько я понимаю, это указывает, что average такое же, как вызов ap на две функции, состав (/) . realToFrac . sum и genericLength

К сожалению, функция ap не имеет никакого смысла вообще для меня, Документах http://hackage.haskell.org/package/base-4.8.1.0/docs/Control-Monad.html#v:ap состояние:

ap :: Monad m => m (a -> b) -> m a -> m b 

In many situations, the liftM operations can be replaced by uses of ap, 
which promotes function application. 

     return f `ap` x1 `ap` ... `ap` xn 

is equivalent to 

     liftMn f x1 x2 ... xn 

Но написание:

let average = liftM2 ((/) . realToFrac . sum) genericLength 

не работает, (дает сообщение об ошибке очень длинного типа, спрашивает, и я его включу), поэтому я не понимаю, что говорят документы.

---

Как работает выражение ap ((/) . realToFrac . sum) genericLength? Не могли бы вы объяснить ap проще, чем документы?

Answer 1

Когда монада m является (->) a, как в вашем случае, вы можете определить ap следующим образом:

ap f g = \x -> f x (g x) 

Мы можем видеть, что это действительно «работает» в вашем pointfree примере.

average = ap ((/) . realToFrac . sum) genericLength 
average = \x -> ((/) . realToFrac . sum) x (genericLength x) 
average = \x -> (/) (realToFrac (sum x)) (genericLength x) 
average = \x -> realToFrac (sum x)/genericLength x 

Мы также можем получить ap из общего закона

ap f g = do ff <- f ; gg <- g ; return (ff gg) 

, который, desugaring do -notation

ap f g = f >>= \ff -> g >>= \gg -> return (ff gg) 

Если мы подставим определения методов монадных

m >>= f = \x -> f (m x) x 
return x = \_ -> x 

мы получаем предыдущее определение ap назад (для нашей конкретной монады (->) a).Действительно:

app f g 
= f >>= \ff -> g >>= \gg -> return (ff gg) 
= f >>= \ff -> g >>= \gg -> \_ -> ff gg 
= f >>= \ff -> g >>= \gg _ -> ff gg 
= f >>= \ff -> \x -> (\gg _ -> ff gg) (g x) x 
= f >>= \ff -> \x -> (\_ -> ff (g x)) x 
= f >>= \ff -> \x -> ff (g x) 
= f >>= \ff x -> ff (g x) 
= \y -> (\ff x -> ff (g x)) (f y) y 
= \y -> (\x -> f y (g x)) y 
= \y -> f y (g y) 

Answer 2

Любой член лямбда может быть переписано в эквивалентный термин, который использует только набор подходящих combinators и нет лямбда-абстракций. Этот процесс называется abstraciton elimination. Во время процесса вы хотите удалить лямбда-абстракции изнутри. Итак, на одном шаге у вас есть λx.M, где M уже свободен от лямбда-абстракций, и вы хотите избавиться от x.

• Если M является x, вы замените λx.x с id (id обычно обозначается I в комбинаторной логике).
• Если M не содержит x, заменить термин с const M (const обычно обозначается K в комбинаторной логике).

• Если M является PQ, то есть термин λx.PQ, вы хотите «толчок» x внутри обеих частей приложения функции, так что вы можете рекурсивно обрабатывать обе части. Это достигается с помощью комбинатора S, определяемого как λfgx.(fx)(gx), то есть он принимает две функции и передает x обеим из них и вместе применяет результаты. Вы можете легко убедиться, что λx.PQ эквивалентен S(λx.P)(λx.Q), и мы можем рекурсивно обрабатывать оба субтерма.

  Как описано в других ответах, комбинатор S доступен в Haskell как ap (или <*>), специализирующийся на монаде читателя.

Появление читателя монады не случайно: При решении задачи замены λx.M с эквивалентной функции, в основном поднимая M :: a к читателю монады r -> a (на самом деле читатель Аппликативный часть достаточно), где r является типом x. Если мы пересматриваем процесс выше:

• Единственный случай, который на самом деле связанный с читателем монады, когда M является x. Затем мы «поднимаем» x до id, чтобы избавиться от переменной. Другие случаи, приведенные ниже, только механические применения грузоподъемного выражения для аппликативного функтора:
• Другого случая λx.M где M не содержит x, это просто грузоподъемные M к читателю Applicative, который pure M. Действительно, для (->) r, pure эквивалентно const.
• В последнем случае <*> :: f (a -> b) -> f a -> f b - это приложение приложения, снятое до монады/аппликативного. И это именно то, что мы делаем: мы поднимаем обе части P и Q к аппликатору читателя, а затем используйте <*>, чтобы связать их вместе.

Этот процесс может быть дополнительно улучшен путем добавления большего количества комбинаторов, что позволяет сократить срок их использования. Чаще всего combinators B and C are used, которые в Haskell соответствуют функциям (.) и flip.И снова (.) - это всего лишь fmap/<$> для читателя. (Я не знаю такой встроенной функции для выражения flip, но было бы рассматривать как специализацию f (a -> b) -> a -> f b для чтения Applicative.)

_{Некоторое время назад я написал короткую статью об этом: The Monad Reader Issue 17, Чтение Монады и абстракция.}