Modeling multiple levels of inheritance using discriminated unions

Question

Is there a recommended way to model multiple levels of inheritance in F#, presumably using a discriminated union?

Taking something like the following in C#:

class Expr { }
class SourceExpr : Expr { }
class JoinExpr : SourceExpr { }
class TableExpr : SourceExpr { }

I've done this in F#:

type SourceExpr =
    | Join of JoinExpr
    | Table of TableExpr

type Expr = 
    | Source of SourceExpr
    | ...

Is there a better way? Does this provide the same polymorphic behavior as inheritance?

Answer 1

It's hard to be too prescriptive here without more information. Depending on what you are trying to do, it may make more sense to use a class hierarchy or a discriminated union (DU). The most common/obvous trade-offs are that class hierarchies are 'open' whereas DUs are 'closed'. That is, you can easily add new types to a class hierarchy, but adding a new operation (abstract method on base class) requires changing all existing classes. In contrast, with DUs you can easily add a new operation (function that pattern matches over the data type), but to add a new case (subclass) you have to redefine the type and update all the existing operations to deal with the new case. (This is sometimes called "the expression problem".)

A typical example that's good for DUs is a compiler; you have a language abstract syntax tree where the language and tree structure are fixed, but you may author many different tree transform operations inside the compiler. A typical example that's good for class hierarchies is UI frameworks; you have some base class(es) that defines all the operations that widgets must supply (Draw, Resize, ...) but then users will add their own custom subtypes with extra capabilities.