Full source code ⋅ Twitter discussion ⋅ Next chapter
We start with the most classic way to define AST and then gradually move to more sophistacated ones.
For the sake of simplicity, let identifiers be a single latin character (so only 26 unique variables are available).
So a regular term is either an abstraction, an application or a variable:
Since we never define our own datatypes here but rather construct from basic ones - patterns serve a role of constructors:
We declare all three options as a covariant functor, therefore their Sum composition is also a covariant functor - we can use its parameter as an embedding if we apply it to a fixpoint combinator:
Using this version of AST we can declare (abstraction) identity function this way:
And this is how we can provide an argument (application) to identity function:
These chunks of code look a bit too verbose, we can come up with more specialised patterns:
Now both abstraction an application of identity function fit in one line:
In other words verbosity is not an issue... Our issue is that Term is a functor and Recursive Term is not!
There is a way to fix that without sacrificing expressibility.