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

[Jan Jakubuv]

2008/10/23 Andreas-Christoph Bernstein <andreas.bernstein at medien.uni-weimar.de>:
> 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.

Sincerely,
 jan.