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

[Derek Elkins]

On Sat, 2007-09-22 at 21:14 -0700, Thomas Hartman 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

4 and 5 are equivalent to myreverse, 3 is inferior. 2 isn't even doing
the same thing.  The easiest and most generalizable way to see that 3 is
bad, -is- time complexity analysis, but just what should be an
instantaneous one: last (and init) are O(n) and are being done each
recursion.  It -should- be immediately obvious to you that last and init
must be O(n) and that that implies version 3 is O(n^2).  At any rate,
usually you don't pick from a variety of implementations, you build one
and you aim for efficiency by construction.

The most important first difference between the first version and
myreverse is the fact that myreverse is written in tail recursive form
and naivereverse is not.  Tail calls are easily syntactically
identifiable.  However, in a lazy language, there is more to that
particular story than normal.  See
http://www.haskell.org/haskellwiki/Stack_overflow for some explanation
about that.