using less stack

C.Reinke [email protected]
Wed, 20 Mar 2002 18:12:12 +0000


> >  > cpsfold f a [] 
> >  > cpsfold f a (x:xs)  x a (\y -> cpsfold f y xs)
> > 
> > and f takes a continuation, Bob's my uncle, and I have a program that 
> > runs quickly in constant space!
> 
> Good.  I'm curious to know from other readers whether
> continuations like this are the only way of solving it,
> though.

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?-).

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

or, with the recently suggested idiom for strictness, tracing and
other annotations:-)

  annotation = undefined
  strict a   = seq a False

  foldl' f a l      | strict a = annotation
  foldl' f a []     = a
  foldl' f a (x:xs) = foldl' f (f a x) xs

Claus