CODEWITHSUNDEEP
listhaskellpermutation
turingcomplete
turingcomplete

Reputation: 2188

list permutations in haskell

So I'm new to haskell and I've been playing with it for a while now. I want to get my function that outputs all list permutations to work. I have written 2 implementations, one works well, the other is giving me an error. Any help would be awesome.

This is the first (working) implementation:

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

This one is giving me an error:

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

and here's the error message:

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)'

I'd appreciate if someone could explain why I'm getting this error. Thanks

Upvotes: 0

Views: 6414

Answers (2)

Nikita Hismatov
Nikita Hismatov

Reputation: 1656

You can use something like this if you are not sure that you have a type deriving Eq (reqiured to use delete):

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

Maybe it is an overkill :)

Upvotes: 0

ДМИТРИЙ МАЛИКОВ
ДМИТРИЙ МАЛИКОВ

Reputation: 21972

Use type signatures to make the compiler's life easier.

permute :: Eq a => [a] -> [[a]], and now we have:

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)'

So, seems like we need to use concatMap instead of map.

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

Upvotes: 5

Related Questions