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

[Andreas-Christoph Bernstein]

apfelmus wrote:
> Andreas-Christoph Bernstein wrote:
>  
>> Is there a pattern for tree traversal with a state ?
>>
>> I am developing a small scenegraph represented by a tree. To draw a
>> scenegraph one traverses over the graph starting with a global state.
>> Inner Nodes can overwrite the inherited state for their subtree (e.g.
>> Transformations are accumulated). The accumulated state is then either
>> used immediately to draw the geometry in the leaf nodes, or a secondary
>> data structure is build. This secondary data structure (a list or a
>> tree) can then be sorted for optimal drawing performance.
>>
>> So i want to do the second and create a list of all leaves with the
>> accumulated global state. To illustrate my problem i appended some code.
>> The idea similar applies to a scenegraph.
>>
>> So my Question is: Is there already a pattern for traversal with a 
>> state ?
>>     
>
> Yes. I'm not sure whether state is really necessary for your problem,
> i.e. whether there is a more elegant formulation, but your algorithm
> fits a well-known pattern, namely the one in  Data.Traversable
>
>   import Data.Traversable
>   import Data.Foldable
>
>   import qualified Control.Monad.State
>
>
>   data BTree a = Fork a (BTree a) (BTree a) | Leaf a deriving Show
>
>      -- main functionality
>   instance Traversable BTree where
>      traverse f (Leaf x)     = Leaf <$> f x
>      traverse f (Fork x l r) = Fork <$>
>                                f x <*> traverse f l <*> traverse f r
>
>      -- derived examples
>   instance Foldable BTree where
>      foldMap = foldMapDefault
>   instance Functor  BTree where
>      fmap    = fmapDefault
>
>   flattenTree = toList
>
>      -- state example
>   data StateMod = ModInt | ModString | ModNop deriving Show
>   type State    = (Int, String)
>
>   modState :: StateMod -> State -> State
>   modState ModInt    (x,w) = (x+1,w)
>   modState ModNop    s     = s
>   modState ModString (x,w) = (x,'b':w)
>
>   startState = (0,"a")
>
>   newTree :: BTree StateMod -> BTree State
>   newTree = flip evalState startState
>           . Data.Traversable.mapM (modify' . modState)
>      where
>      modify' f = Control.Monad.State.modify f >> Control.Monad.State.get
>
>
>   
Hi,

Thanks for the quick reply. But it is not quite what i expect. If i 
apply your
solution to an exampletree i get the following result:

tree :: BTree StateMod
tree = Fork ModNop
             (Fork ModInt (Leaf ModInt) (Leaf ModNop))
              (Leaf ModNop)

flattenTree (newTree tree )

which produces:
[(0,"a"),(1,"a"),(2,"a"),(2,"a"),(2,"a")]

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.

Kind regards,
Andreas