Re: [Haskell-cafe] are some of these reverse algos better than others? is there a quick and dirty way to reveal this fact?
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..100] and beyond. -- fails on [1..10] on win/hugs naivereverse [] = [] naivereverse (x:xs) = naivereverse xs ++ [x] -- fails on [1..100] 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
Re: [Haskell-cafe] are some of these reverse algos better than others? is there a quick and dirty way to reveal this fact?
On 9/23/07, Lennart Augustsson [EMAIL PROTECTED] wrote: 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. Wow! I'm amazed, this function runs in exponential time! How does one actually comes to write it without smelling something wrong with those recursive calls? -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] are some of these reverse algos better than others? is there a quick and dirty way to reveal this fact?
Well, my goal when I first wrote it was to see if I could write reverse without calling any other functions. I did realize that it was really bad. :) -- Lennart On 9/23/07, Felipe Almeida Lessa [EMAIL PROTECTED] wrote: On 9/23/07, Lennart Augustsson [EMAIL PROTECTED] wrote: 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. Wow! I'm amazed, this function runs in exponential time! How does one actually comes to write it without smelling something wrong with those recursive calls? -- Felipe. ___ 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
Re: [Haskell-cafe] are some of these reverse algos better than others? is there a quick and dirty way to reveal this fact?
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..100] and beyond. -- fails on [1..10] on win/hugs naivereverse [] = [] naivereverse (x:xs) = naivereverse xs ++ [x] -- fails on [1..100] 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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] are some of these reverse algos better than others? is there a quick and dirty way to reveal this fact?
On 9/23/07, Thomas Hartman [EMAIL PROTECTED] wrote: -- this is the usual implementation right? myreverse xs = foldl f [] xs where f accum el = el : accum This is often written reverse = foldl (flip (:)) [] which I quite like, because you can contrast it with foldr (:) [] which of course is just a type-restricted version of id. Stuart ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
