Stack usage with a state monad

[Graham Klyne]

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
> > 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