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.

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