Re: [Haskell-beginners] Re: pattern for tree traversel with a state

Brent Yorgey wrote:

On Thu, Oct 23, 2008 at 11:47:43PM +0100, Jan Jakubuv wrote:

...

2008/10/23 Andreas-Christoph Bernstein :

...

apfelmus wrote:

But what i need is [(0,"a"),(1,"a"),(2,"a"),(1,"a"),(0,"a")]

So state changes should affect only their subtree, not the rest of the tree to the right.

It seems to me that you are looking for the Reader monad. Try the following:

import Control.Monad.Reader

t :: (a -> b -> b) -> BTree a -> Reader b (BTree b) t f (Leaf x) = do s <- ask return (Leaf (f x s)) t f (Fork x l r) = do s <- ask l' <- local (f x) (t f l) r' <- local (f x) (t f r) return (Fork (f x s) l' r')

new = runReader (t modState sampleTree) globalState

Then,

flattenTree new

gives you

[(0,"a"),(1,"a"),(2,"a"),(1,"a"),(0,"a")]

I think that the Reader monad is a standard way to this. When you want the state to affect also the rest of the tree then use the State monad.

Just to elaborate on Jan's code, the Reader monad represents an *immutable* state---that is, a read-only "environment" that gets threaded through your computation which you can access at any time (using "ask"). However, using the "local" function, you can run subcomputations within a different environment, obtained by applying some function to the current environment. So this does exactly what you want---after the subcomputation is finished, its locally defined environment goes out of scope and you are back to the original environment. Using the Reader monad in this way is a common idiom for representing recursive algorithms with state that can change on the way down the call stack, but "unwinds" as you come back up, so recursive calls can only affect recursive calls below them, not ones that come afterwards.

-Brent

That is what i was looking for. Thank you all very much for your help. Kind regards, Andreas