FSharpx.Collections


FSharpx.Collections

FSharpx.Collections Namespace

TypeDescription
DList<'T>

DList is an ordered linear structure implementing the List signature (head, tail, cons), end-insertion (conj), and O(1) append. Ordering is by insertion history. DList is an implementation of John Hughes' append list.

Deque<'T>

Double-ended queue is an ordered linear linear structure implementing the signature of List (head, tail, cons) as well as the mirror-image Vector signature (last, initial, conj). "head" inspects the first or left-most element in the structure, while "last" inspects the last or right-most element. "rev" (reverse) has time complexity O(1). Ordering is by insertion history.

Heap<'T>

Heap is an ordered linear structure where the ordering is either ascending or descending. "head" inspects the first element in the ordering, "tail" takes the remaining structure after head, and "insert" places elements within the ordering. PriorityQueue is available as an alternate interface. According to Okasaki the time complexity of the heap functions in this Heap implementation (based on the "pairing" heap) have "resisted" time complexity analysis.

HeapData<'T>
IPriorityQueue<'T>
LazyList<'T>

LazyLists are possibly-infinite, cached sequences. See also IEnumerable/Seq for uncached sequences. LazyLists normally involve delayed computations without side-effects. The results of these computations are cached and evaluations will be performed only once for each element of the lazy list. In contrast, for sequences (IEnumerable) recomputation happens each time an enumerator is created and the sequence traversed.

LazyLists can represent cached, potentially-infinite computations. Because they are cached they may cause memory leaks if some active code or data structure maintains a live reference to the head of an infinite or very large lazy list while iterating it, or if a reference is maintained after the list is no longer required.

Lazy lists may be matched using the LazyList.Cons and LazyList.Nil active patterns. These may force the computation of elements of the list.

NonEmptyList<'T>
PersistentHashMap<'T, 'S>

A Map is a collection that maps keys to values. Hash maps require keys that correctly support GetHashCode and Equals. Hash maps provide fast access (log32N hops). count is O(1).

PersistentVector<'T>

PersistentVector is an ordered linear structure implementing the inverse of the List signature, (last, initial, conj) in place of (head, tail, cons). Length is O(1). Indexed lookup or update (returning a new immutable instance of Vector) of any element is O(log32n), which is close enough to O(1) as to make no practical difference: a PersistentVector containing 4 billion items can lookup or update any item in at most 7 steps. Ordering is by insertion history. The original idea can be found in Clojure.

Queue<'T>

Queue is an ordered linear data structure where elements are added at the end (right) and inspected and removed at the beginning (left). Ordering is by insertion history. The qualities of the Queue structure make elements first in, first out (fifo). "head" inspects the first or left-most element in the structure, while "conj" inserts an element at the end, or right of the structure. Purely functional (immutable) Queue based on Okasaki's batched queue.

RandomAccessList<'T>

RandomAccessList is an ordered linear structure implementing the List signature (head, tail, cons), as well as inspection (lookup) and update (returning a new immutable instance) of any element in the structure by index. Length is O(1). Indexed lookup or update (returning a new immutable instance of RandomAccessList) of any element is O(log32n), which is close enough to O(1) as to make no practical difference: a RandomAccessList containing 4 billion items can lookup or update any item in at most 7 steps. Ordering is by insertion history. While PersistentVector<'T> is appending to the end this version prepends elements to the list.

ModuleDescription
Array

Extensions for F#'s Array module.

ByteString
DList
Deque
Heap
Interfaces
LazyList
List

Extensions for F#'s List module.

Literals
Map

Extensions for F#'s Map module.

PersistentHashMap

Defines functions which allow to access and manipulate PersistentHashMaps.

PersistentVector

Defines functions which allow to access and manipulate PersistentVectors.

PriorityQueue
Queue
RandomAccessList

Defines functions which allow to access and manipulate RandomAccessLists.

ResizeArray

Generic operations on the type System.Collections.Generic.List, which is called ResizeArray in the F# libraries.

Seq

Extensions for F#'s Seq module.

FSharpx.Collections.Experimental Namespace

TypeDescription
AltBinRndAccList<'T>
BKTree<'T>
BankersDeque<'T>
BankersQueue<'T>
BatchedDeque<'T>
BatchedQueue<'T>
BinaryRandomAccessList<'T>
BinaryRoseTree<'T>

Multi-way tree, also known as rose tree. This RoseTree uses a Vector for the children RoseTree forest. Adapted from @mausch F# adaptation of Experimental.RoseTree.

