Составление композиции функций: как работает (.).(.)?

Давайте сначала поиграем в typechecker для механического доказательства. Позже я опишу интуитивный способ мышления об этом.

Я хочу применить (.) к (.), а затем применить (.) к результату. Первое приложение помогает нам определить некоторые эквивалентности переменных.

((.) :: (b -> c) -> (a -> b) -> a -> c) 
      ((.) :: (b' -> c') -> (a' -> b') -> a' -> c') 
      ((.) :: (b'' -> c'') -> (a'' -> b'') -> a'' -> c'')

let b = (b' -> c') 
    c = (a' -> b') -> a' -> c'

((.) (.) :: (a -> b) -> a -> c) 
      ((.) :: (b'' -> c'') -> (a'' -> b'') -> a'' -> c'')

Потом начинаем второй, но быстро застреваем...

let a = (b'' -> c'')

Это ключевой момент: мы хотим let b = (a'' -> b'') -> a'' -> c'', но мы уже определили b, поэтому вместо этого мы должны попытаться объединить --- чтобы максимально согласовать наши два определения. К счастью, они действительно совпадают

UNIFY b = (b' -> c') =:= (a'' -> b'') -> a'' -> c''
which implies 
      b' = a'' -> b''
      c' = a'' -> c''

и с этими определениями/объединениями мы можем продолжить приложение

((.) (.) (.) :: (b'' -> c'') -> (a' -> b') -> (a' -> c'))

затем расширить

((.) (.) (.) :: (b'' -> c'') -> (a' -> a'' -> b'') -> (a' -> a'' -> c''))

и очистить его

substitute b'' -> b
           c'' -> c
           a'  -> a
           a'' -> a1

(.).(.) :: (b -> c) -> (a -> a1 -> b) -> (a -> a1 -> c)

что, честно говоря, немного нелогично.

Вот интуиция. Сначала взгляните на fmap

fmap :: (a -> b) -> (f a -> f b)

он «поднимает» функцию в Functor. Мы можем применить его повторно

fmap.fmap.fmap :: (Functor f, Functor g, Functor h) 
               => (a -> b) -> (f (g (h a)) -> f (g (h b)))

позволяя нам поднимать функцию на все более и более глубокие уровни Functors.

Оказывается, тип данных (r ->) — это Functor.

instance Functor ((->) r) where
   fmap = (.)

который должен выглядеть довольно знакомо. Это означает, что fmap.fmap переводится как (.).(.). Таким образом, (.).(.) просто позволяет нам преобразовать параметрический тип все более и более глубоких слоев (r ->) Functor. (r ->) Functor на самом деле является Reader Monad, поэтому многоуровневые Reader подобны множеству независимых видов глобального неизменного состояния.

Или например иметь несколько входных аргументов, на которые не влияет fmaping. Что-то вроде создания новой функции продолжения на основе «только результата» функции арности (>1).

Наконец, стоит отметить, что если вы думаете, что это интересно, то это формирует основную интуицию, лежащую в основе получения линз в Control.Lens.

Давайте на мгновение забудем о типах и просто воспользуемся лямбда-исчислением.

• Обозначение инфикса Desugar:
  (.) (.) (.)

• Эта-расширить:
  (\ a b -> (.) a b) (\ c d -> (.) c d) (\ e f -> (.) e f)

• Встроить определение (.):
  (\ a b x -> a (b x)) (\ c d y -> c (d y)) (\ e f z -> e (f z))

• Замените a:
  (\ b x -> (\ c d y -> c (d y)) (b x)) (\ e f z -> e (f z))

• Замените b:
  (\ x -> (\ c d y -> c (d y)) ((\ e f z -> e (f z)) x))

• Замените e:
  (\ x -> (\ c d y -> c (d y)) (\ f z -> x (f z)))

• Замените c:
  (\ x -> (\ d y -> (\ f z -> x (f z)) (d y)))

• Замените f:
  (\ x -> (\ d y -> (\ z -> x (d y z))))

• Обозначение Resugar лямбда:
  \ x d y z -> x (d y z)

И если вы спросите GHCi, вы обнаружите, что это ожидаемый тип. Почему? Поскольку стрелка функции правоассоциативна для поддержки каррирования: тип (b -> c) -> (a -> b) -> a -> c на самом деле означает (b -> c) -> ((a -> b) -> (a -> c)). В то же время переменная типа b может обозначать любой тип, включая тип функции. Видишь связь?

Вот более простой пример того же явления:

id :: a -> a
id x = x

Тип id говорит, что id должен принимать один аргумент. И действительно, мы можем вызвать его с одним аргументом:

> id "hello" 
"hello"

Но получается то, что мы также можем назвать с двумя аргументами:

> id not True
False

Или даже:

> id id "hello"
"hello"

Что здесь происходит? Ключ к пониманию id not True заключается в том, чтобы сначала взглянуть на id not. Понятно, что это разрешено, потому что id применяется к одному аргументу. Тип not равен Bool -> Bool, поэтому мы знаем, что a из типа идентификатора должно быть Bool -> Bool, поэтому мы знаем, что это вхождение идентификатора имеет тип:

id :: (Bool -> Bool) -> (Bool -> Bool)

Или, с меньшим количеством скобок:

