:cactus: @functional-data-structure/finger-tree

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 )

• :woman_teacher: API reference
  • :cactus: Definition of a Tree
  • :straight_ruler: Definition of a Measure
    • Example of a Measure
  • :package: How to import
  • :baby: How to create a Tree
    • empty(Measure) -> Tree
    • from(Measure, Iterable) -> Tree
  • :question: Predicates
    • Tree#measure() -> m
    • Tree#isEmpty() -> Boolean
  • :salt: Add values
    • Tree#push(x) -> Tree
    • Tree#cons(x) -> Tree
    • Tree#append(Iterable) -> Tree
    • Tree#prepend(Iterable) -> Tree
  • :pizza: Slice
    • Tree#head() -> x
    • Tree#last() -> x
    • Tree#init() -> Tree
    • Tree#tail() -> Tree
  • :last_quarter_moon: Merge
    • Tree#concat(Tree) -> Tree
  • :broken_heart: Split
    • Tree#splitTree(Function, m) -> [ Tree , x , Tree ]
    • Tree#split(Function) -> [ Tree , Tree ]
    • Tree#takeUntil(Function) -> Tree
    • Tree#dropUntil(Function) -> Tree
  • :flying_saucer: Visit
    • Tree[Symbol.iterator]() -> Iterable
    • Tree#reversed() -> Iterable
• :scroll: References
• :link: Links

:woman_teacher: 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.

:cactus: Definition of a Tree

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

:straight_ruler: 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.

:package: How to import

:warning: 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' ;

:baby: 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' ) ;

:question: 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' ;

:salt: 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' ) ;

:pizza: 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() ;

:last_quarter_moon: Merge

Tree#concat(Tree) -> Tree

Returns the concatenation of two trees.

tree = tree.concat( tree );

:broken_heart: 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 ) ;

:flying_saucer: 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 ) ;

:scroll: References

• Finger trees: a simple general-purpose data structure -- Hinze and Paterson

:link: Links

• A coffeescript implementation with ZLIB licensing (:white_check_mark: the implementation is correct)
• An implementation in Python with Apache licensing (:warning: the implementation is missing splitting functionality)
• A JavaScript implementation with MIT licensing (:rotating_light: the implementation is incorrect)