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