Re: Stack usage with a state monad
At 15:37 31/12/03 +, Joe Thornber wrote:
On Wed, Dec 31, 2003 at 02:38:06PM +, Graham Klyne wrote:
getOrCachePositionValue pos =
do { mcache - gets (findPos pos) -- Query cache for position
; case mcache of
Just cached - return (cachedVal cached) -- Return cached value
Nothing --- Not in cache:
do { let val = calculatePosVal pos -- Calculate new value
; modify (addToCache pos val) -- Cache new value
; return val-- Return new value
}
}
(This code of off-the-cuff, and may contain errors)
My point is that the function 'calculatePosVal' used here to evaluate a
position not in the cache simply returns the calculated value, not a
monad. This function is wrapped in high level code that queries and/or
updates the cache which is kept in a state monad. Thus, the return
type of
'getOrCachePositionValue' would be a monad of the appropriate type.
But I want calculatePosVal to use the cache too :(
Well, maybe you really do need to run your calculation in the state monad,
but I'll ask one more question: to you need your 'calculatePosVal' to
*use* the cache, or to *update* it? If you simply need access to the
cache, then the function could accept cache data extracted from the state
monad as an additional argument; e.g.
getOrCachePositionValue pos =
do { cacheState - get -- Get current cache state
; let mcache = findPos pos cacheState -- Query cache for position
; case mcache of
Just cached - return (cachedVal cached) -- Return cached value
Nothing --- Not in cache:
do { let val = calculatePosVal pos cacheState
-- Calculate new value
; modify (addToCache pos val) -- Cache new value
; return val-- Return new value
}
}
If your calculation really needs to update the cache state as it goes
along, then I agree that it needs to be run in the state monad. But even
then, I'd be inclined to look for sub-calculations that can be evaluated as
ordinary functions.
Anyway, I think I've probably added enough noise to this debate. Whatever
approach you may use, have fun!
#g
Graham Klyne
For email:
http://www.ninebynine.org/#Contact
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Stack usage with a state monad
On Fri, Jan 02, 2004 at 02:46:04PM +, Graham Klyne wrote: If your calculation really needs to update the cache state as it goes along, then I agree that it needs to be run in the state monad. But even then, I'd be inclined to look for sub-calculations that can be evaluated as ordinary functions. I think I do need to update the cache state, though I do think I could still split the function into 2 mutually recursive functions (both returning the state monad) as you suggest, which would at least make the code clearer. Anyway, I think I've probably added enough noise to this debate. Whatever approach you may use, have fun! Thanks for your help. - Joe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Stack usage with a state monad
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 +, 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
Re: Stack usage with a state monad
On Wed, Dec 31, 2003 at 11:54:27AM +, Graham Klyne wrote: 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?) I think you might well be correct that I'm doing things the wrong way. The original program is a chess prog. and the function in question is the alphabeta search. I wanted to hold the transposition table (a cache of seen positions) among other things in the state monad. I thought this was the normal way to approach this, but am having doubts now. The recursive approach will indeed work, but I had hoped to avoid all the code associated with threading the state by hand. - Joe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Stack usage with a state monad
At 12:36 31/12/03 +, Joe Thornber wrote:
On Wed, Dec 31, 2003 at 11:54:27AM +, Graham Klyne wrote:
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?)
I think you might well be correct that I'm doing things the wrong way.
The original program is a chess prog. and the function in question is
the alphabeta search. I wanted to hold the transposition table (a
cache of seen positions) among other things in the state monad. I
thought this was the normal way to approach this, but am having doubts
now. The recursive approach will indeed work, but I had hoped to
avoid all the code associated with threading the state by hand.
I didn't mean to suggest that you avoid using a state monad
altogether. The idea of keeping seen positions certainly seems to me like
a job for a state monad. I just wonder if it's necessary to use the state
monad (or to update the state monad) when doing a simple calculation like
counting the leaves, or evaluating a position.
I've been using Haskell for just a few months now (i.e. I'm not an old
hand) and find that my own code I use a state monad to keep just that
which needs to be kept, and use normal functions for transient results.
If I speculate a little... you have a cache of previously evaluated
positions and associated scores. You are given a new position and wish to
calculate its score, using previous results where possible. Then I would
anticipate something like:
getOrCachePositionValue pos =
do { mcache - gets (findPos pos) -- Query cache for position
; case mcache of
Just cached - return (cachedVal cached) -- Return cached value
Nothing --- Not in cache:
do { let val = calculatePosVal pos -- Calculate new value
; modify (addToCache pos val) -- Cache new value
; return val-- Return new value
}
}
(This code of off-the-cuff, and may contain errors)
My point is that the function 'calculatePosVal' used here to evaluate a
position not in the cache simply returns the calculated value, not a
monad. This function is wrapped in high level code that queries and/or
updates the cache which is kept in a state monad. Thus, the return type of
'getOrCachePositionValue' would be a monad of the appropriate type.
#g
Graham Klyne
For email:
http://www.ninebynine.org/#Contact
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Stack usage with a state monad
On Wed, Dec 31, 2003 at 02:38:06PM +, Graham Klyne wrote:
getOrCachePositionValue pos =
do { mcache - gets (findPos pos) -- Query cache for position
; case mcache of
Just cached - return (cachedVal cached) -- Return cached value
Nothing --- Not in cache:
do { let val = calculatePosVal pos -- Calculate new value
; modify (addToCache pos val) -- Cache new value
; return val-- Return new value
}
}
(This code of off-the-cuff, and may contain errors)
My point is that the function 'calculatePosVal' used here to evaluate a
position not in the cache simply returns the calculated value, not a
monad. This function is wrapped in high level code that queries and/or
updates the cache which is kept in a state monad. Thus, the return type of
'getOrCachePositionValue' would be a monad of the appropriate type.
But I want calculatePosVal to use the cache too :(
- Joe
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Stack usage with a state monad
On Tue, Dec 30, 2003 at 02:12:15PM +, Joe Thornber wrote:
Hi,
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.
If you are using Hugs, try compiling your program with GHC (with -O2).
With GHC it seems to work, but it is still rather slow. After 4 minutes
of waiting a killed the process.
Correction: I had an environment option GHCRTS=-K64M, so it just took
more time before the stack exhausted.
I've optimised you program a bit and now it completes after 4 seconds
using only 2 megabytes of memory. After adding strictness annotations,
increasing sharing in the tree generated by buildTree the program still
was quite resource hungry, so I tried using an unboxed tuple (GHC's
extension) in the state monad - it helped a lot.
I am sorry, if I only confused you. My english is not great and time is
running. Got to go :)
Best regards,
Tom
{-# OPTIONS -fglasgow-exts #-}
module Main (module 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
newtype UnboxedState s a = UnboxedState { runUnboxedState :: s - (# a, s #) }
instance Monad (UnboxedState s) where
return a = UnboxedState $ \s - (# a, s #)
m = k = UnboxedState $ \s -
case runUnboxedState m s of
(# a, s' #) - runUnboxedState (k a) s'
instance MonadState s (UnboxedState s) where
get = UnboxedState $ \s - (# s, s #)
put s = UnboxedState $ \_ - (# (), s #)
execUnboxedState m s = case runUnboxedState m s of
(# _, s' #) - s'
data Tree = Tree [Tree] | Leaf
buildTree :: Int - Int - Tree
buildTree order depth =
head $ drop depth $ iterate (\t - Tree (replicate order t)) Leaf
countLeaves1 :: Tree - Int
countLeaves1 (Tree xs) = sum $ map (countLeaves1) xs
countLeaves1 (Leaf) = 1
incCount :: UnboxedState Int ()
incCount = do {c - get;
put $! (c + 1);
}
countLeaves2 :: Tree - Int
countLeaves2 t = execUnboxedState (aux t) 0
where
aux (Tree xs) = mapM_ aux xs
aux (Leaf) = incCount
main :: IO ()
main = print $ countLeaves2 $ buildTree 15 6
--
.signature: Too many levels of symbolic links
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Stack usage with a state monad
Hi, I think the problem is in the State Monad itself; State Monad is lazy to compute its state. I am not a haskell expert, and there may be better ideas. But anyhow, when I use these = and instead of = and , your example runs fine. I hope it becomes some help. m = k = State $ \s - let (a, s') = runState m s in s `seq` runState (k a) s' -- force evaluation of the state m k = m = \_ - k -- Koji Nakahara ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Stack usage with a state monad
On Wed, Dec 31, 2003 at 02:54:18AM +0900, Koji Nakahara wrote: Hi, I think the problem is in the State Monad itself; State Monad is lazy to compute its state. I am not a haskell expert, and there may be better ideas. But anyhow, when I use these = and instead of = and , your example runs fine. I hope it becomes some help. m = k = State $ \s - let (a, s') = runState m s in s `seq` runState (k a) s' -- force evaluation of the state m k = m = \_ - k Ahh, right. So I didn't have to use UnboxedState. StrictState would do. Best regards, Tom -- .signature: Too many levels of symbolic links ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Stack usage with a state monad
On Tue, Dec 30, 2003 at 08:28:11PM +0100, Tomasz Zielonka wrote: On Wed, Dec 31, 2003 at 02:54:18AM +0900, Koji Nakahara wrote: Hi, I think the problem is in the State Monad itself; State Monad is lazy to compute its state. I am not a haskell expert, and there may be better ideas. But anyhow, when I use these = and instead of = and , your example runs fine. I hope it becomes some help. m = k = State $ \s - let (a, s') = runState m s in s `seq` runState (k a) s' -- force evaluation of the state m k = m = \_ - k Ahh, right. So I didn't have to use UnboxedState. StrictState would do. Thankyou both for your help, I wouldn't have thought of changing the State monad itself. I guess I've got lots more to learn :) - Joe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
