GitHub repository of FSharpx.Core.DataStructures
Functional Data Structures in Typed Racket
FSharpx.DataStructures Performance Metrics
BootstrappedQueue
BootstrappedQueue Performance Metrics Observations
Purely Functional
- Generally good create and populate (Init, new(), and AddOne Actions) performance up to scale 106.
- AddOne Action performance relative to Init shows marked slowdown at scale 105.
No constructor, but you can use the only type member NonEmptyBootstrappedQueue.create in a non-obvious way to quickly instantiate from a List.
Should be incorporated into an ofList member.
BootstrappedQueue Docs
module members
”head
Returns first (head) element.
Complexity: O(1)
Usage:
”isEmpty
Queue is empty or not.
Complexity: O(1)
Usage:
”snoc
Add an element to the right (snoc is cons spelled backwards).
Complexity: O(Log* n)
Usage:
”tail
Returns tail element.
Complexity: O(Log* n)
Usage:
”tryGetHead
Returns option tail element.
Complexity: O(1)
Usage:
”tryGetTail
Returns option tail element.
Complexity: O(Log* n)
Usage:
DList
DList Performance Metrics
Observations
Purely Functional
- Init performance always better than AddOne, very noticeable starting at scale 104.
A Difference List, or DList, is an implementation of John Hughes’ append list. 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<'a> = DList of ('a list -> 'a list)
DList Docs
Constructors:
DList has no constructors. Instantiate a DList through one of the DList Module operators.
type members
”Head
Returns first (head) element.
Complexity: O(log n)
Usage:
”IsEmpty
Returns bool indicating match with Nil.
Complexity: O(1)
Usage:
let x = DList.empty
let b = x.IsEmpty
”Length
Returns the number of items in the collection.
Complexity: O(1)
Usage:
”Tail
Returns the DList tail (all elements after the first)
Complexity: O(log n)
Usage:
module members
”append
Complexity: O(1)
Usage:
”cons
Returns a new DList with element added at head.
Complexity:
Usage:
”empty:
Empty DList
Complexity: O(1)
Usage:
”fold
Complexity: O(n)
Usage:
”head
Returns first (head) element.
Complexity: O(log n)
Usage:
”isEmpty
Complexity: O(1)
Usage:
”length
Returns the number of items in the collection.
Complexity: O(1)
Usage:
”ofSeq
Complexity: O(n)
Usage:
”singleton
Complexity: O(1)
Usage:
”tail
Returns the DList tail (all elements after the first)
Complexity: O(log n)
Usage:
Complexity:
Usage:
Complexity:
Usage:
See also:
A novel representation of lists and its application to the function “reverse”
Functional O(1) append and O(n) iteration from first element list data structure
ImplicitQueue
ImplicitQueue Performance Metrics
Observations
ImplicitQueue Docs
module members
”head
Returns first (head) element.
Complexity: O(1)
Usage:
”isEmpty
Queue is empty or not.
Complexity: O(1)
Usage:
”snoc
Add an element to the right (snoc is cons spelled backwards).
Complexity: O(1)
Usage:
”tail
Returns tail element.
Complexity: O(1)
Usage:
”tryGetHead
Returns option tail element.
Complexity: O(1)
Usage:
”tryGetTail
Returns option tail element.
Complexity: O(1)
Usage:
RealTimeQueue
RealTimeQueue Performance Metrics
Observations
Purely Functional
- Stack overflow at scale 105 in both 64 and 32-bit systems.
- Up to scale 104 AddOne scaling is close to O(1).
- No native Init or new() Action.
RealTimeQueue Docs
module members
”head
Returns first (head) element.
Complexity: O(1)
Usage:
”isEmpty
Queue is empty or not.
Complexity: O(1)
Usage:
”snoc
Add an element to the right (snoc is cons spelled backwards).
Complexity: O(1)
Usage:
”tail
Returns tail element.
Complexity: O(1)
Usage:
”tryGetHead
Returns option tail element.
Complexity: O(1)
Usage:
”tryGetTail
Returns option tail element.
Complexity: O(1)
Usage:
Vector
Persitent Vector Performance Metrics
Transient Vector Performance Metrics
Persitent Vector Observations
Purely Functional
- AddOne Action performance deteriorates at scale 104 or 105.
- Init Action (ofSeq) performance good through scale 105.
Transient Vector Observations
Ported from the Clojure implementation, a Vector is a collection of values indexed by contiguous integers implemented as an immutable hash array mapped trie.
Vector DocsConstructors:
The Vector supports constructors for two underlying types, PersistentVector and TransientVector. If only one reference of the Vecor is to be held, TransientVector mutates the underlying data representation rather than copying on every change (i.e. it is not strictly purely functional).
type members
”AssocN
Returns a new vector (or the modifies the TransientVector) that contains the given value at the index. Index must be <= vector.Count.
Complexity:
Usage:
”Conj
Returns a new vector with the element ‘added’ at the end.
Complexity: O(1)
Usage:
let vP = empty
let vP2 = vP.Conj(4).Conj(5)
”Count
Returns the number of items in the collection.
Complexity: O(1)
Usage:
let vP = empty
let vP2 = vP.Conj(4).Conj(5)
printfn "%i" (vP2.Count())
”Item
Returns the value at the index. If the index is out of bounds it throws an exception.
Complexity: O(log32n)
Usage:
”Peek
Returns the last element in the vector. If the vector is empty it throws an exception.
Complexity: O(1)
Usage:
”Pop
Returns a new vector without the last item. If the collection is empty it throws an exception.
Complexity: O(1)
Usage:
module members
”assocN:
Returns a new vector that contains the given value at the index. Index must be <= vector.Count.
Complexity:
Usage:
”count
Returns the number of items in the collection
Complexity: O(1)
Usage:
”empty:
Empty PersistentVector of type ‘a.
Complexity: O(1)
Usage:
”nth:
Returns the value at the index. If the index is out of bounds it throws an exception.
Complexity: O(1)
Usage:
”cons:
Returns a new vector with the element ‘added’ at the end.
(Unfortunate operator name inherited from the Clojure implementation. Should be renamed to “conj”.)
Complexity:
Usage:
”init:
Creates a PersistentVector by calling the given generator on each index for the count.
Complexity: O(n)
Usage:
”map:
Creates a new PersistentVector whose elements are the results of applying the given function to each of the elements of the Vector.
Complexity: O(n)
Usage:
Creates a new PersistentVector from the given enumerable object.
Complexity: O(n)
Usage:
Returns the last element in the vector. If the vector is empty it throws an exception.
Complexity: O(1)
Usage:
”pop:
Returns a new persistent Vector without the last item, or the same transient vector without the last item. If the collection is empty it throws an exception.
Complexity: O(1)
Usage:
See also:
Porting Clojure’s persistent data structures to .NET part 1 of n – PersistentVector
Porting Clojure’s persistent data structures to .NET part 2 of n – TransientVector