Why is this form of acceptable, but the other form raises a type error?

Question

While working through Real World Haskell, I tried to complete the palindrome exercise using the following code solution:

palin :: [a] -> [a]
palin list = list ++ rev list
    where rev list
           | null list = []
           | otherwise = rev (tail list) ++ (head list)

Which raised a "cannot construct an infinite type error. However, simply replacing the parenthesis around the head list with square brackets, and it works correctly, as demonstrated in the following example:

palin :: [a] -> [a]
palin list = list ++ rev list
    where rev list
           | null list = []
           | otherwise = rev (tail list) ++ [head list]

I don't really understand why it matters, nor do I understand what does the "cannot construct infinite type a = [a]" error means. Could someone explain this?

Answer 1

In the last line, you are trying to append a non-list to a list. head list gives the first item of the list, which is type a. When you try to use ++ to append, you can't append something that isn't a list to a list. By appending [head list], you are appending a list of 1 item to the other list. The [] construct the single item list in this case.

Answer 2

++ operator has type [a] -> [a] -> [a], i.e. it takes two lists of some type and produces another list of the same type. OTOH head function has type [a] -> a, i.e. it takes a list of some type and returns a value of that type. In your first example ++ got [a] on the left hand and a on the right hand. Trying to unify these types type checker produces that error. In the second example you've constructed a single-element list from the result of head and it has type [a], so type checker is happy.

Answer 3

Assume you are the type checker and you see a this:

(tail list) ++ (head list)

You know already, the `list is a list of something. So you start with:

list::[a]

then this must be true:

(tail list)::[a]

and this:

(head list)::a

But then there's `++ which wants both its arguments to have the same type. But this means, that

a == [a] 

or by substitution:

a == [a] == [[a]] == [[[a]]] ...etc.

which is indeed an infinite type.