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

Ответ 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.суб >}