Плоская карта Haskell

Я новичок, интересующийся Haskell, и я пытался самостоятельно реализовать плоскую карту (>>=), чтобы лучше понять ее. В настоящее время у меня есть

flatmap :: (t -> a) -> [t] -> [a]  
flatmap _ [] = []  
flatmap f (x:xs) = f x : flatmap f xs

который реализует часть "карты", но не "плоскую".
Большинство модификаций, которые я делаю, приводят к обескураживающему и довольно неинформативному

Occurs check: cannot construct the infinite type: a = [a]  
    When generalising the type(s) for `flatmap'

ошибка.

Что мне не хватает?


flatten higher-order-functions map haskell
person Mantas Vidutis    schedule 07.06.2010    source источник
comment
Кстати, в Википедии описывается, что такое проверка событий: en.wikipedia.org/wiki/Occurs_check   -  person jrockway    schedule 08.06.2010

Ответы (1)


arrow_upward
23
arrow_downward

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

flatmap _ [] = []  
flatmap f (x:xs) = f x ++ flatmap f xs

Что, как оказалось, совершенно правильно. Однако, если вы забыли также изменить сигнатуру типа, произойдет следующее:

Средство проверки типов видит, что вы используете ++ для результатов f x и flatmap f xs. Поскольку ++ работает с двумя списками одного типа, средство проверки типов теперь знает, что оба выражения должны оцениваться как списки одного типа. Теперь программа проверки типов также знает, что flatmap f xs вернет результат типа [a], поэтому f x также должен иметь тип [a]. Однако в сигнатуре типа сказано, что f имеет тип t -> a, поэтому f x должен иметь тип a. Это приводит средство проверки типов к выводу, что [a] = a является противоречием и приводит к сообщению об ошибке, которое вы видите.

Если вы измените сигнатуру типа на flatmap :: (t -> [a]) -> [t] -> [a] (или удалите ее), она будет работать.

person sepp2k    schedule 07.06.2010
comment
Спасибо. Это была именно моя проблема. - person Mantas Vidutis; 07.06.2010
comment
Иногда это также происходит, если вы не укажете сигнатуру типа. - person Martijn; 07.06.2010