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

Question

(.) принимает две функции, которые принимают одно значение и возвращают значение:

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

поскольку (.) принимает два аргумента, я чувствую, (.).(.) должен быть недействительным, но это совершенно нормально:

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

Что здесь происходит? Я понимаю, что этот вопрос плохо сформулирован... все функции действительно принимают один аргумент благодаря карри. Возможно, лучший способ сказать, что типы не совпадают.

Answer 1

Давайте сначала поиграем в 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 на самом деле ReaderMonad так слоистый Reader s подобен наличию нескольких независимых видов глобального неизменного состояния.

Или как наличие нескольких входных аргументов, на которые не влияет fmap ING. Вроде как составление новой функции продолжения для "просто результата" (>1) функции арности.

---

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

Answer 2

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

• Desugar инфиксная запись:
  (.) (.) (.)

• Eta-расширения:
  (\ 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))))

• Ресугар лямбда нотация:
  \ x d y z -> x (d y z)

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

Answer 3

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

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 это просто функциональная композиция! Когда мы сочиняем два fmaps мы отображаем два уровня функтора функции. У нас изначально есть что-то типа (->) 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)

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

Answer 4

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

id :: a -> a
id x = x

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

> id "hello" 
"hello"

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

> id not True
False

Или даже:

> id id "hello"
"hello"

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

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

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

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

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

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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

Представьте, что у вас есть простая функция: она складывает 2 числа, а затем сводит на нет результат. Мы назовем это foo:

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), Можем ли мы изменить это еще дальше? Да мы можем:

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

(.).(.) эквивалентно (.)(.)(.), потому что в 1-м выражении точка в середине может быть перемещена в позиции префикса и заключена в круглые скобки, что приводит к 2-му выражению.

Теперь мы можем переписать наш foo функция:

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

Теперь вы знаете, что (.).(.) эквивалентно (\f g x y -> f (g x y)):

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