Stack usage with a state monad

[Graham Klyne]

I've read 4 messages following this, but I'd like to pursue this a little 
to test my own understanding...

At 14:12 30/12/03 +0000, Joe Thornber wrote:
>I was wondering if anyone could give me some help with this problem ?
>
>I'm trying to hold some state in a StateMonad whilst I iterate over a
>large tree, and finding that I'm running out of stack space very
>quickly.  The simplified program below exhibits the same problem.

[...]

>module Main (main) where
>
>-- Program to count the leaf nodes in a rose tree.  Written to try and
>-- reproduce a stack space leak present in a larger program.
>
>-- How can I use a state monad to count the leaves without eating all
>-- the stack ?
>
>import Control.Monad.State
>
>data Tree = Tree [Tree] | Leaf
>
>buildTree :: Int -> Int -> Tree
>buildTree order = buildTree'
>     where
>     buildTree' 0 = Leaf
>     buildTree' depth = Tree $ map (buildTree') $ take order $ repeat 
> (depth - 1)
>
>countLeaves1 :: Tree -> Int
>countLeaves1 (Tree xs) = sum $ map (countLeaves1) xs
>countLeaves1 (Leaf) = 1
>
>incCount :: State Int ()
>incCount = do {c <- get;
>                put (c + 1);
>                return ();
>               }
>
>countLeaves2   :: Tree -> Int
>countLeaves2 t = execState (aux t) 0
>     where
>     aux :: Tree -> State Int ()
>     aux (Tree xs) = foldr1 (>>) $ map (aux) xs
>     aux (Leaf) = incCount
>
>main :: IO ()B
>main = print $ countLeaves2 $ buildTree 15 6

My *intuition* here is that the problem is with countLeaves2, in that it 
must build the computation for the given [sub]tree before it can start to 
evaluate it.  Maybe this is why other responses talk about changing the 
state monad?

But why does this computation have be done in a state monad at 
all?  countLeaves seems to me to be a pretty straightforward function from 
a Tree to an Int, with no need for intervening state other than to 
increment a counter:  as such, I'd have expected a simple recursive 
function to serve the purpose.  (Maybe there was something in the original 
application that was lost in the problem isolation?)

#g


------------
Graham Klyne
For email:
http://www.ninebynine.org/#Contact