BinaryTree<'T>

A simple binary tree

BinaryTreeZipper<'T>

The zipper datastructure for binary trees

BinomialHeap<'T>
BinomialTree<'T>
BlockResizeArray<'T>

Resize array fith fixed size block memory allocation. Provide more optimal space usage for huge arrays than standard ResizeArray. Basic version created by Avdyukhin Dmitry dimonbv@gmail.com As evidenced by the tests that cannot run in mono, and pending destabilizing tests, beware that this data structure can be destabilizing to your assembly.

BootstrappedQueue<'T>
DList<'T>

The DList is an implementation of John Hughes' append list. See http://dl.acm.org/citation.cfm?id=8475 for more information. This implementation adds an additional parameter to allow a more efficient calculation of the list length. Note that an alternate form would represent the DList as: type DList<'T> = DList of ('T list -> 'T list) An example can be found at http://stackoverflow.com/questions/5324623/functional-o1-append-and-on-iteration-from-first-element-list-data-structure/5327209#5327209

Deque<'T>
Digit<'T>
EagerRoseForest<'T>
EagerRoseTree<'T>

Multi-way tree, also known as rose tree. This RoseTree uses a List for the children RoseTree forest. Adapted from @mausch F# adaptation of Experimental.RoseTree.

HoodMelvilleQueue<'T>
ImplicitQueue<'T>
IncompatibleMerge
IndexedRoseTree<'T>

Multi-way tree, also known as rose tree. This RoseTree uses a Vector for the children RoseTree forest. Adapted from @mausch F# adaptation of Experimental.RoseTree.

IntMap<'T>
KeyValuePair<'TKey, 'TValue>
LeftistHeap<'T>
ListZipper<'T>

A zipper for lists

NonEmptyBootstrappedQueue<'T>
PairingHeap<'T>

PairingHeap performs extremely well in practice, however (according to Okasaki) it should be avoided for applications taking advantage of persistence. Also according to Okasaki the time complexity of the heap functions in the PairingHeap implementation have "resisted" time complexity analysis. ofSeq: superior performance; insert: superior performance; tail: superior performance

PatternMatchedBug
PhysicistQueue<'T>
RealTimeDeque<'T>
RealTimeQueue<'T>
RingBuffer<'T>
RoseTree<'T>

Multi-way tree, also known as rose tree.

RotationState<'T>
SkewBinaryRandomAccessList<'T>
SkewBinomialHeap<'T>

A SkewBinomialHeap is a priority queue where elements are inserted in any order, using "insert" and are extracted in either ascending or descending order using "head", "peek", "tail", "pop" or any of their "try" variants. The main advantage of the SkewBinomialHeap over the BinomialHeap is that it supports insertions in constant time O(1). (Based on "Purely Functional Data Structures" - 1996 by Chris Okasaki)

TreeBRAL<'T>
TreeBRALDigit<'T>
TreeDirection
TreeSBRAL<'T>
ModuleDescription
AltBinaryRandomAccessList
BKTree
BankersDeque
BankersQueue
BatchedDeque
BatchedQueue
BinaryRandomAccessList
BinaryRoseTree
BinaryTreeZipper

TreeZipper original implementation taken from http://blog.xquant.net/?p=156

BinomialHeap
BlockResizeArray
BootstrappedQueue

bootstrapped queue from Chris Okasaki’s “Purely functional data structures” original implementation taken from http://lepensemoi.free.fr/index.php/2010/02/18/bootstrapped-queue

BottomUpMergeSort
ChampHashMap
DList
Deque
FlatList
HeapPriorityQueue
HoodMelvilleQueue
ImplicitQueue

implicit queue from Chris Okasaki’s “Purely functional data structures” original implementation taken from http://lepensemoi.free.fr/index.php/2010/02/18/implicit-queue

IndexedRoseTree
IntMap
LeftistHeap
ListZipper
PairingHeap
PhysicistQueue
RealTimeDeque
RealTimeQueue

RealTime queue from Chris Okasaki’s "Purely functional data structures" original implementation taken from http://lepensemoi.free.fr/index.php/2010/01/07/real-time-queue

RingBuffer
SkewBinaryRandomAccessList
SkewBinomialHeap

FSharpx.Collections.Mutable Namespace

FSharpx.Collections.Tagged Namespace

TypeDescription
MapTree<'Key, 'T>
SetTree<'T>
Fork me on GitHub