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" <[EMAIL PROTECTED]> To: "C.Reinke" <[EMAIL PROTECTED]> Cc: <[EMAIL PROTECTED]> 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 > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell > _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
