Haskell FlatMap

Question

Je suis un débutant intéressé par Haskell, et j'ai essayé d'implémenter le flatmap (>> =) par moi-même pour mieux le comprendre. Actuellement, j'ai

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

qui implémente la partie "carte" mais pas le "plat".
La plupart des modifications je fais dans le résultat désolant et assez sans information

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

erreur

.

Qu'est-ce qui me manque? Une erreur de ce type se produit lorsque la signature de type que vous spécifiez ne correspond pas au type réel de la fonction.

Answer 1

Puisque vous ne l'avez pas montrer le code qui provoque l'erreur, je dois deviner, mais je suppose que vous l'avez changé quelque chose comme ceci:

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

qui, comme il arrive, est tout à fait correct. Cependant si vous avez oublié de changer également la signature de type ce qui va arriver:

Le vérificateur de type voit que vous utilisez ++ sur les résultats de f x et flatmap f xs. Comme ++ fonctionne sur deux listes du même type, le vérificateur de type sait maintenant que les deux expressions doivent être évaluées en listes du même type. Maintenant le typechecker sait également que flatmap f xs renverra un résultat de type [a], donc f x doit également avoir le type [a]. Cependant, dans la signature de type, il est dit que f a le type t -> a, donc f x doit avoir le type a. Cela conduit le vérificateur de type à conclure que [a] = a qui est une contradiction et conduit au message d'erreur que vous voyez.

Si vous modifiez la signature de type à flatmap :: (t -> [a]) -> [t] -> [a] (ou si vous l'enlevez), cela fonctionnera.