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