Haskell FlatMap

Question

Soy un principiante interesado en Haskell, y he estado tratando de implementar el flatmap (>> =) por mi cuenta para entenderlo mejor. Actualmente tengo

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

que implementa la parte "mapa" pero no la "plana".
La mayor parte de las modificaciones que crea en consecuencia el error descorazonador y bastante sin información

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

.

¿Qué me estoy perdiendo?

Answer 1

Un error como este ocurre cuando la firma de tipo que especifica no coincide con el tipo real de la función. Puesto que no se presentó el código que causa el error, tengo que adivinar, pero supongo que la ha cambiado a algo como esto:

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

Qué como es el caso, es perfectamente correcto. Sin embargo, si también olvidó cambiar la firma del tipo, sucederá lo siguiente:

El verificador de tipos considera que utiliza ++ en los resultados de f x y flatmap f xs. Como ++ funciona en dos listas del mismo tipo, el comprobador de tipos ahora sabe que ambas expresiones tienen que evaluarse en listas del mismo tipo. Ahora el typechecker también sabe que flatmap f xs devolverá un resultado del tipo [a], por lo que f x también tiene que tener el tipo [a]. Sin embargo, en la firma de tipo dice que f tiene el tipo t -> a, por lo que f x tiene que tener el tipo a. Esto lleva al verificador de tipos a concluir que [a] = a es una contradicción y conduce al mensaje de error que ve.

Si cambia la firma de tipo a flatmap :: (t -> [a]) -> [t] -> [a] (o la elimina), funcionará.