Получение предполагаемого типа составных функций Haskell: в частности (.) map uncurry

Ключевая идея в получении сигнатур типов:

1. Убедитесь, что вы установили приоритеты операторов и функций прямо перед тем, как начать.
   Обратите внимание, что приложение-функция имеет наивысший приоритет и ассоциируется слева, поэтому:
2. Первый аргумент важнее всего — сначала разберитесь с ним, а затем
3. В сигнатурах типов -> ассоциируется справа.
4. Получив тип первого аргумента, замените его везде, где он появляется.

Давайте проработаем ваш пример.

Типы

(.)  :: (b -> c) -> (a -> b) -> a -> c
map  :: (a -> b) -> [a] -> [b]
uncurry :: (a -> b -> c) -> (a, b) -> c 

Дайте каждой функции непересекающиеся имена типов

Во-первых, это сбивает с толку, потому что существует множество a, и все они не означают одно и то же, поэтому я буду каждый раз переименовывать типы новыми буквами.

(.)  :: (b -> c) -> (a -> b) -> a -> c
map  :: (d -> e) -> [d] -> [e]
uncurry :: (f -> g -> h) -> (f, g) -> h 

Включите типы в скобки, связывая их справа

(.)  :: (b -> c) -> ((a -> b) -> a -> c)
map  :: (d -> e) -> ([d] -> [e])
uncurry :: (f -> (g -> h)) -> ((f, g) -> h)

Сопоставьте тип первого аргумента со всем типом этого аргумента

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

Теперь (.) имеет первый аргумент (b->c), поэтому (b->c) должен унифицироваться с типом map:

(.)  :: (   b     ->      c      )   -> ((a -> b) -> (a -> c))
map  ::  (d -> e) -> ([d] -> [e])

когда мы подставляем b ~ (d->e) и c ~ ([d]->[e]) в тип (.), мы получаем:

(.) :: ((d->e) -> ([d]->[e]))   ->  ((a -> (d->e)) -> (a -> ([d]->[e])))

и поэтому map становится первым аргументом этого, поэтому он исчезает из сигнатуры типа, когда мы его указываем, давая

(.)           map               ::  ((a -> (d->e)) -> (a -> ([d]->[e])))

Проверить с помощью интерпретатора, например ghci или Hugs

Hugs> :t (.) map
(map .) :: (a -> b -> c) -> a -> [b] -> [c]

Да, когда мы добавляем скобки из-за правоассоциативности ->, это то же самое.

Перейти к следующему аргументу

Итак, теперь у нас есть

(.) map :: ((a -> (d->e)) -> (a -> ([d]->[e])))
uncurry :: (f -> (g -> h)) -> ((f, g) -> h)

Ужасно заманчиво сопоставить эти два первых аргумента, поскольку они выглядят одинаково, но, конечно, нам нужно сопоставить первый аргумент (.) map с целым типом uncurry:

Сопоставьте тип первого аргумента со всем типом этого аргумента

(.) map :: ((     a      -> (  d   -> e)) -> (a -> ([d]->[e])))
uncurry ::   (f->(g->h)) -> ((f,g) -> h)

давая a ~ (f->(g->h)), d ~ (f,g) и e ~ h:

(.) map :: (((f->(g->h)) -> ((f,g)-> h)) -> ((f->(g->h)) -> ([(f,g)]->[h])))

и применение этого к uncurry дает

(.) map            uncurry               :: ((f->(g->h)) -> ([(f,g)]->[h])))

Проверьте с помощью переводчика

Hugs> :t (.) map uncurry
map . uncurry :: (a -> b -> c) -> [(a,b)] -> [c]

Отлично - мы сделали это!

Работа с операторами

Если мы возьмем пример length . map (.) $ repeat id ++ [] ++ [], нам понадобятся исправления всех этих операторов, но мы можем сначала заключить в скобки приложения функций, потому что они имеют приоритет:

length . map (.) $ repeat id ++ [] ++ []
length . (map (.)) $ (repeat id) ++ [] ++ []

Расположите операторы в порядке приоритета

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

infixr 9 .
infixr 5 ++
infixr 0 $

Оператор с наивысшим приоритетом . сначала помещается в квадратные скобки:

(length . (map (.))) $ (repeat id) ++ [] ++ []

Затем ++, который ассоциируется справа:

(length . (map (.))) $ ((repeat id) ++ ([] ++ []))

и есть только одно использование $, поэтому я не стал брать его в скобки.

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

Обычно помогает начать с самых вложенных скобок.

(.) map uncurry эквивалентно ((.) map) uncurry. Функция map не применяется к uncurry, она передается (.). Затем результат, который вы, надеюсь, считаете функцией, получает uncurry в качестве аргумента.

Что касается того, откуда взялись b1, не забывайте, что имена переменных типа не важны, вы можете переименовывать их, если вы аналогичным образом переименовываете все вхождения переменной данного типа. Итак, это:

(.) map uncurry :: (a -> b1 -> b) -> [(a, b1)] -> [b]

эквивалентно этому:

(.) map uncurry :: (apple -> pear -> plum) -> [(apple, pear)] -> [plum]