Короче говоря : из-за вывода типа Хаскелл знает, что m и f на самом деле являются частично экземплярированной стрелкой.
Вывод типа
Хорошо, давайте сделаем математику.Функция join . (flip fmap) - это, по сути, ваше заданное лямбда-выражение \x -> join . x с аргументом (flip fmap), поэтому:
h = (\x -> join . x) (flip fmap)
Теперь лямбда-выражение имеет тип:
(\x -> join . x) :: Monad m => (a -> m (m b)) -> (a -> m b)
Теперьаргумент flip fmap имеет тип:
flip fmap :: Functor f => f c -> ((c -> d) -> f d)
(здесь мы используем c и d вместо a и b, чтобы избежать путаницы между двумя возможно различными типами).
Это означает, что тип flip fmap совпадает с типом аргумента лямбда-выражения, поэтому мы знаем, что:
Monad m => a -> m (m b)
~ Functor f => f c -> ((c -> d) -> f d)
---------------------------------------
a ~ f c, m (m b) ~ ((c -> d) -> f d)
Итак, теперь мы знаем, что a имеет тот же тип, что и f c (в этом смысл тильды ~).
Но нам нужно сделать несколько дополнительных вычислений:
Monad m => m (m b)
~ Functor f => ((c -> d) -> f d)
--------------------------------
m ~ (->) (c -> d), m b ~ f d
Следовательно, мы знаем, что m - это то же самое, что и (->) (c -> d) (в основном это функция, в которой мы знаем этот тип ввода, здесь (c -> d), а тип вывода - это параметр типа m.
Значит, это m b ~ (c -> d) -> b ~ f d, значит, f ~ (->) (c -> d) и b ~ d. Дополнительным следствием является то, что с a ~ f c мы знаем, чтоa ~ (c -> d) -> c
Итак, перечислим, что мы получили:
f ~ m
m ~ (->) (c -> d)
b ~ d
a ~ (c -> d) -> c
Теперь мы можем «специализировать» типы как нашего лямбда-выражения, так и нашей функции flip fmap:
(\x -> join . x)
:: (((c -> d) -> c) -> (c -> d) -> (c -> d) -> d) -> ((c -> d) -> c) -> (c -> d) -> d
flip fmap
:: ((c -> d) -> c) -> (c -> d) -> (c -> d) -> d
и тип flip fmap теперь идеально совпадают с типом аргумента лямбда-выражения.Таким образом, тип (\x -> join . x) (flip fmap) является типом результата типа лямбда-выражения, а именно:
(\x -> join . x) (flip fmap)
:: ((c -> d) -> c) -> (c -> d) -> d
Но сейчас мы, конечно, еще не получили реализацию этой функции.Однако мы уже на шаг впереди.
Вывод реализации
Поскольку теперь мы знаем, что m ~ (->) (c -> d), мы знаем, что нам нужно искать экземпляр стрелки монады :
instance Monad ((->) r) where
f >>= k = \ r -> k (f r) r
Таким образом, для данной функции f :: r -> a в качестве левого операнда и функции k :: a -> (r -> b) ~ a -> r -> b в качестве операнда мы создаем новую функцию, которая отображает переменную x вk применяется к f применяется к x и x.Таким образом, это способ выполнить некоторую предварительную обработку входной переменной x, а затем выполнить обработку как с учетом предварительной обработки, так и с исходным представлением (ну, это интерпретация * , которую может прочитать читатель-человек).использовать).
Сейчас join :: Monad m => m (m a) -> m a is реализовано как :
join :: Monad m => m (m a) -> m a
join x = x >>= id
Таким образом, для монады (->) r это означает, что мы реализуем это следующим образом:
-- specialized for `m ~ (->) a
join f = \r -> id (f r) r
, поскольку id :: a -> a (функция тождества) возвращает свой аргумент,мы можем еще больше упростить его до:
-- specialized for `m ~ (->) a
join f = \r -> (f r) r
или более чистого:
-- specialized for `m ~ (->) a
join f x = f x x
Так что в основном ему присваивается функция f, а затем он дважды применяет аргумент к этой функции.
Кроме того, мы знаем, что экземпляр Functor для типа стрелки определен как :
instance Functor ((->) r) where
fmap = (.)
Так что он в основном используется как«постпроцессор» для результата функции: мы создаем новую функцию, которая будет выполнять постобработку с данной функцией.
Итак, теперь, когда мы достаточно специализировали функцию для заданного Functor / Monad, мы можем получить реализацию в виде:
-- alternative implementation
h = (.) (\f x -> f x x) (flip (.))
или с помощью дополнительных лямбда-выражений:
h = \a -> (\f x -> f x x) ((flip (.)) a)
, который мы теперь можем специализировать следующим образом:
h = \a -> (\f x -> f x x) ((\y z -> z . y) a)
-- apply a in the lambda expression
h = \a -> (\f x -> f x x) (\z -> z . a)
-- apply (\z -> z . a) in the first lambda expression
h = \a -> (\x -> (\z -> z . a) x x)
-- cleaning syntax
h a = (\x -> (\z -> z . a) x x)
-- cleaning syntax
h a x = (\z -> z . a) x x
-- apply lambda expression
h a x = (x . a) x
-- remove the (.) part
h a x = x (a x)
Таким образом, h в основном принимает два аргумента: a и x, затем выполняет функцию с помощью aв качестве функции и x в качестве параметра, и выход снова передается в функцию x.
Пример использования
В качестве примера использования вы используете:
h (\f -> f u) (\x -> x + v)
или лучше:
h (\f -> f u) (+v)
, чтобы мы могли проанализировать это следующим образом:
h (\f -> f u) (+v)
-> (+v) ((\f -> f u) (+v))
-> (+v) ((+v) u)
-> (+v) (u+v)
-> ((u+v)+v)
Итак, мы добавляем u+v к v.