using less stack

[Gertjan Kamsteeg]

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
>