Download the PHP package pwm/treegami without Composer
On this page you can find all versions of the php package pwm/treegami. It is possible to download/install these versions without Composer. Possible dependencies are resolved automatically.
Package treegami
Short Description A tree implementation that can be unfolded, mapped and folded.
License MIT
Homepage https://github.com/pwm/treegami
Informations about the package treegami
Treegami
Treegami is a small library for mapping and folding trees of arbitrary shape. As programmers we often work with trees, either in the open or in hiding, eg. when the're camouflaging as a json document. Treegami makes transforming these structures and extracting data from them easy. The name Treegami is a portmanteau of the words tree and origami.
Table of Contents
- Requirements
- Installation
- Usage
- How it works
- Tests
- Changelog
- Licence
Requirements
PHP 7.1+
Installation
$ composer require pwm/treegami
Usage
As a start, let's just create a tree manually:
Which results in the following tree:
Let's map this tree using a function that maps a string to its length and null to 0:
Which results in the following tree:
Now let's fold this tree to the sum of its node values:
Finally an example of unfolding a tree from a seed value:
Which results in the following full binary tree:
How it works
Some (most?) of the readers will be familiar with the higher-order functions map
and fold
on lists. In PHP they are called array_map
and array_reduce
, respectively.
As a quick refresher: the function map
maps a list into another list by applying a function to its elements, while the function fold
"folds up" a list starting from a seed value by applying a function to its elements accumulating them into a final value. For example if we have a function addOne
, which adds one to a number, then map(addOne, [1,2,3,4,5])
results in [2,3,4,5,6]
. If we then have a function add
, which adds 2 numbers together, then fold(add, 0, [2,3,4,5,6])
, 0
being the seed value, results in 0+2+3+4+5+6 = 20
.
However map
and fold
is not specific to lists. In fact many different structures can be mapped and folded, including trees. Mapping a function over a tree results in another tree of the same shape where each node is the result of the function applied to it. Folding a tree using a function means traversing the tree, applying the function to its nodes and accumulating them into a final value.
For example if we have the following tree:
then mapping addOne
over it results in:
In turn, folding this tree with add
, using the root value 2
as the seed value, results in: 2+3+4+5+6+7+8+9+10+11 = 65
.
In Treegami the seed value for fold
by default is the value of the root node and an empty tree means a tree with no children and null as the node value.
Depending on which order we combine the current value with the accumulated value in our fold function we get different traversal orders. Specifically, if we prepend the current value to the accumulated value we get preorder traversal, while if we append the current value to the accumulated value we get postorder traversal.
In general fold
does not need to "collapse" the structure into some scalar value, like an integer. We can just as easily "fold" the structure into another structure. This is exactly how map
works in Treegami, meaning that map
is expressed via fold
.
unfold
on the other hand is the "opposite" (or dual, to use the correct terminology) of fold
. It takes a function and a seed value and "unfolds" that seed value into a structure, in our case into a tree. What's important to understand is that the function that unfolds the seed returns a pair of values: a node in our tree and a list of seed values, that will be used for subsequent iterations of unfold
, until it returns an empty list, essentially terminating the iteration.
For the curious and brave out there: fold
is a Catamorphism while its dual unfold
is an Anamorphism. You can read more about these terms in the paper Functional programming with bananas, lenses, envelopes and barbed wire.
Tests
$ vendor/bin/phpunit
$ composer phpcs
$ composer phpstan
$ composer infection
Changelog
Click here
Licence
MIT