Объединение типов в Хаскеле

Question

Я вроде застрял с заданием, касающимся моих экзаменов. Я хочу выяснить типы этих двух функций, применяя алгоритм объединения вручную:

map map
(\x -> x >>= (\y -> y))

Может ли кто-нибудь указать мне правильное направление? Единственный ресурс, который я мог найти до сих пор, - это запись в Википедии, которая не очень помогает мне из-за высокого уровня абстракции.

Приветствую и спасибо.

Answer 1

Давай просто сделаем первое.

map :: (a -> b) -> [a] -> [b]

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

map :: (c -> d) -> [c] -> [d]

Теперь мы подставляем второй в качестве первого параметра первого, получая:

(a -> b) === (c -> d) -> ([c] -> [d]) (recall the associativity of (->))
a === (c -> d)
b === ([c] -> [d])

Теперь мы подставляем эти назначения типов в оставшуюся часть первой подписи, получая

map map :: [c -> d] -> [[c] -> [d]]

Очистить?

Answer 2

Тип map является map :: (a -> b) -> [a] -> [b], Отсюда тип map foo получается из [a] -> [b] заменив a а также b с тем, что может быть получено из fooтип. Если, например, foo :: t -> tзаменяешь a = t, b = t и получить [t] -> [t], Если foo :: [t] -> Int, вы получаете [[t]] -> [Int],

В вашем случае тип foo (который map) является (x -> y) -> [x] -> [y], Вы должны объединить этот тип с a -> b выяснить что a а также b должны быть заменены на. [Обратите внимание, что стрелка функции является ассоциативной справа, x -> y -> z = x -> (y -> z).]

Чтобы найти тип

\x -> x >>= (\y -> y)

использовать известный тип (>>=) :: Monad m => m a -> (a -> m b) -> m b, Игнорировать ограничение (Monad m =>) теперь.

В качестве первого аргумента (>>=), x должен иметь тип m a пока еще неизвестно m а также a, Второй аргумент (>>=) здесь личность,

(\y -> y) :: t -> t

так что вы должны объединиться t -> t с a -> m b, Это дает вам некоторую информацию о aа именно a = m b,

Что дает x :: m (m b), а также (\x -> x >>= (\y -> y)) :: type_of_x -> type_of_rhs,

Наконец, запомните временно забытое ограничение Monad m =>,