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

[Lennart Augustsson]

Well, my goal when I first wrote it was to see if I could write reverse
without calling any other functions.
I did realize that it was really bad. :)

  -- Lennart

On 9/23/07, Felipe Almeida Lessa <felipe.lessa at gmail.com> wrote:
>
> 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.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070923/8d89d18b/attachment.htm