Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Unexpected result while reversing a list

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?

like image 687
TommyQ Avatar asked Nov 14 '11 03:11

TommyQ


1 Answers

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]

like image 166
Jeff Burka Avatar answered Sep 19 '22 16:09

Jeff Burka