Как я могу понять "(.). (.)"?

Question

Я считаю, что я понимаю 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 

Если «просто применяя определение» является единственным способом сделать это, как же кто-нибудь придумал (.) . (.)?
Должно быть какое-то более глубокое понимание или интуиция, которую мне не хватает.

Answer 1

Вы также можете использовать ваше понимание fmap . fmap.

Если у Вас есть два Functor сек foo и bar, затем

fmap . fmap :: (a -> b) -> foo (bar a) -> foo (bar b) 

fmap . fmap принимает функцию и производит индуцированную функцию для композиции двух Functor с.

Теперь для любого типа t, (->) t является Functor и fmap для этого Functor является (.).

Так (.) . (.) является fmap . fmap для случая, когда два Functor s являются (->) 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) 

т.д.

Answer 2

Итак, это то, что я получаю, когда я делаю немного более постепенного расширения

(.) 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> 

Пока я не знаю, происхождение этого комбинатора, вполне вероятно, что он был , разработанный для использования в комбинационной логике, где вы строго работаете с комбинаторами, , поэтому вы не можете определить вещи, используя более удобные лямбда-выражения. Может быть какая-то интуиция, которая идет с этим, но я ее не нашел. Скорее всего, вы бы разработали некоторый уровень интуиции, если бы вам пришлось сделать это достаточно.

Answer 3

Ваше решение расходится, когда вы вводите 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)

Edit:

Более глубокое значение заключается в следующем:

(.) просто определяется как

\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) 

Подставьте второе выражение для f1 ...

\x0 -> \g1 x1 -> ((\f2 g2 x2 -> f2 (g2 x2)) x0) (g1 x1) 

Теперь "сальто назад"! (beta-reduction on):
Это интересный шаг - 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) 

, где аргументы хорошо по порядку.

Answer 4

Это проще всего написать уравнения, combinators-style, вместо лямбда-выражений: 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), вы хотите, чтобы преобразовать его into a combinatory form (избавиться от всех скобок и переменных повторений). Затем вы применяете шаблоны, соответствующие определениям комбинаторов, надеясь проследить этот вывод назад. Это намного меньше механического/автоматического.

Answer 5

Выполняется с (.) . (.) на самом деле довольно просто, это интуиция за тем, что она делает, что довольно сложно понять.

(.) доставит вас очень далеко, переписывая выражение в вычисления типа «труба» (подумайте о | в оболочке). Тем не менее, становится неудобно использовать, как только вы пытаетесь создать функцию, которая принимает несколько аргументов с помощью функции, которая принимает только одну. В качестве примера, давайте определение concatMap:

concatMap :: (a -> [b]) -> [a] -> [b] 
concatMap f xs = concat (map f xs) 

Избавление от xs просто стандартная операция:

concatMap f = concat . map f 

Однако нет «хороший» способ избавления от f. Это вызвано тем фактом, что map принимает два аргумента, и мы хотели бы применить concat к его окончательному результату.

Вы можете, конечно, применить некоторые pointfree трюки и уйти только с (.):

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 
    =    (.) . (.) 

Что касается интуиции, есть такой very nice article, что вы должны читать. Я перефразирую часть о (.):

Давайте снова думать о том, что наш комбинатор должен делать: он должен применять f к результате из результата из g (я использую конечный результат в перед тем, как это сделать, это действительно то, что вы получаете, когда полностью применяете - modulo объединяющие переменные типа с другим типом функции - g, результат вот только приложение g x для некоторых x).

Что это означает для нас, чтобы нанести f на результат от g? Хорошо, как только мы применим g к некоторому значению, мы возьмем результат и применим к нему f. Звучит знакомо: вот что делает (.).

result :: (b -> c) -> ((a -> b) -> (a -> c)) 
result = (.) 

Теперь, получается, что состав (наша из слов) этих комбинаторов это просто функция композиции, то есть:

(.:) = result . result -- the result of result