CODEWITHSUNDEEP
listhaskellreverse
TommyQ
TommyQ

Reputation: 511

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?

Upvotes: 8

Views: 8305

Answers (5)

neoplay
neoplay

Reputation: 29

reverse2 :: [a] -> [a]
reverse2 [] = []
reverse2 [x] = [x]
reverse2 x = (last x) : (reverse2 (init x))

Upvotes: 0

Landei
Landei

Reputation: 54584

While playing around with Data.Monoid I found the following alternative, slightly rube-goldbergish solution:

import Data.Foldable
import Data.Monoid

reverse = getDual . foldMap (Dual . (:[]))

Upvotes: 2

Will Ness
Will Ness

Reputation: 71065

The minimal correction to your original code is arguably 

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

i.e. you were combining your list's sub-parts in a wrong order.

This is of course still a quadratic algorithm. You get an iterative version out of it by first observing

reverse' (a:b:c:d:xs) = (((reverse' xs ++ [d]) ++ [c]) ++ [b]) ++ [a]

and then regrouping and keeping thus formed intermediate results in a separate, accumulator argument, as was pointed out in a previous response:

rev (x:xs) acc = rev xs (x:acc)

Having found your workhorse, you set it up with an appropriate interface,

reverse' xs = rev xs []

(plus few edge cases).

Upvotes: 6

Landei
Landei

Reputation: 54584

As others already pointed out the mistake, let me show you a useful and elegant technique which can be often applied in such cases and leads often to efficient algorithms: Use an accumulator.

rev xs = rev' xs [] where
  rev' [] acc = acc
  rev' (x:xs) acc = rev' xs (x:acc)

So you have a sub-function with an additional argument (the "accumulator") which collects what you already have. Obviously in the base case you need to give this result back, because you are done. The recursive case is very simple here: It's just like having a stack of plates, which you take one by one from the top, and build a new stack by adding one by one at the top. This resulting stack is reversed, just like we need it.

Note that for some other applications of this technique you don't want that reversion, which can be fixed by inserting a reverse in the base case.

Upvotes: 10

Jeff Burka
Jeff Burka

Reputation: 2571

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]

Upvotes: 18

Related Questions