You don't have to define cpsfold explicitly recursively since it can be expressed in terms of foldr: cpsfold f a xs = foldr (\x k y -> f x y k) id xs a The following definition would even be better (but not equivalent): cpsfold' f a xs = foldr (\x k y -> f y x k) id xs a The list members are now 'consumed' left-to-right by f, with initial value a. So, answer4 = foldr (\x k a -> if x > a then k x else k a) id [1..500000] 0 also works without a crash or insufficient stack space. Gertjan ----- Original Message ----- From: "Amanda Clare" <ajc99@aber.ac.uk> To: "C.Reinke" <C.Reinke@ukc.ac.uk> Cc: <haskell@haskell.org> Sent: Wednesday, March 20, 2002 7:45 PM Subject: Re: using less stack
[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
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell