Понимание `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 не имеет для меня никакого смысла, документы 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 проще, чем документация?


functional-programming haskell pointfree
person Caridorc    schedule 31.10.2015    source источник
comment
let average = liftM2 ((/) . realToFrac) sum genericLength работает.   -  person Ørjan Johansen    schedule 31.10.2015
comment
@ ØrjanJohansen Интересно, не могли бы вы в ответе объяснить почему?   -  person Caridorc    schedule 31.10.2015
comment
Взгляните на ap реализацию экземпляра Monad для функций   -  person Bergi    schedule 31.10.2015
comment
В качестве забавного упражнения ap можно определить как (. ((. (return .)) . (>>=))) . (>>=). :-)   -  person awllower    schedule 10.03.2018

Ответы (2)


arrow_upward
8
arrow_downward

Когда монада 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-нотацию

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)
person chi    schedule 31.10.2015
comment
Значит, определение ap' f g = \x -> f x (g x) даст ему подмножество мощности, которой обладает нормальный ap? - person Caridorc; 31.10.2015
comment
@Caridorc: Да, нормальный ap работает на всех монадах, ваш ap' только на функциях - person Bergi; 31.10.2015
comment
ap' в чем-то похож на .? В то время как . составляет две функции, каждая из которых принимает один аргумент, ap' составляет две функции, одна из которых принимает два аргумента, а другая - один. - person Caridorc; 31.10.2015
comment
@Caridorc Только смутно. В лямбда-исчислении и комбинаторной логике он известен как комбинатор S. en.wikipedia.org/wiki/Combinatory_logic #Examples_of_combinators - person chi; 31.10.2015
comment
@chi Действительно! Applicative можно рассматривать как обобщение исчисления SKI: (<*>) - это S, pure - это K, и I = S K K. - person Rein Henrichs; 01.11.2015

arrow_upward
10
arrow_downward

Любой лямбда-термин можно переписать в эквивалентный термин, который использует только набор подходящих комбинаторов и не использует лямбда-выражения. абстракции. Этот процесс называется устранением абстрацитона. В процессе вы хотите удалить лямбда-абстракции изнутри. Итак, на одном этапе у вас есть λ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. И снова (.) для читателя просто _53 _ / _ 54_. (Я не знаю такой встроенной функции для выражения flip, но для читателя это будет рассматриваться как специализация f (a -> b) -> a -> f b.)

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

person Petr    schedule 31.10.2015
comment
Он не встроен, но lens имеет обобщенный flip как _ 3_. Я чувствую, что это какая-то дыра в Data.Functor. - person Ørjan Johansen; 01.11.2015