[Haskell-cafe] Re: A guess on stack-overflows - thunks build-up andtail recursion

[Claus Reinke]

>I wonder if I could write some sort of "chunked fold" which basically 
>still produces the same amount of thunks but in a way so that the do not 
>go on the stack all at once for reduction and thus do not cause a stack 
>overflow. Kind of a tree.

Not without re-associating the applications of the operation being folded.
It is the association of everything to one side, for a strict operation, that 
leads to an expression whose evaluation will run out of limited stack,
while storing the arguments not yet used on the other side.

If your operation is associative, you could unroll the recursion a few steps
and reassociate, thereby reducing the depth of the stack of left-overs by 
the factor of unrolling. Or you could try building a tree of applications, 
perhaps from the bottom up:

import Debug.Observe

foldr2 op n (a:b:t) = (a`op`b) `op` foldr2 op n t
foldr2 op n [a]     = a `op` n
foldr2 op n []      = n

foldl2 op n (a:b:t) = foldl2 op (n`op`(a`op`b)) t
foldl2 op n [a]     = n `op` a
foldl2 op n []      = n

foldlt op n []  = n
foldlt op n [a] = n `op` a
foldlt op n l   = foldlt op n (pairs l)
  where pairs []      = []
        pairs [a]     = [a]
        pairs (a:b:t) = (a `op` b) : pairs t

main = 
  -- printO $ observe "foldl2" foldl2 (+) 0 [1..10::Int]
  -- printO $ observe "foldr2" foldr2 (+) 0 [1..10::Int]
  printO $ observe "foldlt" foldlt (+) 0 [1..10::Int]

That works somewhat better for foldl2 than for foldr2 (why?), and 
foldlt holds out the longest (is it possible to write a foldrt?), but isn't 
all that efficient:

*Main> foldl (+) 0 [1..500000::Int]
446198416
*Main> foldl (+) 0 [1..600000::Int]
*** Exception: stack overflow
*Main> foldl2 (+) 0 [1..600000::Int]
-388326432
*Main> foldl2 (+) 0 [1..1000000::Int]
1784293664
*Main> foldl2 (+) 0 [1..1100000::Int]
*** Exception: stack overflow

*Main> foldr (+) 0 [1..500000::Int]
446198416
*Main> foldr (+) 0 [1..600000::Int]
*** Exception: stack overflow
*Main> foldr2 (+) 0 [1..600000::Int]
-388326432
*Main> foldr2 (+) 0 [1..700000::Int]
*** Exception: stack overflow

These versions still have their issues, as observation on small lists
shows, so you might want to experiment with your own variations;-)

Claus