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

[Andreas-Christoph Bernstein]

Brent Yorgey wrote:
> 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
>   

That is what i was looking for. Thank you all very much for your help.

Kind regards,
Andreas