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

[Brent Yorgey]

On Thu, Oct 23, 2008 at 11:47:43PM +0100, Jan Jakubuv wrote:
> 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.

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