On Mon, Aug 20, 2007 at 11:21:01AM -0500, Lanny Ripple wrote: > Not really more efficient but plays to the language implementation's > strengths. > > Imagine > > take 10 $ foo (10^9) > > and > > take 10 $ bar (10^9) > > bar wouldn't evaluate until the 10^9 was done. (And I just ground my > laptop to a halt checking that. :) foo on the other hand would run out to > 10^6 and then conveniently finish the rest of your program waiting for the > need of the other 10^9-10 values. If you *always* needed the result of the > 10^9 calculations then tail-recursion should be better since you won't be > holding onto the evaluation frames.
Even if you did, in the presense of laziness it's not useful to make
list producers tail recursive. Consider:
sum = sum' 0
sum' k [] = k
sum' k (x:xs) = (sum' $! (k+x)) xs
enum x y | x >= y = 0
| otherwise = x : enum (x+1) y
sum (enum 1 10) =>
sum' 0 (enum 1 10) =>
sum' 0 (1 : enum (1+1) 10) =>
(sum' $! (0+1)) (enum (1+1) 10) =>
sum' 1 (enum (1+1) 10) =>
sum' 1 (2 : enum (2+1) 10) =>
(sum' $! (1+2)) (enum (2+1) 10) =>
sum' 3 (enum (2+1) 10) =>
sum' 3 (3 : enum (3+1) 10) =>
(sum' $! (3+3)) (enum (3+1) 10) =>
sum' 6 (enum (3+1) 10) =>
sum' 6 (4 : enum (4+1) 10) =>
(sum' $! (6+4)) (enum (4+1) 10) =>
sum' 10 (enum (4+1) 10) =>
...
sum' 36 (9 : enum (9+1) 10) =>
(sum' $! (36+9)) (enum (9+1) 10) =>
sum' 45 (enum (9+1) 10) =>
sum' 45 [] =>
45
(I need to find some way to automate making these trails :) )
It runs in constant space, despite the producer's non-tail-recursion.
Stefan
signature.asc
Description: Digital signature
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
