Haskell FlatMap - PullRequest
Новая
       35

Haskell FlatMap

12 голосов
/ 07 июня 2010

Я новичок, интересующийся 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'

ошибка.

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

1 Ответ

22 голосов
/ 07 июня 2010

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

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] (или удалите ее), она будет работать.

...