Как я могу понять "(.) . (.)"?
Я верю я понимаю fmap . fmap для Функторов, но на функциях это болит голова в течение нескольких месяцев.
Я видел, что вы можете просто применить определение (.) в (.) . (.), но я забыл, как это сделать.
Когда я сам пробую, то всегда получается неправильно
(.) f g = \x -> f (g x)
(.) (.) (.) = \x -> (.) ((.) x)
\x f -> (.) ((.) x) f
\x f y -> (((.)(f y)) x)
\x f y g-> (((.)(f y) g) x)
\x f y g-> ((f (g y)) x)
\x f y g-> ((f (g y)) x):: t2 -> (t1 -> t2 -> t) -> t3 -> (t3 -> t1) -> t
Если "только применение определения" является единственным способом сделать это, как кто-то придумал (.) . (.)?
Там должно быть какое-то более глубокое понимание или интуиция, по которой я скучаю.
5 ответов
Вы также можете использовать свое понимание fmap . fmap,
Если у вас есть два Functors foo а также bar, затем
fmap . fmap :: (a -> b) -> foo (bar a) -> foo (bar b)
fmap . fmap берет функцию и производит индуцированную функцию для композиции двух Functors.
Теперь для любого типа t, (->) t это Functorи fmap для этого Functor является (.),
Так (.) . (.) является fmap . fmap для случая, когда два Functorс (->) s а также (->) t, и поэтому
(.) . (.) :: (a -> b) -> ((->) s) ((->) t a) -> ((->) s) ((->) t b)
= (a -> b) -> (s -> (t -> a)) -> (s -> (t -> b))
= (a -> b) -> (s -> t -> a) -> (s -> t -> b)
это "составляет" функцию f :: a -> b с функцией двух аргументов, g :: s -> t -> a,
((.) . (.)) f g = \x y -> f (g x y)
Эта точка зрения также проясняет, что и как шаблон распространяется на функции, принимающие больше аргументов,
(.) . (.) . (.) :: (a -> b) -> (s -> t -> u -> a) -> (s -> t -> u -> b)
и т.п.
Подходя с (.) . (.) на самом деле довольно просто, интуиция, стоящая за тем, что он делает, довольно сложно понять.
(.) очень далеко уходит, когда вы переписываете выражения в вычисления типа "pipe" (подумайте о | в ракушке). Тем не менее, это становится неудобным для использования, когда вы пытаетесь составить функцию, которая принимает несколько аргументов, с функцией, которая принимает только один. В качестве примера давайте определим concatMap:
concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f xs = concat (map f xs)
Избавиться от xs это просто стандартная операция:
concatMap f = concat . map f
Тем не менее, нет "хорошего" способа избавиться от f, Это связано с тем, что map принимает два аргумента, и мы хотели бы применить concat на его окончательный результат.
Вы можете, конечно, применить некоторые бессмысленные трюки и сойти с рук просто (.):
concatMap f = (.) concat (map f)
concatMap f = (.) concat . map $ f
concatMap = (.) concat . map
concatMap = (concat .) . map
Но, увы, читаемость этого кода в основном исчезла. Вместо этого мы вводим новый комбинатор, который делает именно то, что нам нужно: применить вторую функцию к конечному результату первой.
-- .: is fairly standard name for this combinator
(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
(f .: g) x y = f (g x y)
concatMap = concat .: map
Хорошо, вот и все для мотивации. Давайте перейдем к бессмысленному делу.
(.:) = \f g x y -> f (g x y)
= \f g x y -> f ((g x) y)
= \f g x y -> f . g x $ y
= \f g x -> f . g x
Теперь здесь начинается интересная часть. Это еще один из бессмысленных приемов, которые обычно помогают, когда вы застряли: мы переписываем . в форме префикса и попробуйте продолжить оттуда.
= \f g x -> (.) f (g x)
= \f g x -> (.) f . g $ x
= \f g -> (.) f . g
= \f g -> (.) ((.) f) g
= \f -> (.) ((.) f)
= \f -> (.) . (.) $ f
= (.) . (.)
Что касается интуиции, есть эта очень хорошая статья, которую вы должны прочитать. Я перефразирую часть о (.):
Давайте еще раз подумаем о том, что должен делать наш комбинатор: он должен применяться f к результату результата g (Я использовал конечный результат в этой части ранее специально, это действительно то, что вы получаете, когда вы полностью применяете - по модулю объединение переменных типа с другим типом функции - g функция, результат здесь просто приложение g x для некоторых x).
Что это значит для нас, чтобы подать заявку f к результату g? Ну, как только мы подаем заявку g к некоторому значению, мы возьмем результат и применим f к этому. Звучит знакомо: вот что (.) делает.
result :: (b -> c) -> ((a -> b) -> (a -> c))
result = (.)
Теперь выясняется, что композиция (наше слово) этих комбинаторов является просто функциональной композицией, то есть:
(.:) = result . result -- the result of result
Ваше решение расходится, когда вы вводите y, Так должно быть
\x f y -> ((.) ((.) x) f) y :: (c -> d) -> (a -> b -> c) -> a -> b -> d
\x f y z -> ((.) ((.) x) f) y z :: (c -> d) -> (a -> b -> c) -> a -> b -> d
\x f y z -> ((.) x (f y)) z :: (c -> d) -> (a -> b -> c) -> a -> b -> d
-- Or alternately:
\x f y z -> (x . f y) z :: (c -> d) -> (a -> b -> c) -> a -> b -> d
\x f y z -> (x (f y z)) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
Что соответствует оригинальной подписи типа: (.) . (.) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
(Расширить проще всего в ghci, где вы можете проверить каждый шаг с помощью :t expression)
Редактировать:
Более глубокая интуиция заключается в следующем:
(.) просто определяется как
\f g -> \x -> f (g x)
Который мы можем упростить до
\f g x -> f (g x)
Поэтому, когда вы предоставляете ему два аргумента, он каррируется и все еще нуждается в другом аргументе для разрешения. Каждый раз, когда вы используете (.) с двумя аргументами вы создаете "потребность" в еще одном аргументе.
(.) . (.) конечно просто (.) (.) (.)Итак, давайте расширим это:
(\f0 g0 x0 -> f0 (g0 x0)) (\f1 g1 x1 -> f1 (g1 x1)) (\f2 g2 x2 -> f2 (g2 x2))
Мы можем бета-уменьшить на f0 а также g0 (но у нас нет x0!):
\x0 -> (\f1 g1 x1 -> f1 (g1 x1)) ((\f2 g2 x2 -> f2 (g2 x2)) x0)
Подставим 2-е выражение для f1...
\x0 -> \g1 x1 -> ((\f2 g2 x2 -> f2 (g2 x2)) x0) (g1 x1)
Теперь это "переворачивается"! (бета-сокращение на f2):
Это интересный шаг - x0 заменяется f2 -- Это означает, что x, который мог бы быть данными, вместо этого является функцией.
Вот что (.) . (.) обеспечивает - "необходимость" для дополнительного аргумента.
\x0 -> \g1 x1 -> (\g2 x2 -> x0 (g2 x2)) (g1 x1)
Это начинает выглядеть нормально... Давайте сделаем бета-сокращение в последний раз (на g2):
\x0 -> \g1 x1 -> (\x2 -> x0 ((g1 x1) x2))
Таким образом, мы остались с
\x0 g1 x1 x2 -> x0 ((g1 x1) x2)
где аргументы приятно еще в порядке.
Итак, это то, что я получаю, когда делаю чуть более постепенное расширение
(.) f g = \x -> f (g x)
(.) . g = \x -> (.) (g x)
= \x -> \y -> (.) (g x) y
= \x -> \y -> \z -> (g x) (y z)
= \x y z -> (g x) (y z)
(.) . (.) = \x y z -> ((.) x) (y z)
= \x y z -> \k -> x (y z k)
= \x y z k -> x (y z k)
Который, по словам GHCI имеет правильный тип
Prelude> :t (.) . (.)
(.) . (.) :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c
Prelude> :t \x y z k -> x (y z k)
\x y z k -> x (y z k)
:: (t1 -> t) -> (t2 -> t3 -> t1) -> t2 -> t3 -> t
Prelude>
Хотя я не знаю происхождения этого комбинатора, вполне вероятно, что он был разработан для использования в комбинаторной логике, где вы работаете строго с комбинаторами, поэтому вы не можете определять вещи, используя более удобные лямбда-выражения. Может быть какая-то интуиция, которая идет с выяснением этих вещей, но я не нашел это. Скорее всего, вы бы развили некоторый уровень интуиции, если бы вам пришлось сделать это достаточно.
Проще всего писать уравнения в стиле комбинаторов вместо лямбда-выражений: a b c = (\x -> ... body ...) эквивалентно a b c x = ... body ...и наоборот, при условии, что x не появляется среди {a,b,c}, Так,
-- _B = (.)
_B f g x = f (g x)
_B _B _B f g x y = _B (_B f) g x y
= (_B f) (g x) y
= _B f (g x) y
= f ((g x) y)
= f (g x y)
Вы обнаружите это, если, учитывая f (g x y), вы хотите преобразовать его в комбинаторную форму (избавиться от всех скобок и повторений переменных). Затем вы применяете шаблоны, соответствующие определениям комбинаторов, надеясь проследить этот вывод в обратном направлении. Это гораздо менее механический / автоматический, хотя.