Mark T.B. Carroll wrote:

I don't know what the infamous "expression problem" is, nor am I familiar with polymorphic variants or structural subtyping, but have you looked at the Data.Generics.* stuff and Scrap Your Boilerplate papers? They may be relevant.

The expression problem is "a new name for an old problem", basically being able to extend a data type and functions over the data type in seperate modules with no knowledge of each other. Here is a link to (I think) the original description: http://www.daimi.au.dk/~madst/tool/papers/expression.txt Structural subtyping is something like "duck typing" in dynamic languages, but checked at compile time. For records, it means that if you only access two labels then the function will work on any record that has those labels with those types, even if it may have more labels. For variants (or sum-types, or tagged unions, or whatever they are called in Haskell) it means that if your function can handle certain cases, then it can also handle values that range over less cases. So in pseudo-Haskell with imaginary subtyping: data Vertical a = U a | D a data Horizontal a = L a | R a data Direction a = #Vertical a | #Horizontal a -- borrowing ocaml syntax: this means that Direction shares constructors with Vertical and Horizontal getData :: Direction a -> a getData (U a) = a getData (D a) = a getData (L a) = a getData (R a) = a getLeftStick :: IO (Vertical Int) getRightStick :: IO (Horizontal Int) main = do { accel <- getLeftStick; print (getData accel) } So getData doesn't care that accel is Horizontal and not Direction because Horizontal is a sub-type of direction. Of course, in this syntax since you named the subtyping relationship its more technically nominal subtyping (like in traditional static OO languages) not structural subtyping (which figures out the subtype relationship from the structure automatically, so if we just reused the U,D,L, and R constructors in Direction). I have looked into SYB briefly. I will probably end up using it to keep the amount of code to a minimum, but it won't save me from having to define a different data type for each version of the AST if I want to preserve type safety.