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