PersistentVector

A Vector is a collection of values indexed by contiguous integers. Vectors support access to items by index in log32N hops. count is O(1). conj puts the item at the end of the vector. More details can be found in the API docs.

open FSharpx.Collections

// Create a new PersistentVector and add some items to it
let v = 
    PersistentVector.empty 
    |> PersistentVector.conj "hello"
    |> PersistentVector.conj "world"
    |> PersistentVector.conj "!"

seq ["hello"; "world"; "!"]

// lookup some items
PersistentVector.nth 0 v

"hello"

PersistentVector.nth 1 v

"world"

v.[2]

"!"

// Check no. of elements in the PersistentVector
PersistentVector.length v

3

PersistentVectors are immutable and therefor allow to create new version without destruction of the old ones.

let v' = 
    v
    |> PersistentVector.conj "!!!" 
    |> PersistentVector.update 0 "hi" // replace existing value

PersistentVector.nth 0 v'

"hi"

PersistentVector.nth 3 v'

"!!!"

PersistentVector.nth 0 v

"hello"

PersistentVector.length v

3

PersistentVector.length v'

4

// remove the last element from a PersistentVector
let v'' = PersistentVector.initial v'

PersistentVector.length v''

3

There a couple of interesting operations on PersistentVectors:

// Convert a sequence of values to a PersistentVectors
let intVector = 
    PersistentVector.ofSeq [1..10]

seq [1; 2; 3; 4; ...]

// Square all values in a PersistentVector
let intVector' = 
    PersistentVector.map (fun x -> x * x) intVector
intVector'.[3]

16

Using from C#

A Vector is a collection of values indexed by contiguous integers. Vectors support access to items by index in log32N hops. Count is O(1). Conj puts the item at the end of the vector.

// Create an empty PersistentVector and add some elements
PersistentVector<string> vector =
    PersistentVector<string>.Empty()
        .Conj("hello")
        .Conj("world")
        .Conj("!");

Console.WriteLine(vector[0]); // hello
Console.WriteLine(vector[2]); // !            

// Check no. of elements in the PersistentVector
Console.WriteLine(vector.Length);  // 3

PersistentVectors are immutable and therefor allow to create new version without destruction of the old ones.

PersistentVector<string> vector2 = vector.Conj("!!!").Update(0,"hi");

Console.WriteLine(vector2[0]); // hi
Console.WriteLine(vector[0]);  // hello
Console.WriteLine(vector2[3]); // !!!

Console.WriteLine(vector.Length);  // 3
Console.WriteLine(vector2.Length); // 4

// remove the last element from a PersistentVector
PersistentVector<string> vector3 = vector2.Initial;

Console.WriteLine(vector3.Length); // 3

Performance Tests

Bulk operations on PersistentVector use an internal TransientVector in order to get much better performance. The following scripts shows this:

open FSharpx.Collections

let trials = 5
let r = new System.Random()

let initArrayAndVectorFromList n =
    sprintf "Init with n = %d" n |> printInFsiTags
    let list = [for i in 1..n -> r.Next()]

    let initvector list = 
        let v = ref PersistentVector.empty
        for x in list do
            v := PersistentVector.conj x !v
        !v

    averageTime trials "  Array.ofSeq" 
        (fun () -> Array.ofSeq list)

    averageTime trials "  Multiple PersistentVector.conj" 
        (fun () -> initvector list)

    averageTime trials "  PersistentVector.ofSeq" 
        (fun () -> PersistentVector.ofSeq list)

let lookupInArrayAndVector n count =
    sprintf "%d Lookups in size n = %d" count n |> printInFsiTags
    let list = [for i in 1..n -> r.Next()]
    let array = Array.ofSeq list
    let vector = PersistentVector.ofSeq list

    averageTime trials "  Array" 
        (fun () -> for i in 1..count do array.[r.Next n])

    averageTime trials "  PersistentVector" 
        (fun () -> for i in 1..count do PersistentVector.nth (r.Next n) vector)


let replaceInArrayAndVector n count =
    sprintf "%d writes in size n = %d" count n |> printInFsiTags
    let list = [for i in 1..n -> r.Next()]
    let array = Array.ofSeq list
    let vector = PersistentVector.ofSeq list

    averageTime trials "  Array" 
        (fun () -> for i in 1..count do array.[r.Next n] <- r.Next())

    averageTime trials "  PersistentVector" 
        (fun () -> for i in 1..count do PersistentVector.update (r.Next n) (r.Next()) vector)

initArrayAndVectorFromList 10000
initArrayAndVectorFromList 100000
initArrayAndVectorFromList 1000000

[fsi:Init with n = 10000]
 [fsi:  Array.ofSeq 0.0ms]
 [fsi:  Multiple PersistentVector.conj 2.4ms]
 [fsi:  PersistentVector.ofSeq 0.8ms]
 [fsi:Init with n = 100000]
 [fsi:  Array.ofSeq 0.4ms]
 [fsi:  Multiple PersistentVector.conj 26.4ms]
 [fsi:  PersistentVector.ofSeq 9.4ms]
 [fsi:Init with n = 1000000]
 [fsi:  Array.ofSeq 8.2ms]
 [fsi:  Multiple PersistentVector.conj 334.4ms]
 [fsi:  PersistentVector.ofSeq 131.2ms]

lookupInArrayAndVector 10000 10000
lookupInArrayAndVector 100000 10000
lookupInArrayAndVector 1000000 10000

[fsi:10000 Lookups in size n = 10000]
 [fsi:  Array 0.0ms]
 [fsi:  PersistentVector 0.4ms]
 [fsi:10000 Lookups in size n = 100000]
 [fsi:  Array 0.0ms]
 [fsi:  PersistentVector 0.8ms]
 [fsi:10000 Lookups in size n = 1000000]
 [fsi:  Array 0.2ms]
 [fsi:  PersistentVector 2.8ms]

replaceInArrayAndVector 10000 10000
replaceInArrayAndVector 100000 10000
replaceInArrayAndVector 1000000 10000

[fsi:10000 writes in size n = 10000]
 [fsi:  Array 0.2ms]
 [fsi:  PersistentVector 6.2ms]
 [fsi:10000 writes in size n = 100000]
 [fsi:  Array 0.2ms]
 [fsi:  PersistentVector 10.0ms]
 [fsi:10000 writes in size n = 1000000]
 [fsi:  Array 0.2ms]
 [fsi:  PersistentVector 9.4ms]