id :: (Bool -> Bool) -> Bool -> Bool

Таким образом, это вхождение id на самом деле принимает два аргумента.

Те же рассуждения работают и для id id "hello" и (.) . (.).

Это один из тех изящных случаев, когда я думаю, что проще сначала понять более общий случай, а затем подумать о конкретном случае. Итак, давайте подумаем о функторах. Мы знаем, что функторы позволяют отображать функции на структуру.

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Но что, если у нас есть два слоя функтора? Например, список списков? В этом случае мы можем использовать два слоя fmap

>>> let xs = [[1,2,3], [4,5,6]]
>>> fmap (fmap (+10)) xs
[[11,12,13],[14,15,16]]

Но шаблон f (g x) точно такой же, как (f . g) x, поэтому мы могли бы написать

>>> (fmap . fmap) (+10) xs
[[11,12,13],[14,15,16]]

Какой тип fmap . fmap?

>>> :t fmap.fmap
  :: (Functor g, Functor f) => (a -> b) -> f (g a) -> f (g b)

Мы видим, что он отображает два слоя функтора, как мы и хотели. Но теперь помните, что (->) r — это функтор (тип функций из r, который вы могли бы предпочесть читать как (r ->)), и его экземпляр функтора — это

instance Functor ((->) r) where
  fmap f g = f . g

Для функции fmap — это просто композиция функций! Когда мы составляем два fmap, мы отображаем два уровня функционального функтора. Сначала у нас есть что-то типа (->) s ((->) r a), что эквивалентно s -> r -> a, и в итоге мы получим что-то типа s -> r -> b, поэтому тип (.).(.) должен быть

(.).(.) :: (a -> b) -> (s -> r -> a) -> (s -> r -> b)

которая берет свою первую функцию и использует ее для преобразования вывода второй (с двумя аргументами) функции. Так, например, функция ((.).(.)) show (+) — это функция двух аргументов, которая сначала складывает свои аргументы, а затем преобразует результат в String, используя show:

>>> ((.).(.)) show (+) 11 22
"33"

Тогда возникает естественное обобщение для размышлений о более длинных цепочках fmap, например

fmap.fmap.fmap ::
  (Functor f, Functor g, Functor h) => (a -> b) -> f (g (h a)) -> f (g (h b))

который отображает три слоя функтора, что эквивалентно составлению функции с тремя аргументами:

(.).(.).(.) :: (a -> b) -> (r -> s -> t -> a) -> (r -> s -> t -> b)

Например

>>> import Data.Map
>>> ((.).(.).(.)) show insert 1 True empty
"fromList [(1,True)]"

который вставляет значение True в пустую карту с ключом 1, а затем преобразует вывод в строку с show.

Эти функции могут быть полезны в целом, поэтому иногда вы видите их определенными как

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

так что вы можете написать

>>> let f = show .: (+)
>>> f 10 20
"30"

Конечно, можно дать более простое и точное определение (.:).

(.:) :: (a -> b) -> (r -> s -> a) -> (r -> s -> b)
(f .: g) x y = f (g x y)

что может помочь несколько демистифицировать (.).(.).

Вы правы, (.) принимает только два аргумента. Вас просто смущает синтаксис haskell. В выражении (.).(.) на самом деле точка в середине принимает две другие точки в качестве аргумента, как и в выражении 100 + 200, которое можно записать как (+) 100 200.

(.).(.) === (number the dots)
(1.)2.(3.) === (rewrite using just syntax rules)
(2.)(1.)(3.) === (unnumber and put spaces)
(.) (.) (.) ===

И из (.) (.) (.) должно быть еще более ясно, что первый (.) принимает второй (.) и третий (.) в качестве аргументов.

Да, это из-за каррирования. (.), как и все функции в Haskell, принимает только один аргумент. То, что вы составляете, является первым частичным вызовом каждого соответствующего составного (.), который принимает свой первый аргумент (первую функцию композиции).

^{(Сначала прочитайте мой ответ о композиции функций, операторе $ и бесточечном стиле.)}

foo a b = negate (a + b)

foo a b = negate $ a + b
foo a b = negate $ (+) a b
foo a b = negate $ (+) a $ b
foo a b = negate . (+) a $ b
foo a   = negate . (+) a -- f x = g x is equivalent to f = g
foo a   = (.) negate ((+) a) -- any infix operator is just a function
foo a   = (negate.) ((+) a) -- (2+) is the same as ((+) 2)
foo a   = (negate.) $ (+) a
foo a   = (negate.) . (+) $ a
foo     = (negate.) . (+)
foo     = ((.) negate) . (+)
foo     = (.) ((.) negate) (+) -- move dot in the middle in prefix position
foo     = ((.) ((.) negate)) (+) -- add extra parentheses

(.) ((.) negate)
(.) . (.) $ negate -- because f (f x) is the same as (f . f) x
(.)(.)(.) $ negate
((.)(.)(.)) negate

foo = ((.).(.)) negate (+)
foo = ((.)(.)(.)) negate (+) -- same as previous one
foo = negate .: (+)
  where (.:) = (.).(.)

(\f g x y -> f (g x y)) negate (+) 2 3 -- returns -5
((.).(.)) negate (+) 2 3 -- returns -5