Nouveau à Haskell, ne comprends pas pourquoi je reçois une erreur de type infini

Question

module Main where 

rev :: [a] -> [a] 
rev (x:[]) = x 
rev (x:xs) = (rev xs):x 

lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 

main = do 
    print (rev lst) 

Je travaille mon chemin à travers 99 Haskell Problems et essayer d'écrire une fonction pour inverser une liste (oui, je sais qu'il ya déjà un dans le prélude).

Mon problème est que lorsque je tente de compiler le code ci-dessus (ou tapez simplement la définition de la fonction dans GHCi), je reçois:

Occurs check: cannot construct the infinite type: a = [a] 
In the expression: rev :: [a] -> [a] 
In the definition of `it': it = rev :: [a] -> [a] 

Je ne suis pas tout à fait sûr où je vais mal avec mes types pour obtenir cette erreur. Je suppose que cela a quelque chose à voir avec la façon dont je fais correspondre les motifs, mais je ne sais pas pourquoi.

Answer 1

Le problème est que le type de (:) est a -> [a] -> [a], mais votre troisième ligne (rev (x:xs) = (rev xs):x) aurait besoin d'être [a] -> a -> [a].

La fonction que vous souhaitez est communément appelée snoc (c'est-à-dire le contraire de cons, qui est le nom de (:) dans le monde Lisp). Il n'est pas prévu pour les listes dans les bibliothèques standard Haskell, mais vous pouvez facilement faire la même chose avec (++):

rev :: [a] -> [a] 
rev (x:[]) = [x] 
rev (x:xs) = rev xs ++ [x] 

---

EDIT: Il y avait aussi un problème dans la deuxième ligne, comme le souligne Landei sur dans les commentaires: vous retourniez l'élément, pas une liste contenant l'élément.

Answer 2

Travis est correct en ce qui concerne l'erreur spécifique, mais pour le bien de toute personne qui trouve cette question plus tard lors de la recherche « erreurs de type infini », voici ce que (apparemment cryptique) message:

Une fonction ayant le type les variables dans sa signature signifient qu'il ne se soucie pas du type qu'il reçoit là - il n'inspecte pas les valeurs de ce type, ce ne sont que des boîtes noires. Cependant, quand effectivement en utilisant une telle fonction, les variables de type seront clouées à quelque chose de plus concret sur une base par utilisation. Cependant, des types spécifiques ne sont pas nécessaires - les variables de type peuvent également être remplies avec d'autres variables de type. Ce processus unification fait partie de l'inférence de type et permet au compilateur de combiner des variables de type inconnu dans différentes parties du programme.

Les erreurs qui se produisent lorsque les variables de type de liaison peuvent souvent sembler cryptiques au début, en particulier lorsque GHC tente de combiner des variables dans la même signature de type. Par exemple:

• Si le compilateur essaie d'unifier deux variables distinctes, il se plaindra de « variables de type rigides liés par une signature de type », ce qui signifie qu'il ne peut pas unifier les deux types parce que vous avez dit explicitement ils étaient distincts.

• Si le compilateur tente d'unifier une variable de type avec un sous-ensemble de lui-même, par exemple, décider que la variable de type a doit être le même que [a], il se plaindra d'un type infini, ce qui signifie simplement que l'unification naïve dit que a est réellement [a] est réellement [[a]] est réellement [[[a]]] ... et ainsi de suite.