Haskell permutation function does not compile

1
votes

I'm brushing up on some Haskell and I am trying to write a permutation function that would map [1,2,3] -> [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]. I have the following -

permute:: [a] -> [[a]]
permute [] = []
permute list = map f list
        where
                f x = listProduct x (permute (exclude x list))
                exclude e list1 = filter (/= e) list1
                listProduct x list2 = map (x :) list2

The following is the error message I get -

permutations.hs:3:20:
    Couldn't match type `a' with `[a]'
      `a' is a rigid type variable bound by
          the type signature for permute :: [a] -> [[a]]
          at permutations.hs:1:11
    Expected type: a -> [a]
      Actual type: a -> [[a]]
    In the first argument of `map', namely `f'
    In the expression: map f list
    In an equation for `permute':
        permute list
          = map f list
          where
              f x = listProduct x (permute (exclude x list))
              exclude e list1 = filter (/= e) list1
              listProduct x list2 = map (x :) list2
Failed, modules loaded: none.

I would try to debug, but it doesn't even compile. Any ideas?

3
debugginghaskelltypescompiler-errorspermutation
It's debugging for you somewhat, saying that it expects f to be a function of type a -> [a] but is getting a type a -> [[a]] - גלעד ברקן
listProduct anything looks like it ought to return a [[a]], which would make f take the argument x and return a [[a]]. Perhaps try to experiment with each function independently to make sure its doing what you'd like it to. - גלעד ברקן
Gilad, why is f expected to be of type (a -> [a])? by the definition of map, seems like f is entitled to map from and to totally polymorphic types - map :: (a->b) -> [a] -> [b] map f [] = [] map f (x:xs) = f x : map f xs - Dan Sok
You should put type signatures on f, exclude and listProduct. The compiler errors when you have type signatures will give you more of a clue about where you went wrong. - TheCriticalImperitive
@TheCriticalImperitive Generally a good idea, although in this particular case that requires the ScopedTypeVariables extension, and doesn't actually help any. - Ørjan Johansen

3 Answers

2
votes

Let's focus on the involved list types, only:

permute (exclude x list)

is of type [[a]] because of the type signature of permute, hence

listProduct x (permute (exclude x list))

is also of type [[a]] by the def. of listProduct

listProduct x list2 = map (x :) list2

Summing up,

 f x = listProduct x (permute (exclude x list))

returns [[a]], but then

permute list = map f list

applies f to all the elements of a [a], returning a [[[a]]], which is not the correct return type for permute.

How to fix

  1. Turn that [[[a]]] into [[a]] by concatenating all the lists.
  2. Add an Eq a constraint, since you re using /= x in exclude
  3. The base case currently states that the empty list has no permutations, which is wrong. There is one permutation for []. (Indeed, 0!=1, not 0)
0
votes

To anyone who may be interested - to solve this problem I needed a way to simulate iteration from imperative programming, and therefore a circular list suggested itself (essentially I have been trying to simulate a solution I wrote in javascript once which involved the same process I describe, with the single exception that I took advantage of a for loop).

permute [] = [[]]
permute list = [h:tail | h <- list, tail <- (permute (exclude h list))]
  where
    exclude x = filter (/= x)

Not necessarily the most efficient solution because exclude is an O(n) operation, but neat, and works very well as a proof of concept.

0
votes

The "right" way to do this is to combine the picking and the excluding of a list item into one purely positional operation select :: [a] -> [(a,[a])]:

import Control.Arrow (second)
-- second f (a, b) = (a, f b)

select [] = []
select (x:xs) = (x,xs) : map (second (x:)) (select xs)

permute [] = [[]]    -- 1 permutation of an empty list
permute xs = [x : t | (x,rest) <- select xs, t <- permute rest]

To "debug"-develop your program you could define each internal function on its own as a global one, and see whether the bits and pieces fit together:

> let exclude e list1 = filter (/= e) list1
> let listProduct x list2 = map (x :) list2
> let f x = listProduct x (permute (exclude x list)) 
<interactive>:1:25: Not in scope: `permute' -- permute is not defined yet!!
<interactive>:1:44: Not in scope: `list'    -- need to pass 'list' in
> let f list x = listProduct x (undefined (exclude x list))
                                ---------   -- use a stand-in for now
> let permute [] = [] ; permute list = map (f list) list
> :t permute                           ---
permute :: (Eq t) => [t] -> [[[t]]]    -- one too many levels of list!

So they do fit together, it's just that the result is not what we want. Instead of changing what f produces (as the compiler suggested), we can change how its results are combined. concat removes one level of list nesting (it is the monadic join for the [] type constructor):

> let permute [] = [] ; permute list = concatMap (f list) list
> :t permute                           ---------
permute :: (Eq t) => [t] -> [[t]]      -- much better

Incidentally, were you not to specify the type signature yourself, it would compile and report the [a] -> [[[a]]] type back to you.

More importantly, by bringing the /= into the picture, you needlessly require an Eq a constraint on the items in a list: permute :: (Eq a) => [a] -> [[a]].