[Haskell-cafe] are some of these "reverse" algos better than others? is there a quick and dirty way to reveal this fact?

[Felipe Almeida Lessa]

On 9/23/07, Lennart Augustsson <lennart at augustsson.net> wrote:
> If we're discussing bad versions of reverse, don't forget this one:
>
> rev [] = []
> rev (x:xs) =
>     case rev xs of
>     [] -> [x]
>     y:ys -> y : rev (x : rev ys)
>
> It's different from most versions of reverse because it doesn't use any
> auxiliarry functions.
> It's also extremely inefficient.

Wow! I'm amazed, this function runs in exponential time! How does one
actually comes to write it without smelling something wrong with those
recursive calls?

-- 
Felipe.