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

Thomas Hartman tphyahoo at gmail.com
Sun Sep 23 00:14:45 EDT 2007


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.


More information about the Haskell-Cafe mailing list