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