Haskell List Reversal Error

Question

Hi guys,

I'm writing a list reversal program for haskell.

I've got the idea for the list reversal and that has lead to the following code:

myreverse list1
 | list1 == []    = list1
 | otherwise      = (myreverse(tail list1)):(head list1)

Unfortunately the above code results in the following error:

Occurs check: cannot construct the infinite type: a = [[a]]
 Expected type: [[a]]
 Inferred type: a
 In the second argument of '(:)', namely '(head list1)'
 In the expression: (myreverse(tail list1)):(head list1)

PS: I get the same sort of error when I run it on a snippet that I wrote called mylast coded below:

mylast list
 | list == []      = []
 | otherwise       = mylast_helper(head list1)(tail list1)

mylast_helper item list2
 | list2 == []     = item
 | otherwise       = mylast_helper(head list2)(tail list2)

Error occurs at the otherwise case of the recursive helper.

EDIT: Thanks for all the input, I guess I forgot to mention that the constraints of the question forbid the use of the ++ operator. I'll keep that in mind for future questions I create.

Cheers, -Zigu

Answer 1

The type of cons (:) is a -> [a] -> [a] - in other words, you give it an element and then a list and it puts the element at the start of the list. In your last line, you're doing the reverse - list first and then an element. To fix it up, change the : to the list concat operator ++:

myreverse list1
  | list1 == [] = list1
  | otherwise   = (myreverse (tail list1)) ++ [head list1]

(To try and translate the error, it's saying "OK, the first argument to : you've given me is a list, therefore the second argument needs to be a list of elements of that same type, so a list of lists...BUT...you've given me an argument which is the type of an element of the list, so I need some type that is the same as a list of lists of that type, which I can't do. Bang!")

Answer 2

First off, try adding a signature to each of your functions; this will help the compiler know what you're trying to do and give you better error messages earlier on. A signature would look like this, for example: mylast :: [a] -> a. Then, instead of using guards (|), define your function through a series of equations, using pattern matching:

mylast :: [a] -> a
mylast (x:[]) = x
mylast (_:t) = mylast t

In GHCi, you can look at the type of something using :t term. That's the best general advice I can give... look carefully at the types and make sure they make sense for how you're using them.

Answer 3

You are using the function

(:) :: a -> [a] -> [a]

with ill-typed arguments:

myReverse (tail list1) :: [a]
head list1 :: a

In your function, the list list1 must have type a. Hence the second argument, head list1, must have type [a]. GHC is warning you that it cannot construct the type you have specified for it. The head of a list is structurally smaller than the tail of a list, but you are telling it that the head of a list has type [a], yet the tail of a list has type a.

If you stare closely at your types, however, you will notice that you can append the head of list1 to the recursive call to myreverse using (++):

myReverse xs = case (null xs) of
               True  -> xs
               False -> myReverse (tail xs) ++ [head xs]

Here,

[head xs] :: [a]
myReverse (tail xs) :: [a]

which aligns with the type of append:

(++) :: [a] -> [a] -> [a]

There are much better ways to implement reverse, however. The Prelude defines reverse as a left fold (. Another version of reverse can be implemented using a right fold, and is very similar to your myReverse function:

reverse xs = foldr (\x xs -> xs ++ [x]) [] xs

Answer 4

Ended up working on this question more and answering it myself. Thanks a lot for the feedback. It pushed me along the right direction.

myreverse list1
 | list1 == []  = list1
 | otherwise    = myreverse_h(list1)([])

myreverse_h list1 list2
 | list1 == []  = list2
 | otherwise    = myreverse_h(tail list1)((head list1):list2)

Any comments on better code though? I don't think its as efficient as it could be...