Full source code ⋅ Previous chapter ⋅ Next chapter
In previous chapter we defined lambda term using this Sum functor composition where each functor encodes type of term - Along is for abstraction, Twice is for application, Flout is for variable:
Let's look at each of these functors' supertypes to check out their contents:
If we feed functor to a fixpoint combinator its parameters become subexpressions but Flout doesn't have any - this is where we have a stopping point i.e. it serves as a leaf in our improvised Abstract Syntax Tree.
So that if we exclude Flout from this term we are stuck with infinetely coinductively defined expression:
Some primitives give us ability to control unrestricted recursion, Instruction is one of them:
Using this new version of AST we can declare (abstraction) identity function this way:
And this is how we can provide an argument (application) to identity function:
As previously, we can come up with more specialised patterns:
... so that these code snippets look completely identical!
However despite the superficial similarity, there is one big improvement - our AST is a functor now!
As you can see whenever we map we only affect variables without touching actual expression - that's the purpose of being a functor.
Pretty often when we buld new functors from more primitive ones - assosiated natural transformations come for free. Let's traverse our AST!
Challenge: what is going to be printed to a console output if you run it? Run executables to check the answers.