FingerTree

This package provides an implementation of 2-3 finger trees. Finger trees are a general purpose purely functional data structure that can be used to efficiently implement many other kinds of data structures like priority queues. A finger tree is an annotated sequence, where each node stores the result of applying an associative operation to its descendents. This information (the "annotation" or "tag") can be used in a variety of ways to create new data structures beyond just trees.

Core Types

type Config a tag

The Config type records the tag type's semantics. This includes the zero value, and the combine definition in used. This type could also be called "annotator" or "decorator", because it tells the functions in this module how they should annotate the nodes of the tree.

type Tree a tag

The Tree type is a finger tree with elements of type a annotated by type tag, instantiated with a particular tag Config.

Note on annotations

To facilitate this data structure the annotations used should form a monoid in respect of the Config of the tree. This means that the combine function you provide should be associative, and the empty value you provide should act as an identity element: combine x empty == x for any annotation x.

I have used the term config because elm doesn't have the ability to prove the annotation type chosen does actually form a monoid under the action of a particular function, and I think for the purposes of defining things like priority queue semantics (one of the main applications of a finger tree) "config" makes more sense.

Creation

create :

{ annotate : a -> tag

, combine : tag -> tag -> tag

, empty : tag

}

-> Config a tag

Create a new tree config. You need to provide a function that annotates nodes, an associative function which can be used to combine two annotations, and a zero value for the annotations to start with. The zero value is only used to initialise accumulators, and ideally should not be used as an actual annotation. It should be the identity element of combine.

empty : Config a tag -> Tree a tag

Given the config you want to use, create an empty tree using that config.

Inserting elements

consLeft : a -> Tree a tag -> Tree a tag

Add an element to a tree at the left side/the start.

consRight : a -> Tree a tag -> Tree a tag

Add an element to the tree at the right side/the end.

appendList : List a -> Tree a tag -> Tree a tag

Add a list of elements to a tree by consing them to the right side/the end.

prependList : List a -> Tree a tag -> Tree a tag

Add a list of elements to a tree by consing them to the left side/the start.

Retrieving elements and subtrees

isEmpty : Tree a tag -> Bool

Check if the tree is empty.

annotation : Tree a tag -> tag

Extract the tree's annotation. There a few things to keep in mind here:

If the tree is empty the empty annotation of the tree's config is returned.
This is the cumulative combination / sum of the annotations of the tree's elements.

head : Tree a tag -> Maybe a

Extract the leftmost / first element of the tree.

tail : Tree a tag -> Maybe (Tree a tag)

Remove the leftmost / first element of the tree.

prefix : Tree a tag -> Maybe (Tree a tag)

Remove the rightmost / last element of the tree.

last : Tree a tag -> Maybe a

Extract the rightmost/last element of the tree.

viewLeft : Tree a tag -> Maybe ( a, Tree a tag )

Extract the leftmost element from the tree and return it and the remaining tree.

viewRight : Tree a tag -> Maybe ( a, Tree a tag )

Extract the rightmost element from the tree and return it and the remaining tree.

length : Tree a tag -> Int

This function counts the number of elements in the tree by visiting each element. You could also use the annotation to keep track of this.

Working on trees

append : Tree a tag -> Tree a tag -> Tree a tag

Append two trees, this is like joining the second tree to the end of the first tree.

split : (tag -> Bool) -> Tree a tag -> ( Tree a tag, Tree a tag )

Split a tree using a monotonic predicate on the tags. The first tree of the result is everything before the predicate was true, and the final result is the everything afterwards.

The predicate being monotonic means that if it's true for a tag t then it's also true for any combine t x.

splitAt :

comparableTag

-> Tree a comparableTag

-> ( Tree a comparableTag, Tree a comparableTag )

Split a tree at a the given tag. This function needs the tags to be comparable so that it can split the tree by tag >= i.

cut : (tag -> Bool) -> Tree a tag -> ( Tree a tag, Maybe a, Tree a tag )

Cut the tree, extracting everything before the predicate, the first value for which the predicate is true (if it is) and everything afterward.

foldLeft : (a -> b -> b) -> b -> Tree a tag -> b

Perform a fold on the tree from left to right; using the same argument order as List.foldl.

foldRight : (a -> b -> b) -> b -> Tree a tag -> b

Perform a fold on the tree from right to left; using the same argument order as List.foldr.

toList : Tree a tag -> List a

Convert a tree into a regular elm list. The elements are ordered from left to right.

equal : Tree a tag -> Tree a tag -> Bool

Check if two trees are equal by comparing their elements from left to right.

Working with annotations and elements

type alias Tagged a tag =

( tag, a )

Type alias for pairs of elements and their tag.

unconsLeft : Tree a tag -> Maybe ( Tagged a tag, Tree a tag )

Like viewLeft but also returns the annotation of the element.

unconsRight : Tree a tag -> Maybe ( Tagged a tag, Tree a tag )

Like viewRight but also returns the annotation of the element.

cutWithTag :

(tag -> Bool)

-> Tree a tag

-> ( Tree a tag, Maybe (Tagged a tag), Tree a tag )

Like split but also returns the annotation of the element which caused the split.

foldLeftWithTag : (b -> Tagged a tag -> b) -> b -> Tree a tag -> b

Like foldLeft but uses the natural argument order and uses the annotation and element to fold.

foldRightWithTag : (Tagged a tag -> b -> b) -> Tree a tag -> b -> b

Like foldRight but uses the natural argument order and uses the annotation and element to fold.

Helpers for working with tree configuration

config : Tree a tag -> Config a tag

Extract the config being used by the tree.

mempty : Config a tag -> tag

The empty value used by the tree config.

mappend : Config a tag -> tag -> tag -> tag

The associative operation that combines annotations used by the tree config.

annotator : Config a tag -> a -> tag

The function that assigns elements their annotation used by the tree config.

Modules

FingerTree

Mehgugs/elm-finger-tree/1.0.1