Получение привязки монады из аппликативной (‹*›) путаницы

Работая с книгой Haskell, мой мозг ломается на следующем примере. Я действительно не знаю, что делает функция flip в строке 21.

1 class Functor f where
2   fmap :: (a -> b) -> f a -> f b
3
4 class Functor f => Applicative f where
5   pure :: a -> f a
6   (<*>) :: f (a -> b) -> f a -> f b
7
8 class Applicative f => Monad f where
9   return :: a -> f a
10   (>>=) :: f a -> (a -> f b) -> f b
11
12 instance Functor ((->) r) where
13   fmap = (.)
14
15 instance Applicative ((->) r) where
16   pure = const
17   f <*> a = \r -> f r (a r)
18
19 instance Monad ((->) r ) where
20   return = pure
21   ra >>= arb = flip arb <*> ra


-- flip :: (a -> b -> c) -> b -> a -> c

-- ra >>= arb = flip arb <*> ra

Насколько я понимаю, flip принимает функцию, которая принимает два аргумента, затем два отдельных аргумента и возвращает значение. В примере с привязкой мы передаем arb как (a -> b -> c), затем <*> как b в подписи флипа и, наконец, ra как a? Я не вижу этого.

Я попытался сделать типы более конкретными для моего реального примера, чтобы вы могли переписать <*> как

(<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)

и я могу сделать то же самое для привязки

(>>=) :: (r -> a) -> (a -> r -> b) -> (r -> b)

так что даже такой болван, как я, может видеть, что если бы мы могли поменять местами <*>, мы могли бы выстроиться в линию, как

(<???>) :: (r -> a) -> (r -> a -> b) -> (r -> b)
(>>=) ::   (r -> a) -> (a -> r -> b) -> (r -> b)

но, глядя на вторые аргументы, первый хочет r в качестве первого аргумента, а bind хочет a

Итак, каким-то образом flip пример из книги делает это для нас, но я действительно не понимаю, как это сделать. Любая помощь будет принята с благодарностью.

Благодарю вас!


person Shane Unger    schedule 22.01.2019    source источник
comment
flip f = \arg1 arg2 -> f arg2 arg1 — это все, что нужно, чтобы превратить a -> r -> b в r -> a -> b. В Haskell, где все функции являются одним аргументом для одного значения (а значение иногда является другой функцией), это также эквивалентно flip f arg1 arg2 = f arg2 arg1.   -  person Ry-♦    schedule 22.01.2019


Ответы (1)


Я думаю, что точка путаницы верхнего уровня: flip модифицирует arb, а не модифицирует <*>, как вы, кажется, полагаете. Мы «модифицировали» <*>, чтобы иметь «правильный» порядок аргументов, просто задав <*> его аргументы в обратном порядке, в котором мы их получили!

Теперь подробности. У нас есть, как вы заметили:

(>>=) :: (r -> a) -> (a -> r -> b) -> (r -> b)

Итак, поскольку у нас слева написано

ra >>= arb = ...

тогда то, что мы имеем в области видимости:

ra :: r -> a
arb :: a -> r -> b

(Обратите внимание, как имена были выбраны, чтобы отразить типы!) Переписывая тип, который вы дали для flip, мы имеем

flip :: (a -> b -> c) -> b -> a -> c -- original
flip :: (a -> r -> b) -> r -> a -> b -- rename variables

следовательно:

flip arb :: r -> a -> b

Теперь вспомните тип (<*>), который вы написали:

(<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)

Итак, в качестве первого аргумента (<*>) нам нужно что-то типа r -> a -> b. Привет! flip arb имеет такой тип! В качестве второго аргумента нам нужно что-то типа r -> a. И нам снова повезло, потому что ra имеет такой тип, так что...

flip arb <*> ra :: r -> b

(Как обычно с инфиксными операторами, это применение оператора (<*>) к аргументам flip arb и ra.) Какой тип мы надеялись получить? Ну, а теперь вернемся к типу (>>=):

(>>=) :: (r -> a) -> (a -> r -> b) -> (r -> b)

После приема двух аргументов это должно вернуть что-то типа r -> b. Круто, вот что мы построили.

ra >>= arb = flip arb <*> ra
person Daniel Wagner    schedule 22.01.2019
comment
тот факт, что flip влияет только на arb, а не на остальную часть выражения, это из-за приоритета приложения функции по сравнению с операторами? arb применяется к flip, а не <*> или ra, это потому, что применение аргумента к flip каким-то образом имеет приоритет? - person Shane Unger; 22.01.2019
comment
Другими словами, почему бы нам не написать (flip arb) <*> ra? - person Shane Unger; 22.01.2019
comment
Возможно, стоит отметить, что монады типа Reader — единственные, которые могут быть реализованы исключительно в терминах аппликативных операторов. - person Carl; 22.01.2019
comment
@ShaneUnger (flip arb) <*> ra тоже в порядке. И да, приложение префиксной функции связывает сильнее, чем приложение инфиксной функции, поэтому даже без круглых скобок это означает одно и то же. - person Daniel Wagner; 22.01.2019