permutations de liste dans haskell

Question

Donc je suis nouveau à haskell et je joue avec lui depuis un moment maintenant. Je veux obtenir ma fonction qui produit toutes les permutations de liste pour fonctionner. J'ai écrit 2 implémentations, l'une fonctionne bien, l'autre me donne une erreur. Toute aide serait géniale.

Ceci est le premier (travail) mise en œuvre:

permute [] = [[]] 
permute xs = [y| x <- xs, y <- map (x:) $ permute $ delete x xs] 

Celui-ci me donne une erreur:

permute [] = [[]] 
permute xs = map (\x -> map (x:) $ permute $ delete x xs) xs 

et voici le message d'erreur:

Occurs check: cannot construct the infinite type: t0 = [t0] 
Expected type: [t0] 
Actual type: [[t0]] 
In the expression: map (x :) $ permute $ delete x xs 
In the first argument of `map', namely 
`(\ x -> map (x :) $ permute $ delete x xs)' 

Je d apprécier si quelqu'un pourrait expliquer pourquoi je reçois cette erreur. Merci

Answer 1

Utilisez des signatures de type pour faciliter la vie du compilateur.

permute :: Eq a => [a] -> [[a]], et maintenant nous avons:

Couldn't match type `a' with `[a]' 
    `a' is a rigid type variable bound by 
     the type signature for permute :: Eq a => [a] -> [[a]] 
     at perm.hs:4:1 
Expected type: [a] 
    Actual type: [[a]] 
In the expression: map (x :) $ permute $ xs 
In the first argument of `map', namely 
    `(\ x -> map (x :) $ permute $ xs)' 

Alors, semble que nous devons utiliser concatMap au lieu de map.

permute :: Eq a => [a] -> [[a]] 
permute [] = [[]] 
permute xs = concatMap (\x -> map (x:) $ permute $ delete x xs) xs 

Answer 2

Vous pouvez utiliser quelque chose comme ça si vous n'êtes pas sûr que vous avez un type deriving Eq (à utiliser delete pre- scrit):

perms :: [a] -> [[a]] 
perms [] = [[]] 
perms [a] = [[a]] 
perms [a,b] = [[a,b],[b,a]] 
perms xs = concatMap f [0..length xs - 1] where 
    f i = map ((xs!!i):) $ perms $ exclude i xs 
    exclude n xs = take (n) xs ++ drop (n+1) xs 

Peut-être est un surpuissant :)