# primetalk / rewritable-tree  0.1.0

Rewritable tree typeclass and supporting algorithms

Scala versions: 2.13 2.12

# Rewritable tree

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.

## Primer

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
/ \              / \
/ \         / \  / \
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.

## Fold (aka catamorphism)

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.

## Collect data

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.