Поиск типа функции композиции в Haskell

Скажем, у меня есть следующая функция в Haskell:

compose2 = (.) . (.)

Как мне найти тип этой функции? Из-за множества композиций я застреваю, пытаясь определить тип этой функции.

Я знаю, что могу использовать :t compose2 для получения типа. Однако я хочу знать, как это сделать без помощи компьютера. Какие шаги я должен предпринять, чтобы найти тип?


types haskell function-definition
person Miles Cox    schedule 28.11.2020    source источник
comment
тесно связаны: stackoverflow.com/ вопросы/34701011/   -  person Will Ness    schedule 28.11.2020
comment
для ответа на вопрос о том, как получить тип функции a в целом, см., например, это или просмотрите, например. эти   -  person Will Ness    schedule 28.11.2020
comment
Спасибо за предложения! Я сам не смог найти похожий пост.   -  person Miles Cox    schedule 28.11.2020

Ответы (1)


arrow_upward
6
arrow_downward

Может помочь, если мы сначала дадим функциям композиции более уникальный идентификатор, например:

compose2 = (.)2 .1 (.)3

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

compose2 = ((.)1 (.)2) (.)3

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

(.)1 :: (b -> c) -> ((a -> b) -> (a -> c))
(.)2 :: (e -> f) -> ((d -> e) -> (d -> f))
(.)3 :: (h -> i) -> ((g -> h) -> (g -> i))

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

Мы знаем, что (.)2 является параметром приложения функции с (.)1, поэтому это означает, что тип параметра (b -> c) совпадает с типом (e -> f) -> ((d -> e) -> (d -> f)), и, следовательно, b ~ (e -> f) и c ~ ((d -> e) -> (d -> f)).

Кроме того, мы знаем, что тип второго параметра (.)1 совпадает с типом (.)3, поэтому (a -> b) ~ ((h -> i) -> ((g -> h) -> (g -> i))) и, следовательно, a ~ (h -> i) и b ~ ((g -> h) -> (g -> i)), поэтому возвращаемый тип (.)1, который равен (a -> c), таким образом, может быть специализирован для:

((.)1 (.)2) (.)3 :: a -> c

и начиная с a ~ (h -> i) и c ~ (d -> e) -> (d -> f):

((.)1 (.)2) (.)3 :: (h -> i) -> ((d -> > e) -> (d > f))

мы знаем, что b эквивалентно как b ~ (e -> f), так и b ~ ((g -> h) -> (g -> i)), так что это означает, что e ~ (g -> h) и f ~ (g -> i), таким образом, мы можем дополнительно специализировать подпись:

((.)1 (.)2) (.)3 :: (h -> i) -> ((d -> (g -> h)) -> (d -> (g -> i)))

который является более подробной формой:

(.)2 .1 (.)3 :: (h -> i) -> (d -> g -> h) -> d -> g -> i

Если мы автоматически выведем тип, мы получим:

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

Если мы таким образом заменим b на h, c на i, a1 на d и a на g, мы получим тот же самый тип.

person Willem Van Onsem    schedule 28.11.2020
comment
Большое спасибо за такой исчерпывающий ответ! Теперь я могу получить тип сам :) - person Miles Cox; 28.11.2020