One aspect of many functional languages that’s always fascinated me is the ease with which you can express a recursive structure, such as a language, and have it evaluated. Suppose you want to define the grammar of a DSL of propositions, in F# you could do so using the discriminated union type:
type Proposition = | True | And of Proposition * Proposition | Or of Proposition * Proposition | Not of Proposition
In an object-oriented language like C#, this definition would be analogous to a hierarchy of classes. Proposition would be the base class of True, And, Or, and Not. Each would then have a constructor that accepts some number of arguments, e.g., the And constructor would accept a two-tuple, two propositions, making the Proposition type recursive. In C# you might even model the recursive relationship using the Composite pattern.
In F#, an instance of the Proposition type may be created using a constructor syntax that resembles that of a function call:
let p = And(Or(True, Not(True)), Not(Not(True)))
Now, because of the recursive nature of the Proposition type, instances of it form a parse tree-like structure:
And /\ / \ Or Not /\ \ / \ \ True Not Not \ \ \ \ True True
Having a parse tree is not useful in itself. What you need is some way to execute or evaluate it. Given the recursive nature of the grammar, it makes sense for the evaluator to be recursively defined as well. The evaluator would do pattern matching on the node type, deconstructing it into the parts needed to evaluate it. Since our language of propositions maps directly to the boolean operations of F#, it’s simple to evaluate the parse tree:
let rec eval (p: Proposition) = match p with | True -> true | And(p1, p2) -> eval p1 && eval p2 | Or (p1, p2) -> eval p1 || eval p2 | Not(p1) -> not (eval p1) let e = eval p // e : bool = true
PS: I’ve encountered this gist implementing a nice progression of the same idea with expressions and variables.