🌵 @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 )

• 👩‍🏫 API reference
  • 🌵 Definition of a Tree
  • 📏 Definition of a Measure
    • Example of a Measure
  • 📦 How to import
  • 👶 How to create a Tree
    • empty(Measure) -> Tree
    • from(Measure, Iterable) -> Tree
  • ❓ Predicates
    • Tree#measure() -> m
    • Tree#isEmpty() -> Boolean
  • 🧂 Add values
    • Tree#push(x) -> Tree
    • Tree#cons(x) -> Tree
    • Tree#append(Iterable) -> Tree
    • Tree#prepend(Iterable) -> Tree
  • 🍕 Slice
    • Tree#head() -> x
    • Tree#last() -> x
    • Tree#init() -> Tree
    • Tree#tail() -> Tree
  • 🌗 Merge
    • Tree#concat(Tree) -> Tree
  • 💔 Split
    • Tree#splitTree(Function, m) -> [ Tree , x , Tree ]
    • Tree#split(Function) -> [ Tree , Tree ]
    • Tree#takeUntil(Function) -> Tree
    • Tree#dropUntil(Function) -> Tree
  • 🛸 Visit
    • Tree[Symbol.iterator]() -> Iterable
    • Tree#reversed() -> Iterable
• 📜 References
• 🔗 Links

👩‍🏫 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

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

🔗 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)