Skip to content

functional-data-structure/finger-tree

Repository files navigation

Finger trees for JavaScript. See docs. Parent is @functional-data-structure/persistent.

data FingerTree x = Empty
                  | Single x
                  | Deep ( Digit x ) ( FingerTree ( Node x ) ) ( Digit x )

License Version Tests Dependencies GitHub issues Downloads

Code issues Code maintainability Code coverage (cov) Code technical debt Documentation Package size

πŸ‘©β€πŸ« API reference

The data structure is fully persistent: All methods are pure functions that do not modify their object.

The parent project shows how specialized persistent data structures can be build on top of those methods.

🌡 Definition of a Tree

data Tree x = Empty
            | Single x
            | Deep ( Digit x ) ( Tree ( Node x ) ) ( Digit x )

πŸ“ Definition of a Measure

Measure = (
  plus = ( x , x ) -> m
  measure = x -> m
  zero = ( ) => m
)

Example of a Measure

The following measure will compute the size of each subtree.

const counter = {
  plus : ( x , y ) => x + y ,
  measure : x => 1 ,
  zero : ( ) => 0 ,
} ;

See also @functional-abstraction/measure for more examples of measures and see @functional-data-structure/persistent for examples of data structures that can be build on top of this abstraction.

πŸ“¦ How to import

⚠️ The code requires regeneratorRuntime to be defined, for instance by importing regenerator-runtime/runtime.

First, require the polyfill at the entry point of your application:

require( 'regenerator-runtime/runtime' ) ;
// or
import 'regenerator-runtime/runtime.js' ;

Then require what you need from the exported object, for instance the two main API functions from and empty:

const { from , empty } = require( '@functional-data-structure/finger-tree' ) ;
// or
import { from , empty } from '@functional-data-structure/finger-tree' ;

πŸ‘Ά How to create a Tree

empty(Measure) -> Tree

Create an empty tree from a measure object.

let tree = empty( counter ) ;

from(Measure, Iterable) -> Tree

Create a tree from a measure object and an iterable.

let tree = from( counter , 'abc' ) ;

❓ Predicates

Tree#measure() -> m

Returns the measure of the tree.

if ( tree.measure() > 1 ) ...

Tree#isEmpty() -> Boolean

Returns true if the tree is empty, false otherwise.

return tree.isEmpty() ? 'empty' : 'not empty' ;

πŸ§‚ Add values

Tree#push(x) -> Tree

Returns a new tree with an additional value as the new right-most value.

tree = tree.push('k');

Tree#cons(x) -> Tree

Returns a new tree with an additional value as the new left-most value.

tree = tree.cons('g');

Tree#append(Iterable) -> Tree

Equivalent to applying push to each value of the iterable in order.

tree.append( 'www' ) ;

Tree#prepend(Iterable) -> Tree

Equivalent to applying cons to each value of the iterable in reverse order.

tree.prepend( 'xyz' ) ;

πŸ• Slice

Tree#head() -> x

Returns the left-most value in the tree.

let head = tree.head() ; // 'a'

Tree#last() -> x

Returns the right-most value in the tree.

let last = tree.last() ; // 'b'

Tree#init() -> Tree

Returns a new tree without the right-most value.

while ( ! tree.isEmpty() ) tree = tree.init() ;

Tree#tail() -> Tree

Returns a new tree without the left-most value.

while ( ! tree.isEmpty() ) tree = tree.tail() ;

πŸŒ— Merge

Tree#concat(Tree) -> Tree

Returns the concatenation of two trees.

tree = tree.concat( tree );

πŸ’” Split

The following methods allow you to efficiently split a tree at the value where the measure crosses a given threshold.

Tree#splitTree(Function, m) -> [ Tree , x , Tree ]

Split the tree into a left tree, a middle value, and a right tree according to a predicate on the measure of the tree increased by a constant measure m. The predicate must be monotone, false then true, on prefixes of the values in left-to-right order. The middle value x is the value for which the predicate switches from false to true.

let [ left , middle , right ] = tree.splitTree( measure => measure > 1 , 1 ) ;

Tree#split(Function) -> [ Tree , Tree ]

Split the tree into a left tree and a right tree according to a predicate on the measure of the tree. The predicate must be monotone, false then true, on prefixes of the values in left-to-right order. The left-most value of the right tree is the value for which the predicate switches from false to true.

let [ left , right ] = tree.split( measure => measure > 2 ) ;

Tree#takeUntil(Function) -> Tree

Returns the left tree of Tree#split.

let left = tree.takeUntil( measure => measure > 2 ) ;

Tree#dropUntil(Function) -> Tree

Returns the right tree of Tree#split.

let right = tree.dropUntil( measure => measure > 2 ) ;

πŸ›Έ Visit

Tree[Symbol.iterator]() -> Iterable

Returns an iterator on the values of the tree in left-to-right order.

for ( const x of tree ) console.log( x ) ;

Tree#reversed() -> Iterable

Returns an iterator on the values of the tree in right-to-left order.

for ( const x of tree.reversed() ) console.log( x ) ;

πŸ“œ References

πŸ”— Links