I have stack problems: my program uses too much stack. I suspect, from removing bits of code, that it's due to a foldr in my program. If I use foldr or foldl on a long list (eg >500 bulky elements for a 3M stack), is this likely to be filling the stack? What is it that gets stored on the stack? If so, is there an obvious refactoring of the fold to use? Amanda -- Amanda Clare http://users.aber.ac.uk/ajc99/ Tel: +44 (0)1970 621787 Fax: +44 (0)1970 622455 Dept. of Computer Science, University of Wales, Aberystwyth, SY23 3DB
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, from removing bits of code, that it's due to a foldr in my program. If I use foldr or foldl on a long list (eg >500 bulky elements for a 3M stack), is this likely to be filling the stack? What is it that gets stored on the stack? If so, is there an obvious refactoring of the fold to use?
Amanda
-- Amanda Clare http://users.aber.ac.uk/ajc99/ Tel: +44 (0)1970 621787 Fax: +44 (0)1970 622455 Dept. of Computer Science, University of Wales, Aberystwyth, SY23 3DB
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
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, from removing bits of code, that it's due to a foldr in my program. If I use 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ón -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk 31 Chalmers Road jf@cl.cam.ac.uk Cambridge CB1 3SZ +44 1223 570179 (after 14:00 only, please!)
Thanks for all the advice. In the end, I couldn't make $! work for me (it always seems to be harder than I think it will be to use it, and $! and deepSeq makes my code run slowly). But a continuation passing style foldl worked wonderfully. I now have:
cpsfold f a [] = a cpsfold f a (x:xs) = f 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! Amanda -- Amanda Clare http://users.aber.ac.uk/ajc99/ Tel: +44 (0)1970 621787 Fax: +44 (0)1970 622455 Dept. of Computer Science, University of Wales, Aberystwyth, SY23 3DB
Thanks for all the advice. In the end, I couldn't make $! work for me (it always seems to be harder than I think it will be to use it, and $! and deepSeq makes my code run slowly).
:-(
But a continuation passing style foldl worked wonderfully.
As Jay Cox pointed out by email, my answer was rot because I had confused foldl and foldr
I now have:
cpsfold f a [] = a cpsfold f a (x:xs) = f 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. Jón -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk 31 Chalmers Road jf@cl.cam.ac.uk Cambridge CB1 3SZ +44 1223 570179 (after 14:00 only, please!)
participants (2)
-
Amanda Clare -
Jon Fairbairn