https://travis-ci.com/Primetalk/rewritable-tree.svg?branch=feature%2Frewritable-tree
libraryDependencies += "ru.primetalk" %% "rewritable-tree" % "0.1.0"
This library contains some tools for working with
immutable data structures represented with algebraic data types.
These data structures can be thought of as a tree.
One of the tools is the rewrite
function that helps
to optimize the data structure based on some rules.
Let's try to implement a distributive property of elementary algebra:
a * (b + c) == a * b + a * c
We can model arithmetic expressions using the following data structure:
sealed trait Expr
case class Number(i:Int) extends Expr
case class Add(a: Expr, b: Expr) extends Expr
case class Mul(a: Expr, b: Expr) extends Expr
The distributive property (a * (b + c) == a * b + a * c
) can be illustrated with trees:
Mul Add
/ \ / \
a Add == Mul Mul
/ \ / \ / \
b c a b a c
and it can implemented as the following pattern matching rule:
case Mul(a@_, Add(b@_, c@_)) => Add(Mul(a, b), Mul(a, c))
If we want to apply this rule through the whole expression we need a way to traverse the tree and reconstruct it in case of replacement.
def rewrite(rule: Expr => Option[Expr])(tree: Expr): Expr
It's analogous to Functor.map
with the difference that
we are not mapping the data inside the tree but rather
the "spine", the structure of the tree.
We can construct another data structure from our tree, or calculate some statistics about it.
def fold[A](zero: A)(f: A => Expr => A): A
For instance, to count tree nodes:
val count = fold(0)(i => _ => i + 1)
There are two options for fold - whether we traverse the tree depth-first or width-first.
Apart from rewriting trees it's often the case when we want to
collect some data from the tree. This can be achieved with
collect
method
def collect[A](tree: Expr)(pf: PartialFunction[Expr, A]): Seq[A]
It can be used when we want to collect some of the tree elements.