Implementing function to reverse the order of elements in a list

Question

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?

Bear in mind that adding a value to the front of a list with `:` is cheap, while concatenating two lists with `++` is _not_. Doing `++` many times is not ideal from a performance standpoint. — Chris, Mar 01 '23 at 22:48

Guru Stron · Accepted Answer · 2023-03-01T18:28:18.600

: 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.

Implementing function to reverse the order of elements in a list

1 Answers1