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@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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe