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
_______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
