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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
