using less stack

C.Reinke C.Reinke@ukc.ac.uk
Wed, 20 Mar 2002 20:32:19 +0000


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

..[explanation omitted]..

I didn't express myself well: I don't doubt that you solved your
problem by using cpsfold, but the cpsfold alone doesn't do the
trick. It just translates the implicit continuation (which uses
stack space) into an explicit continuation function (which uses 
heap space). So there's something else going on.

As you explained, having the continuation explicit makes it easier
to get a handle on what happens next at every step, which is the
usual reason for using CPS style. And if neither the cautious
evaluate-to-weak-head-normal-form seq nor the all-out
evaluate-to-normal-form deepSeq do the job for you, I can well
imagine that CPS style permits you to fine-tune evaluation to the
needs of your application. But as Olaf has pointed out, having that
much control can be a bit of a fragile construction.

So I was just wondering about the specific use of fold in your
application, and how you've redefined your operator to make use of
your CPS version of fold (in order to solve the space problem).

Incidentally, cpsfold processes the list in reversed order, which
may or may not matter, depending on the operator passed to it.

  Hugs session for:
  Prelude.hs
  R.hs
  folds.hs

  Main> foldr (-) 0 [1..4]
  (1 - (2 - (3 - (4 - 0))))

  Main> foldl (-) 0 [1..4]
  ((((0 - 1) - 2) - 3) - 4)

  Main> cpsfold (\x y c-> c $ x - y) 0 [1..4]
  (4 - (3 - (2 - (1 - 0))))


Claus

--
Research Opportunity: Refactoring Functional Programs (UKC)
Closing date: Friday 22 March 2002  <------- !!!
http://www.cs.ukc.ac.uk/vacancies_dir/r02-24.html