The following Expr constructors are provided as a convinience for
experimenting with the package, and are unlikely to be useful in any serious
application as they produce expressions with empty annotations!
Extract the annotation or metadata attached to an expression. This only works
at a single level. If you want to extract the annotations for subexpressions as
well – to convert into a tree for example – take a look at
foldWithAnnotation.
Produces a set of bindings introduced by lambda arguments by walking
consecutive Lam expressions and accumulating the arguments. For example,
given...
\x -> \y -> \z -> ......we would produce...
Set.fromList [ "x", "y", "z" ]...and...
\x -> let y = x + 2 in \z -> ......would produce...
Set.fromList [ "x", "z" ]Similar to lambdaBindings, this function produces a set
of bindings by walking consecutive Let expressions and accumulating the names
introduced. For example, given...
let x = 1 in
let y = 2 in
let z = 3 in
......we would produce...
Set.fromList [ "x", "y", "z" ]Pattern matching can introduce new bindings into scope the same way lambda and let expressions might. Not all patterns introduce bindings, though, so this function tells you what – if any – are introduced!
For example, given...
[ x, 2, z ] ->
......we would produce...
Set.fromList [ "x", "z" ]...and...
( _, { y } ) ->
......would produce...
Set.fromList [ "y" ]Recursively transform an expression, bottom-up.
Like transform, this recursively transforms an expression from
the bottom up. It's behaviour is different in two important ways:
Transformations are applied to sub-expressions. If you want a non-recursive version
of this function, check out transformMany_.
🚨 Be mindful of what transformations you are applying, and in what order you
supply them. It is possible to overflow the stack with transformMany if the
transformations you supply diverge – we will never stop trying to apply them!
Repeatedly apply a list of transformations to a given expression. This is
distinct from transformMany in that it does not apply the
transformations recursively to sub-expressions.
🚨 Be mindful of what transformations you are applying, and in what order you
supply them. It is possible to overflow the stack with transformMany_ if the
transformations you supply diverge – we will never stop trying to apply them!
fold is an abstraction over a recurisve, bottom-up traversal of an
expression. It takes a record of functions, each of which is responsible for
handling a particular type of expression but where recursive expressions are
replaced with the result of the previous fold. Consider the analog between:
type Expr ann
= App ann (Expr ann) (Expr ann)
| Lam ann String (Expr ann)
| ...and
{ onApp : a -> a -> a
, onLam : a -> String -> a -> a
, ...
}Importantly, the functions we provide to fold are not recursive!
❓ We mentioned that fold performed a bottom-up traversal. You might be
wondering if it is possible to perform a top-down traversal instead... and it
is! To achieve this – and bear with me – we need to accumulate a function from
the fold, and then execute that.
By accumulating a function it is possible to pass state down the tree while we build something up. This is a bit mind bending so let's take a look at a simple example.
💡 For the true functional programming nerds, this function is also known as a
catamorphism or cata.
This is a convenient version of the slightly more general
foldWithExpr that only includes the annotation for the
current expression.
Just like how List.foldl reduces a list down to a single value, this
function gives us a way to fold an expression tree down to a single value. We
pass in a record of functions that are called according to the type of expression
we are currently folding: you can think of it like pattern matching but now how
the places where our type would typically recurse on Expr ann instead have the
type a to hold the value of the previous fold.
In addition, we also get the current Expr ann being folded – this can be useful
if you need the original context of the expression you are folding. If you just
need the annotation attached to the expression, you can use
foldWithAnnotation instead. If you don't need to know
anything about the expression you are folding, you can use fold.
💡 For the true functional programming nerds, this function is more commonly
known as a paramorphism or para. Typically described as a model of primitive
recursion, para gives us access to the original expression as well as the
transformation that was applied to its child
An expression representing a relatively simple functional programming language. It noteably includes pattern matching and let bindings.
The
anntype variable represents any annotations you might want to attach to the AST. This could include source spans to locate or translate the AST back to some source code, or it could be type annotations added during type inference, or whatever else might be useful!.