[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 felipe.lessa at gmail.com
Sun Sep 23 07:30:38 EDT 2007

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?


More information about the Haskell-Cafe mailing list