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

[Lennart Augustsson]

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.

  -- Lennart


On 9/23/07, Thomas Hartman <tphyahoo at gmail.com> wrote:
>
> I came up with the following functions to do "reverse." The first one
> is obviously bad, because of the expensive list concat. The last one,
> "myreverse", I think is the reference implementation you get in the
> prelude. The ones between, I'm not so sure. I suspect they're "naive"
> as the name indicates, but in practice they stop working at the same
> place as myreverse, at least on hugs.
>
> If versions "naive 2-5" are indeed inferior to myreverse, is there a
> quick and dirty way to reveal which ones are better via a profiling
> tool, or some trick like that? Something easier than doing the
> space/time complexity analysis by hand I mean?
>
> By the way, on ghc they all work out to [1..1000000] and beyond.
>
> -- fails on [1..100000] on win/hugs
> naivereverse [] = []
> naivereverse (x:xs) = naivereverse xs  ++ [x]
>
> -- fails on [1..1000000] on win/hugs
> naivereverse2 [] = []
> naivereverse2 (x:xs) = ( last xs ) : ( naivereverse2 ( init xs ) ++ [x] )
>
> naivereverse3 [] = []
> naivereverse3 ( x : xs ) = ( last xs ) : naivereverse3 ( init xs )
>
> naivereverse4 xs = myreverse' [] xs
>   where myreverse' reversed [] = reversed
>         myreverse' reversed xs = myreverse' ( (head xs) : reversed ) (
> tail xs )
>
> naivereverse5 xs = myreverse' [] xs
>   where myreverse' reversed [] = reversed
>         myreverse' reversed (x:xs) = myreverse' ( x : reversed ) xs
>
> -- this is the usual implementation right?
> myreverse xs = foldl f [] xs
>   where f accum el = el : accum
>
> t.
> _______________________________________________
> 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/807cdb20/attachment.htm