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

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

addOne x = 1 + x

Как мы видим 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 не имеет никакого отношения ко мне, docs 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 проще, чем документы?

Ответ 1

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

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

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

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)

то есть обессоливая 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)

Ответ 2

Любой лямбда-член может быть переписан эквивалентным термином, который использует только набор подходящих комбинаторов и никаких абстракций лямбда. Этот процесс называется устранение абстракции. Во время процесса вы хотите удалить лямбда-абстракции изнутри. Итак, на одном шаге у вас есть λ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 на аппликатор читателя, который равен pure M. Действительно, для (->) r pure эквивалентно const.
В последнем случае <*> :: f (a -> b) -> f a -> f b - это приложение функции, снятое с монады/аппликативного. И это именно то, что мы делаем: мы поднимаем обе части P и Q к аппликатору читателя, а затем используем <*> для их связывания.

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

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