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
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