Search code examples
haskellfunctional-programmingreverse

Implementing function to reverse the order of elements in a list

I am trying to implement my own version of the reverse function in Haskell. The following code utilizing the : operator.

reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs : [x]

This results in the a compilation error. However, if I use the ++ operator instead, the code compiles without issue. This is demonstrated here:

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

Why doesn't the : operator work here?

Solution

  • : is used to add an element to list, so the first (left) operand should be an element (a) but you have [a] hence the type mismatch. ++ joins to lists (result of reverse' xs is of type [a] and [x] is of type [a]).

    From "Learn You a Haskell for Great Good!" An intro to lists paragraph:

    A common task is putting two lists together. This is done by using the ++ operator.

    putting something at the beginning of a list using the : operator (also called the cons operator)

    Notice how : takes a number and a list of numbers or a character and a list of characters, whereas ++ takes two lists. Even if you're adding an element to the end of a list with ++, you have to surround it with square brackets so it becomes a list.