scalaz-core/scalaz/FingerTree

FingerTree

sealed abstract
class FingerTree[V, A](implicit measurer: Reducer[A, V])

Finger trees with leaves of type A and Nodes that are annotated with type V.

Finger Trees provide a base for implementations of various collection types, as described in "Finger trees: a simple general-purpose data structure", by Ralf Hinze and Ross Paterson. A gentle introduction is presented in the blog post "Monoids and Finger Trees" by Heinrich Apfelmus.

This is done by choosing a suitable type to annotate the nodes. For example, a binary tree can be implemented by annotating each node with the size of its subtree, while a priority queue can be implemented by labelling the nodes by the minimum priority of its children.

The operations on FingerTree enforce the constraint measured (in the form of a Reducer instance).

Finger Trees have excellent (amortized) asymptotic performance:

  • Access to the first and last elements is O(1)
  • Appending/prepending a single value is O(1)
  • Concatenating two trees is (O lg min(l1, l2)) where l1 and l2 are their sizes
  • Random access to an element at n is O(lg min(n, l - n)), where l is the size of the tree.
  • Constructing a tree with n copies of a value is O(lg n).
Type Params
A

The type of the elements stored at the leaves

V

The type of the annotations of the nodes (the '''measure''')

See also
Companion
object
class Object
trait Matchable
class Any

Value members

Abstract methods

def fold[B](empty: => B, single: (V, A) => B, deep: (V, Finger[V, A], => FingerTree[V, Node[V, A]], Finger[V, A]) => B): B

Fold over the structure of the tree. The given functions correspond to the three possible variations of the finger tree.

Fold over the structure of the tree. The given functions correspond to the three possible variations of the finger tree.

Value Params
deep

otherwise, convert the measure, the two fingers, and the sub tree to a B.

empty

value to return if the tree is empty

single

if the tree contains a single element, convert the measure and this element to a B

Concrete methods

def +:(a: A): FingerTree[V, A]

Prepends an element to the left of the tree. O(1).

Prepends an element to the left of the tree. O(1).

def :+(a: => A): FingerTree[V, A]

Appends an element to the right of the tree. O(1).

Appends an element to the right of the tree. O(1).

def :-|(a: => A): FingerTree[V, A]

Replace the last element of the tree with the given value. O(1)

Replace the last element of the tree with the given value. O(1)

def <++>(right: => FingerTree[V, A]): FingerTree[V, A]

Appends the given finger tree to the right of this tree.

Appends the given finger tree to the right of this tree.

def add1(n: A, right: => FingerTree[V, A]): FingerTree[V, A]
def add2(n1t: => A, n2t: => A, right: => FingerTree[V, A]): FingerTree[V, A]
def add3(n1t: => A, n2t: => A, n3t: => A, right: => FingerTree[V, A]): FingerTree[V, A]
def add4(n1t: => A, n2t: => A, n3t: => A, n4t: => A, right: => FingerTree[V, A]): FingerTree[V, A]
def addDigits0(m1: FingerTree[V, Node[V, A]], dig1: Finger[V, A], dig2: Finger[V, A], m2: => FingerTree[V, Node[V, A]]): FingerTree[V, Node[V, A]]
def addDigits1(m1: FingerTree[V, Node[V, A]], d1: Finger[V, A], xt: => A, d2: Finger[V, A], m2t: => FingerTree[V, Node[V, A]]): FingerTree[V, Node[V, A]]
def addDigits2(m1: FingerTree[V, Node[V, A]], d1: Finger[V, A], xt: => A, yt: => A, d2: Finger[V, A], m2t: => FingerTree[V, Node[V, A]]): FingerTree[V, Node[V, A]]
def addDigits3(m1: FingerTree[V, Node[V, A]], d1: Finger[V, A], xt: => A, yt: => A, zt: => A, d2: Finger[V, A], m2t: => FingerTree[V, Node[V, A]]): FingerTree[V, Node[V, A]]
def addDigits4(m1: FingerTree[V, Node[V, A]], d1: Finger[V, A], xt: => A, yt: => A, zt: => A, wt: => A, d2: Finger[V, A], m2t: => FingerTree[V, Node[V, A]]): FingerTree[V, Node[V, A]]
def foldLeft[B](b: B)(f: (B, A) => B): B
def foldMap[B](f: A => B)(implicit s: Monoid[B]): B
def foldRight[B](z: => B)(f: (A, => B) => B): B
def foreach(f: A => Unit): Unit

