fsprojects/FSharpx.Collections


fsprojects/FSharpx.Collections

FSharpx.Collections Namespace

TypeDescription
ByteString

An ArraySegment with structural comparison and equality.

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
Dictionary

Extensions for System.Collections.Generic.Dictionary.

Exceptions
Heap
Interfaces
LazyList
List

Extensions for F#'s List module.

Literals
Map

Extensions for F#'s Map module.

NameValueCollection

Extensions for NameValueCollections.

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

Seq

Extensions for F#'s Seq module.

TimeMeasurement

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.

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

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.

FlatList<'T>
HoodMelvilleQueue<'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>
LeftistHeap<'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>
RingBuffer<'T>
RoseForest<'T>
RoseTree<'T>

Multi-way tree, also known as rose tree.

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

Timeseries<'T>
TreeBRAL<'T>
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
BottomUpMergeSort
DList
Deque
EagerRoseTree
FlatList
HeapPriorityQueue
HoodMelvilleQueue
ImplicitQueue
IndexedRoseTree
IntMap
LeftistHeap
ListZipper

ListZipper original implementation taken from http://learnyouahaskell.com/zippers

PairingHeap
PhysicistQueue
RealTimeDeque
RealTimeQueue
RingBuffer
RoseTree
SkewBinaryRandomAccessList
SkewBinomialHeap

FSharpx.Collections.Mutable Namespace

TypeDescription
CircularBuffer<'T>

Microsoft.FSharp.Collections Namespace

ModuleDescription
ResizeArray

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

Microsoft.FSharp.Collections.Tagged Namespace

TypeDescription
Map<'Key, 'T, 'ComparerTag>
Map<'Key, 'T>
MapTree<'Key, 'T>
Set<'T, 'ComparerTag>
Set<'T>
SetTree<'T>
ModuleDescription
MapTree
SetTree
Fork me on GitHub