Stack usage with a state monad
Graham Klyne
GK at ninebynine.org
Wed Dec 31 11:54:27 EST 2003
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
More information about the Haskell-Cafe
mailing list