I bring this up because I have been working on a Scheme compiler in Haskell for fun, and something like polymorphic variants would be quite convinent to allow you to specify versions of the AST (input ast, after closure conversion, after CPS transform, etc.), but allow you to write functions that work generically over all the ASTs (getting the free vars, pretty printing, etc.).
Proper subtyping or at least extendable ADTs would be nicer, but you can have type-checked progress flags using phantom types, e.g.: data LT flag = L String (LT flag) | A (LT flag) (LT flag) | Var String data Input data Renamed data CPSed data ConstPropd rename :: LT Input -> LT Renamed cps :: LT Renamed -> LT CPSed constantPropagate :: LT CPSed -> LT ConstPropd dumpExpr :: (forall a. LT a) -> String -- ignores progress flag This way you have at least a way to check that the proper phases have been run before. It might even be possible to store different things in the nodes (not tested), like in: newtype Ident = MkIdent String class VarType flag vt | flag -> vt instance VarType Input String instance VarType Renamed Ident instance VarType CPSed Ident instance VarType ConstPropd Ident data LT flag = (VarType flag vt => L vt (LT flag)) | ... (This probably doesn't work, but you get the idea.) / Thomas