[Haskell-cafe] stateful walk through a tree?

[David Tolpin]

Hi,

I am looking for help in design of a stateful tree walker. I have a tree-like data structure (an AST for a small language) for which there is a general stateful walk procedure. That is, each node type is an instance of a walker class, and the walk function is monadic:

class Walker a where
   walk :: a -> State Context b

The context is used to store names in the scope, for example.  Now, I'd like to use Walker as a general class for implementing several different transformations on the tree (like cross-referencing, code emission, tree visualisation). Those transformations will need expanded state. What is the proper design for that?

In Common Lisp, for example, I would Context to contain an opaque slot (visitor), and would assign additional state information to it; a would also define a generic function that would dispatch on the visitor (and probably on walker if I end up having more than one walker).

How would I do that in Haskell? I'd like to avoid using mutable variables for now (mostly for didactic puproses).

David