Fwd: [Haskell-cafe] curious about sum

[Alberto G. Corona]

Once more I forgot to send my messages to the haskell cafe list. All the
rest of the list which I´m suscribed to, send  the mail replies to the list
automatically, but this doesn´t. Please, can this be changed?.

---------- Forwarded message ----------
From: Alberto G. Corona <agocorona at gmail.com>
Date: 2009/6/13
Subject: Re: [Haskell-cafe] curious about sum
To: Deniz Dogan <deniz.a.m.dogan at gmail.com>


first, I was completely wrong. It is foldl what is neccesary. sum is
defined in terms of foldl:

sum= foldl (+) 0

but
Prelude> foldl (+)  0 [1..1000000]
*** Exception: stack overflow

that is not because + is non strict, but because foldl is:

foldl f z0 xs0 = lgo z0 xs0
            where
               lgo z []     =  z
               lgo z (x:xs) = lgo (f z x) xs

this version of foldl IS strict:

foldlStrict f z0 xs0 = lgo z0 xs0
            where
               lgo z []     =  z
               lgo z (x:xs) =let t= f z x in t `seq` lgo t xs

main= print $  foldlStrict (+) 0 [1..1000000]
500000500000

so the garbage collector do the job in freeing the consumed part of the
list.

2009/6/13 Alberto G. Corona <agocorona at gmail.com>
>
> Prelude> let strictplus x y= let z=x +y in z `seq` z; sum1= foldr
 strictplus 0 in sum1[0..1000000]
> *** Exception: stack overflow
> I suppose that strictplus is strict, so the garbage collector would free
the consumed part of the list.
> Then, why the stack overflow?
> 2009/6/13 Deniz Dogan <deniz.a.m.dogan at gmail.com>
>>
>> 2009/6/13 Jochem Berndsen <jochem at functor.nl>:
>> > Keith Sheppard wrote:
>> >> Is there any reason that sum isn't strict? I can't think of any case
>> >> where that is a good thing.
>> >>
>> >> Prelude> sum [0 .. 1000000]
>> >> *** Exception: stack overflow
>> >
>> > It is useful if the (+) is nonstrict; although I cannot think of any
>> > useful mathematical structure where (+) would be nonstrict.
>>
>> I remember needing a non-strict sum at least once, but I do not
>> remember the exact application. But imagine having a (very) long list
>> of numbers and you want to do A if the sum exceeds a small number,
>> otherwise B.
>>
>> if sum [0..100000] > 10 then A else B
>>
>> However, this idea didn't work, because of strictness.
>>
>> --
>> Deniz Dogan
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090614/7ced6adb/attachment-0001.html