The FSharpx.Collections namespace now provides a collection of linear data structures deriving from the List signature. To emphasize the unity of the collection I implemented a standardized nomenclature expanding on the List value names. This is not without controversy. Structures like Queue are well-known in other (mostly imperative) languages, but I believe together these structures exhibit more similarities than differences, and bringing them all together in one F# collection is an opportunity to emphasize that logical unity.

My intent was to expand the List signature nomenclature with the naming standard favored by Okasaki, but “init” as the name for the inverse of “tail” would not do as this conflicts with a List module value. So this value is named “initial”. And I made one other change from Okasaki. In recognition of Steffen Forkmann’s F# implementation of the Vector structure from Clojure being the basis of two structures in this collection (Vector and RandomAccessList), I have opted to name the end-insertion function/member “conj” instead of “snoc”.

The List-like Immutable Data Structures

The following structures provide features perhaps available from List and Array, but not efficiently implemented and/or not in the right combination for a particular task, and the full composability and immutability you expect from purely functional data structures.

Deque (Double-ended queue) is an ordered 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. Ordering is by insertion history.

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.

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.

LazyList is an ordered linear structure implementing the List signature (head, tail, cons), but unlike the other linear structures computation of elements is delayed, executed once on demand, and thereafter cached. Adapted from the PowerPack implementation with the List signature values available from within the type class.

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.

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. Ordering is by insertion history.

Vector is an ordered linear structure implementing the inverse of the List signature, (last, initial, conj) in place of (head, tail, cons). Indexed lookup or update (returning a new immutable instance of Vector) of any element is O(log32n) — just about O(1). Length is O(1). Ordering is by insertion history.

Comparing Performance

I recently posted a performance preview of the Queue data structure. Here are the performance benchmarks across the list-like structures, including List and Array from the Microsoft.FSharp.Collections namespace for comparison.

Times are milliseconds on a 2.2GHz 4GB dual core 64-bit Windows 7 machine. Orders of magnitude represent either the beginning or resulting number of elements in the structure. Milliseconds is derived by dividing ticks by 10,000. More on the benchmarking methodology can be found here. The data structure benchmark application can be found here.

Add elements to empty structure

Comments

1) Depending on the structure’s signature by invoking cons or conj using seq.fold.

2) Source data is an ascending ordered integer array, except where noted.

3) Note that repeatedly adding an element to an existing array does not scale.

4) (*) I had trouble getting any Deque benchmarks at scale 1M to complete in reasonable time and have yet to establish whether this is a problem with my benchmark infrastructure or the Deque implementation or a combination thereof.

Initialize structure

Comments

1) Using the respective module’s ofSeq, or different function where indicated.

2) Source data is an ascending ordered integer array, except where noted.

3) Queue and Deque both support O(1) ofList which would load from a list in a fraction of a millisecond.

Peek and Dequeue until the structure is empty

Comments

1) Inspects element with either head or last and recursively takes tail or initial, depending on structure signature.

Use IEnumerable to iterate through each element

Reverse

Append

Comments

1) Using merge for the Heap structure.

Iterate by index

Random lookup (10,000)

Random update (10,000)

Implementation Notes

1) I borrowed the structural equality implementation from Vector for the other structures. Heap perhaps does not need to used Unckecked.equals, but I have not profiled that option to see whether it would actually improve performance. More attention to equality checks taking advantage of internal structure may prove to be somewhat more efficient.

2) The structural equality implementation puts an internal mutable reference value in each structure that gets updated at most once per lifetime. I don’t think this will impede multi-threading use of the structures, but I don’t know for sure either.

3) As noted above there may be issues with Deque at scales >>100K elements. Another Deque in the “experimental” DataStructures namespace may meet the needs of your application better.

There are some useful additions to the F# tool-belt coming up. Microsoft recently released a preview edition of immutable collections, and if all goes as planned I will release a suite of 6 purely functional linear data structures to FSharpx.Collections in just a couple of days.

Queue is a data structure that needs better representation in the functional world, and both collections make contributions, so this is an opportunity to do some performance comparisons of the queues available to F# programmers. The contenders are two queues from the .NET Framework, System.Collections.Generic.Queue and System.Collections.Concurrent.Queue, the upcoming FSharpx.Collections.Queue, and FSharpx.Datastructures.BatchedQueue, from which FSharpx.Collections.Queue was developed.

The first benchmark exercises something like “real world” usage of the queues with the following steps:

1) enqueue the number of elements indicated

2) peek and dequeue half that number

3) enqueue the same number to the resulting queue

4) peek and dequeue half the resulting size of that queue

5) enqueue one more time the original number

(Milliseconds on a 2.2GHz 4GB dual core 64-bit Windows 7 machine)

And then the obligatory “not so real world” benchmarks

Enqueue the indicated number of elements

Peek and Dequeue until the queue is empty

Initialize from a sequential source (an array unless otherwise indicated)

(The preview Immutable.Queue does not yet implement this capability.)

Use IEnumerable to iterate through each element

(queue of indicated size)

So which Queue is right for You?

That of course depends on your application. For raw speed the system generic queue is hard to beat. The concurrent queue compares well against generic in all categories in a single-threaded environment, so for raw speed it should be a contender in multi-threaded environments, unless composability and immutability is preferred.

Preview Immutable.Queue seems primarily intended for the C# world, but has adequate composability to make it suitable for F#. FSharpx.Collections.Queue performs just as well (sometimes better), and has a broader range of supporting functions including fold, foldback, reverse (usually O(1), worst case O(n)), ofSeq, and ofList.