# FSharpx.Collections

## FSharpx.Collections Namespace

Type | Description |

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

Module | Description |

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

Type | Description |

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

## FSharpx.Collections.Mutable Namespace

## FSharpx.Collections.Tagged Namespace

Type | Description |

MapTree<'Key, 'T> | |

SetTree<'T> |