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

On 9/23/07, Lennart Augustsson 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.