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
Type checking
Hi, Can anyone explain to me how hugs manages to derive that f x y z = y (y z) x is of type f :: a - ((a - b) - a - b) - (a - b) - b Many thanks and a happy new year to all! Lee _ Stay in touch with absent friends - get MSN Messenger http://www.msn.co.uk/messenger ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Type checking
On 2003-12-31 at 19:27GMT Lee Dixon wrote: Hi, Can anyone explain to me how hugs manages to derive that f x y z = y (y z) x is of type f :: a - ((a - b) - a - b) - (a - b) - b To begin with, f has three arguments, x y and z, so letting each of these have types Tx Ty and Tz, f has to have type Tx - Ty - Tz - R, for some R. We see that y is applied to z, so y must have type Tz - Ry: f:: Tx - (Tz - Ry) - Tz - R but y is also applied to (y z) and x. (y z):: Ry, so y must also have type Ry - Tx - R since R is the type of the body of f. so we need to find a type that has instances Tz - Ry and Ry - Tx - R putting Ry = (a - b), we want Tz - (a - b) to be the same as (a - b) - Tx - R, which it is if Tz = (a - b), Tx = a and R = b. ie Ty = (a - b) - a - b. So substitute all those in the first guess for the type of f we get a - ((a - b) - a - b) - (a - b) - b | ---|------|| |Tz Tz | |-|--| TxTy R You want to look up unification and Hindley-Milner type inference. Does that help? Jón -- Jón Fairbairn [EMAIL PROTECTED] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Monads
Omitting the typeclass bit, I'm trying to write something like (s1 - s2) - StateT s1 m () - StateT s2 m a - StateT s1 m a That is, it sequences two StateT computations, providing a way to translate from the first's state to the second to keep the chain going. I can easily write something for when s1 and s2 are the same, and my understanding of much of Control.Monad.* remains tenuous at best, but if it's easy for anyone to provide me with some tips, then I thought I should mention that it'd certainly be helpful. And Happy New Year, everyone! -- Mark ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Parsec question
I tried posting this before but, from my point of view, it vanished. My
apologies if it's a duplicate.
In http://www.cs.uu.nl/~daan/download/parsec/parsec.html we read,
testOr2 = try (string (a))
| string (b)
or an even better version:
testOr3 = do{ try (string (a); char ')'; return (a) }
| string (b)
Why is the latter better?
(BTW, I like Parsec. Thanks, Daan. (-:)
-- Mark
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Monads
Mark, I'm no expert, but does it help to start from withStateT? withStateT :: (s - s) - StateT s m a - StateT s m a withStateT f m = StateT $ runStateT m . f There are some notes about computations and lifting state transformers in Modular Denotational Semantics for Compiler Construction Sheng Liang, Paul Hudak http://citeseer.nj.nec.com/liang96modular.html Monad Transformers and Modular Interpreters Sheng Liang, Paul Hudak, Mark Jones http://citeseer.nj.nec.com/liang95monad.html Don't mind me: I just couldn't control the vestiges of librarianship lurking in my dark, lost soul... Dobrego Nowego Roku! Chris Milton (no, not MLton:-) --- Mark Carroll [EMAIL PROTECTED] wrote: Omitting the typeclass bit, I'm trying to write something like (s1 - s2) - StateT s1 m () - StateT s2 m a - StateT s1 m a That is, it sequences two StateT computations, providing a way to translate from the first's state to the second to keep the chain going. I can easily write something for when s1 and s2 are the same, and my understanding of much of Control.Monad.* remains tenuous at best, but if it's easy for anyone to provide me with some tips, then I thought I should mention that it'd certainly be helpful. And Happy New Year, everyone! -- Mark ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Monads
Mark Carroll [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: Omitting the typeclass bit, I'm trying to write something like (s1 - s2) - StateT s1 m () - StateT s2 m a - StateT s1 m a That is, it sequences two StateT computations, providing a way to translate from the first's state to the second to keep the chain going. Don't you need a (s2 - s1) function as well, to translate the final state back into StateT s1? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig GW Bush: And when leaders make the wise and responsible choice, when they renounce terror and weapons of mass destruction, as Col. Ghadafi has now done, they serve the interest of their own people and they add to the security of all nations. http://www.tmealf.com/survey_form.htm ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Monads
On Wed, 31 Dec 2003, Ken Shan wrote: Don't you need a (s2 - s1) function as well, to translate the final state back into StateT s1? Yes, you're right: the thing actually running the stateful computation presumably expects to start it with a state of type s1 and to be able to extract from it a state of type s1 when it's done. -- Mark ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
