happy Haskell hacking for compiler writers

[Norman Ramsey]

I'm curious about using purely functional data structures to represent
a control-flow graph in a compiler.   I'm working on a compiler that
uses this model:

  1. Build a control-flow graph
  2. Execute a million optimization steps, each of which makes a small
     mutation to the control-flow graph
  3. Linearize the control-flow graph and emit assembly code

Right now we're using mutable data structures, and I'm curious about
using functional ones.  I figure readers of this list are more likely
than most to know how to write things like ``rewrite every basic
block as a new subgraph with one entry and one exit.''  

Any suggestions about what data structures I should use, what the interface
should look like, and especially what the critical higher-order functions
are and how they should be implemented?  (I should add that I care about
efficiency---one of the reasons I'm interested in a functional data structure
is that I believe I'm paying a lot for all the mutation I'm doing.)

Pointers to papers are code are also very welcome.



Norman