Could not deduce (a ~ [a])

Question

I try to write a function, which takes a list of sublists, reverses sublists and returns concatenated, reversed sublists. Here is my attempt:

conrev :: Ord a => [[a]] -> [a]
conrev [[]] = []
conrev [[a]] = reverse [a]
conrev [(x:xs)] = reverse x ++ conrev [xs]

main = putStrLn (show (conrev [[1,2],[],[3,4]]))

I get this error:

3.hs:4:27:
    Could not deduce (a ~ [a])
    from the context (Ord a)
      bound by the type signature for conrev :: Ord a => [[a]] -> [a]
      at 3.hs:1:11-31
      `a' is a rigid type variable bound by
      the type signature for conrev :: Ord a => [[a]] -> [a] at 3.hs:1:11
    In the first argument of `reverse', namely `x'
    In the first argument of `(++)', namely `reverse x'
    In the expression: reverse x ++ conrev [xs]

What am I doing wrong? The second question is - could the type signature be more generic? I have to write as generic as possible.

Answer 1

In the equation

conrev [(x:xs)] = reverse x ++ conrev [xs]

you match a list containing a single element, which is a nonempty list x:xs. So, given the type

conrev :: Ord a => [[a]] -> [a]

the list x:xs must have type [a], and thus x :: a.

Now, you call reverse x, which means x must be a list, x :: [b]. And then you concatenate

reverse x :: [b]

with

conrev [xs] :: [a]

from which it follows that b must be the same type as a. But it was determined earlier that a ~ [b]. So altogether, the equation demands a ~ [a].

If you had not written the (unnecessary) Ord a constraint, you would have gotten the less opaque

Couldn't construct infinite type a = [a]

error.

Your implementation would work if you removed some outer []:

conrev :: Ord a => [[a]] -> [a]
conrev [] = []
conrev [a] = reverse a
conrev (x:xs) = reverse x ++ conrev xs

but the better implementation would be

conrev = concat . map reverse