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 <[EMAIL PROTECTED]> 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 >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe