Unexpected result while reversing a list

Question

I need some explanation into the unexpected result of the code below, seemingly, due to some bug.

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

*Main> reverse' [0,8,2,5,6,1,20,99,91,1]
[1,1,1,1,1,1,1,1,1,1]

Is this because of some bug?

Answer 1

When you get a totally unexpected result, especially with relatively simple function like this, it can be helpful to follow the logic through by hand. So let's see what happens here:

reverse' (0:[8,2,5,6,1,20,99,91,1]) = 1 : reverse' xs ==>
1 : (reverse' (8:[2,5,6,1,20,99,91,1]) = 1 : reverse' xs ==>
1 : 1 : (reverse' (2:[5,6,1,20,99,91,1]) = 1 : reverse' xs ==>
...

You can see where this is going. The problem is simple; you're just reversing the wrong part of the list in the recursive step. Instead of reversing the tail like you're doing now, you want to reverse everything but the last element. So you could revise it to something like this:

reverse' :: [b] -> [b]
reverse' [] = []
reverse' [x] = [x]
reverse' xs = last xs : reverse' (init xs)

which returns what you'd expect: reverse' [1,91,99,20,1,6,5,2,8,0] = [0,8,2,5,6,1,20,99,91,1]