[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
