type error when compiling

Question

I don't understand why the following code won't compile:

 append :: [a] -> [a] -> [a]
 append xs ys = foldr (:) ys xs

 traverse :: a -> [a] -> [[a]]
 traverse x [] = [[x]]
 traverse x (y:ys) = append [(x:y:ys)] (map (y:) (traverse x ys))

 comb :: [a] -> [[a]]
 comb [] = [[]]
 comb (x:[]) = [[x]]
 comb (x:y:[]) = [[x,y],[y,x]] 
 comb (x:xs) = map (traverse x) (comb xs)

It produces the following error:

pr27.hs:13:20:
Couldn't match type `a' with `[a]'
`a' is a rigid type variable bound by
the type signature for comb :: [a] -> [[a]] at pr27.hs:10:1
Expected type: [a] -> [a]
Actual type: [a] -> [[a]]
In the return type of a call of `traverse'
In the first argument of `map', namely `(traverse x)'
Failed, modules loaded: none

But when I load just traverse and use it in an expression similar to the above, I get the desired result. What's going on?

Main> map (traverse 3) [[1,2],[2,1]]
     [[[3,1,2],[1,3,2],[1,2,3]],[[3,2,1],[2,3,1],[2,1,3]]]

Tikhon has explained the problem, so let me try to give the solution. Unless I'm badly mistaken, what you want would be achieved by changing the last equation of comb to comb (x:xs) = concatMap (traverse x) (comb xs) or comb (x:xs) = comb xs >>= traverse x. — Daniel Fischer

Tikhon Jelvis Tikhon Jelvis · Accepted Answer · 2012-02-17T22:57:33

The problem is that comb has to return a value of type [[a]]. traverse returns a value of type [[a]], so mapping it over another list produces [[[a]]], which has too many levels of nesting.

Let's look at map. It has a type map :: (x -> y) -> [x] -> [y]. traverse x has a type [a] -> [[a]]. Now we need to combine the two. To do this, we replace x with [a] and y with [[a]], getting ([a] -> [[a]]) -> [[a]] -> [[[a]]]. This clearly shows the result of mapping traverse has to have at least three levels of nesting.

If you look at your example, this is what you actually get. For comb, you only want one two levels deep.

The reason your example worked in GHCi is because an expression there can have any type. Your map (traverse 3) [[1,2], [2,1]] expression is perfectly legal; however, it has the type Num a => [[[a]]], which is a list of lists of lists of numbers. (Try it: :t map (traverse 3) [[1,2], [2,3]].) However, the type of comb is [a] -> [[a]]. This means the result has to be a list of lists, not a list of lists of lists. So the issue is that map (traverse 3) is incompatible with comb, not that it is illegal by itself.

type error when compiling

1 Answers