Execute the provided side effect for each element in the tree.

Execute the provided side effect for each element in the tree.

def head: A

Selects the first element in the tree.

Selects the first element in the tree.

Throws
if

the tree is empty

def init: FingerTree[V, A]

Selects a subtree containing all elements except the last

Selects a subtree containing all elements except the last

Throws
if

the tree is empty

def isEmpty: Boolean
def iterator: Iterator[A]

An iterator that visits each element in the tree.

An iterator that visits each element in the tree.

def last: A

Selects the last element in the tree.

Selects the last element in the tree.

Throws
if

the tree is empty

def map[B, V2](f: A => B)(implicit r: Reducer[B, V2]): FingerTree[V2, B]

Maps the given function across the tree, annotating nodes in the resulting tree according to the provided Reducer.

Maps the given function across the tree, annotating nodes in the resulting tree according to the provided Reducer.

def measure: Maybe[V]
def reduceTo[M : Monoid]: M

Convert the leaves of the tree to an M

Convert the leaves of the tree to an M

def reverseIterator: Iterator[A]

An iterator that visits each element in the tree in reverse order.

An iterator that visits each element in the tree in reverse order.

def split(pred: V => Boolean): (FingerTree[V, A], FingerTree[V, A])

Splits this tree into a pair of subtrees at the point where the given predicate, based on the measure, changes from false to true. O(log(min(i,n-i)))

Splits this tree into a pair of subtrees at the point where the given predicate, based on the measure, changes from false to true. O(log(min(i,n-i)))

Value Params
pred

predicate on node measures. Must be a semigroup homomorphism from the semigroup V of node measures to the semigroup of Booleans with || as the semigroup operation. Namely, it must hold that pred(v1 |+| v2) = pred(v1) || pred(v2).

Returns

(as, bs), where - as: the subtree containing elements before the point where pred first holds - bs: the subtree containing elements at and after the point where pred first holds. Empty if pred never holds.

def split1(pred: V => Boolean): (FingerTree[V, A], A, FingerTree[V, A])

Like split, but returns the element where pred first holds separately

Like split, but returns the element where pred first holds separately

Throws
if

the tree is empty.

def tail: FingerTree[V, A]

Selects a subtree containing all elements except the first

Selects a subtree containing all elements except the first

Throws
if

the tree is empty

def to[F[_]](implicit R: Reducer[A, F[A]], M: Monoid[F[A]]): F[A]

Convert the leaves of the tree to an F[A]

Convert the leaves of the tree to an F[A]

def toIList: IList[A]

Convert the leaves of the tree to a scalaz.IList

Convert the leaves of the tree to a scalaz.IList

def toList: List[A]

Convert the leaves of the tree to a scala.List

Convert the leaves of the tree to a scala.List

def toStream: Stream[A]

Convert the leaves of the tree to a scala.Stream

Convert the leaves of the tree to a scala.Stream

override
def toString: String

Convert the tree to a String. Unsafe: this uses Any#toString for types V and A

Convert the tree to a String. Unsafe: this uses Any#toString for types V and A

Definition Classes
Any
def traverseTree[F[_], V2, B](f: A => F[B])(implicit ms: Reducer[B, V2], F: Applicative[F]): F[FingerTree[V2, B]]

Like traverse, but with a more constraint type: we need the additional measure to construct the new tree.

Like traverse, but with a more constraint type: we need the additional measure to construct the new tree.

def viewl: ViewL[[_] =>> FingerTree[V, _$9], A]
def viewr: ViewR[[_] =>> FingerTree[V, _$14], A]
def |-:(a: A): FingerTree[V, A]

Replace the first element of the tree with the given value. O(1)

Replace the first element of the tree with the given value. O(1)