using less stack

[Amanda Clare]

[cpsfold omitted]

> Actually, and quite apart from it being cumbersome to use, I've got
> my doubts about whether this cpsfold really does the job (is that
> just me missing some point?-).

It does the job for me! In practical terms I can see it works. I'm not 
an expert - I may have this all wrong, but perhaps the point you're 
looking for is that the arguments to f are brought to the very outside 
of the expression, and hence available for evaluation. Imagine for 
[x1,x2,x3,x4]
from foldr:  f x1 (f x2 (f x3 (f x4 a)))
from foldl:  f (f (f (f a x1) x2) x3) x4

Neither are available for immediate evaluation. In the case of foldr the 
end of the list (x4) has to be reached before anything can be evaluated. 
In the case of foldl the first function to be pulled upon is the 
outermost f, which then can't do anything useful (in my case) without 
evaluating its second argument, and so on.

with the cpsfold I get

f x1 a (\y1 -> f x2 y1 (\y2 -> f x3 y3 (\y3 -> f x4 y4 (\y4 -> y4)

so x1 and a are available immediately for f to use, and f x1 a is the 
outermost expression so will be evaluated first.

See for yourself with the following (difference can be seen in ghc with 
standard 1M stack):

 > answer1 = foldr larger 0 [1..500000]
 > answer2 = foldl larger 0 [1..500000]
 > answer3 = cpsfold cpslarger 0 [1..500000]

 > larger    x y   = if x > y then x   else y
 > cpslarger x y k = if x > y then k x else k y



> Also, I'm curious to know why the usual strict variant of foldl
> doesn't help in this case?
> 
>   foldl' f a []     = a
>   foldl' f a (x:xs) = (foldl' f $! f a x) xs

Because $! and seq only evaluates enough to make sure the answer is not 
bottom, and if my f is complex then it doesn't do enough.

Amanda