using less stack

Jon Fairbairn
Mon, 18 Mar 2002 19:14:16 +0000

> Apologies for the typo: that should have been 50000 elements, not 500.
> =

> Amanda Clare wrote:
> > I have stack problems: my program uses too much stack. I suspect, fro=
m =

> > removing bits of code, that it's due to a foldr in my program. If I u=
se =

> > foldr or foldl on a long list (eg >500 bulky elements for a 3M stack)=
, =

> > is this likely to be filling the stack?

The fold itself won't be filling the stack. Without seeing
some of the code it's hard to tell, but the most common
cause of this sort of problem is a lack of strictness.

foldr (+) 0 [0..5000]

doesn't use up stack for the fold, but it builds a
suspension for all 5000 additions, and evaluating that
/does/ use stack unless the compiler has spotted that (+) is
strict. (What compiler/interpreter are you using?)

> > What is it that gets stored on =

> > the stack? If so, is there an obvious refactoring of the fold to use?=

The solution is to stick in $! judiciously and use foldr'
(which seems to have got dropped from the standard libraries
at some point, so you'll have to write your own) that uses


-- =

J=F3n Fairbairn                       
31 Chalmers Road                               
Cambridge CB1 3SZ            +44 1223 570179 (after 14:00 only, please!)