Erreur d'inversion de liste Haskell

Question

J'écris un programme d'inversion de liste pour haskell.

J'ai eu l'idée de l'inversion de la liste et qui a conduit au code suivant:

myreverse list1 
| list1 == [] = list1 
| otherwise  = (myreverse(tail list1)):(head list1) 

Malheureusement, les résultats de code ci-dessus dans l'erreur suivante:

Occurs check: cannot construct the infinite type: a = [[a]] 
Expected type: [[a]] 
Inferred type: a 
In the second argument of '(:)', namely '(head list1)' 
In the expression: (myreverse(tail list1)):(head list1) 

PS: I obtenir le même genre d'erreur quand je l'exécute sur un extrait que j'ai écrit appelé mylast codé ci-dessous:

mylast list 
| list == []  = [] 
| otherwise  = mylast_helper(head list1)(tail list1) 

mylast_helper item list2 
| list2 == []  = item 
| otherwise  = mylast_helper(head list2)(tail list2) 

Une erreur se produit dans le cas contraire de l'assistant récursif.

EDIT: Merci pour toutes les entrées, je suppose que j'ai oublié de mentionner que les contraintes de la question interdisent l'utilisation de l'opérateur ++. Je garderai cela à l'esprit pour les futures questions que je vais créer.

Cheers, -Zigu

Answer 1

Le type de contre (:) est a -> [a] -> [a] - en d'autres termes, vous lui donnez un élément et une liste et il met l'élément au début de la liste. Dans votre dernière ligne, vous faites l'inverse - liste d'abord, puis un élément. Pour le corriger, changer le : à la liste opérateur concat ++:

myreverse list1 
    | list1 == [] = list1 
    | otherwise = (myreverse (tail list1)) ++ [head list1] 

(pour essayer de traduire l'erreur, il est dit « OK, le premier argument de : vous me avez donné une liste, donc le deuxième argument doit être une liste d'éléments de ce même type, donc une liste de listes ... MAIS ... vous m'avez donné un argument qui est le type d'un élément de la liste, donc j'ai besoin d'un type c'est la même chose qu'une liste de listes de ce type, ce que je ne peux pas faire Bang! ")

Answer 2

Tout d'abord, essayez d'ajouter une signature à chacune de vos fonctions; cela aidera le compilateur à savoir ce que vous essayez de faire et vous donnera de meilleurs messages d'erreur plus tôt. Une signature ressemblerait à ceci, par exemple: mylast :: [a] -> a. Ensuite, au lieu d'utiliser des gardes (|), définir votre fonction à travers une série d'équations, en utilisant la correspondance de motif:

mylast :: [a] -> a 
mylast (x:[]) = x 
mylast (_:t) = mylast t 

En GHCi, vous pouvez regarder le type de quelque chose en utilisant :tterme. C'est le meilleur conseil général que je peux donner ... regardez attentivement les types et assurez-vous qu'ils ont un sens pour la façon dont vous les utilisez.

Answer 3

Vous utilisez la fonction

(:) :: a -> [a] -> [a] 

avec des arguments mal typée:

myReverse (tail list1) :: [a] 
head list1 :: a 

Dans votre fonction, la liste list1 doit avoir le type un. Par conséquent, le deuxième argument, liste de tête1, doit avoir le type [a]. GHC vous avertit qu'il ne peut pas construire le type que vous avez spécifié pour cela.La tête d'une liste est structurellement plus petite que la queue d'une liste, mais vous dites que la tête d'une liste a le type [a], mais la queue d'une liste a le type un.

Si vous regardez attentivement vos types, cependant, vous remarquerez que vous pouvez ajouter la tête de list1 à l'appel récursif à myreverse en utilisant (++):

myReverse xs = case (null xs) of 
       True -> xs 
       False -> myReverse (tail xs) ++ [head xs] 

ici,

[head xs] :: [a] 
myReverse (tail xs) :: [a] 

qui aligne avec le type de ajouter:

(++) :: [a] -> [a] -> [a]

Il y a de bien meilleures façons de mettre en œuvre inverse, cependant. Le Prélude définit inverse comme un pli gauche (Une autre version de inverse peut être mis en œuvre en utilisant un pli à droite, et est très proche de votre fonction myReverse.

reverse xs = foldr (\x xs -> xs ++ [x]) [] xs 

Answer 4

a fini par travailler sur cette question plus et répondre à moi-même. Merci beaucoup pour les commentaires. il m'a poussé dans la bonne direction.

myreverse list1 
| list1 == [] = list1 
| otherwise = myreverse_h(list1)([]) 

myreverse_h list1 list2 
| list1 == [] = list2 
| otherwise = myreverse_h(tail list1)((head list1):list2) 

Tous les commentaires sur un meilleur code bien? Je ne pense pas aussi efficace que son il pourrait être ...