# Stack usage with a state monad

Graham Klyne gk at ninebynine.org
Wed Dec 31 14:38:06 EST 2003

```At 12:36 31/12/03 +0000, Joe Thornber wrote:
>On Wed, Dec 31, 2003 at 11:54:27AM +0000, 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
> >
> > 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

```