Haskell FlatMap

Я начинаю интересоваться 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

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

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

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

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

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