Product
Introducing License Enforcement in Socket
Ensure open-source compliance with Socket’s License Enforcement Beta. Set up your License Policy and secure your software!
ru.primetalk:rewritable-tree_2.12
Advanced tools
Rewritable tree typeclass and supporting algorithms.
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.
FAQs
Rewritable tree typeclass and supporting algorithms.
We found that ru.primetalk:rewritable-tree_2.12 demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 0 open source maintainers collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Product
Ensure open-source compliance with Socket’s License Enforcement Beta. Set up your License Policy and secure your software!
Product
We're launching a new set of license analysis and compliance features for analyzing, managing, and complying with licenses across a range of supported languages and ecosystems.
Product
We're excited to introduce Socket Optimize, a powerful CLI command to secure open source dependencies with tested, optimized package overrides.