using less stack
Wed, 20 Mar 2002 18:45:15 +0000
> 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
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.