[Haskell-cafe] Newbie question: Where is StackOverflow on the Wiki?

[Stefan O'Rear]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070820/4eb5bb86/attachment.bin