New to Haskell, don't understand why I'm getting an infinite type error

5
votes
module Main where

rev :: [a] -> [a]
rev (x:[]) = x
rev (x:xs) = (rev xs):x

lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

main = do
   print (rev lst)

I'm working my way through 99 Haskell Problems and trying to write a function to reverse a list (yes, I am aware there's one already in the prelude).

My problem is that when I try to compile the code above (or just type the function definition into GHCi), I get:

Occurs check: cannot construct the infinite type: a = [a]
In the expression: rev :: [a] -> [a]
In the definition of `it': it = rev :: [a] -> [a]

I'm not quite sure where I'm going wrong with my types to get this error. I'm guessing it has something to do with how I'm pattern matching, but I don't know why.

2
haskell
You can only element:list but not list:element (use list ++ [element] instead). I think there is a duplicate already... - kennytm
stackoverflow.com/questions/3861181/haskell-list-reversal-error - kennytm
It's better to write rev [] = [] and rev (x:xs) = rev xs ++ [x] since this handles empty list too. - sdcvvc

2 Answers

17
votes

Travis is correct regarding the specific error, but for the sake of anyone who finds this question later when searching for "infinite type errors", here's what that (seemingly cryptic) message means:

A function having type variables in its signature means that it doesn't care what type it receives there--it doesn't inspect the values of that type, they're just black boxes. However, when actually using such a function, the type variables will be nailed down to something more concrete on a per-use basis. Specific types aren't required, though--the type variables can also be filled in with other type variables. This unification process is part of type inference and lets the compiler combine unknown type variables in different parts of the program.

Errors that occur when binding type variables can often seem cryptic at first, particularly when GHC attempts to combine variables in the same type signature. For instance:

  • If the compiler tries to unify two distinct variables, it will complain about "rigid type variables bound by a type signature", which means that it can't unify the two types because you explicitly told it they were distinct.

  • If the compiler tries to unify a type variable with a subset of itself, such as deciding that the type variable a should be the same as [a], it will complain about an infinite type, which just means that naive unification says that a is actually [a] is actually [[a]] is actually [[[a]]]... and so on.

9
votes

The problem is that the type of (:) is a -> [a] -> [a], but your third line (rev (x:xs) = (rev xs):x) would need it to be [a] -> a -> [a].

The function you want is commonly called snoc (i.e. the opposite of cons, which is the name for (:) in the Lisp world). It's not provided for lists in the Haskell standard libraries, but you can easily do the same thing with (++):

rev :: [a] -> [a]
rev (x:[]) = [x]
rev (x:xs) = rev xs ++ [x]

EDIT: There was also a problem in the second line, as Landei points out in the comments: you were returning the element, not a list containing the element.