Persistent vectors, Part 1 -- The landscape
This is the first of a series of posts on the design and implementation of PersistentVector
, an immutable, persistent vector class supporting a transient mode for efficient batch operations.
To warm up, let’s look at what we’re aiming for.
The goal
The set of interfaces to implement is a good place to start. A little picture might help:
IPersistentVector
is our goal.
That means we will be implementing all of
Seqable
IPersistentCollection
ILookup
Associative
Sequential
IPersistentStack
(*)Reversible
(*)Counted
Indexed
(*)IPersistentVector
(*)IEditableCollection
(*)IKVReduce
(*)IMappedEnumerable
(*)IMappedEnumerableTyped
(*)IChunkedSeq
IObj
(*)IMeta
(*)IFn
Some of these we’ve seen before. The starred ones we’ve not talked about.
The interfaces of greatest importance are mentioned in IPersistentVector
:
[<AllowNullLiteral>]
type IPersistentVector =
inherit Associative
inherit Sequential
inherit IPersistentStack
inherit Reversible
inherit Indexed
abstract length: unit -> int
abstract assocN: i: int * value: obj -> IPersistentVector
abstract cons: o: obj -> IPersistentVector
abstract count: unit -> int
The new ones here are
[<AllowNullLiteral>]
type Indexed =
inherit Counted
abstract nth: i: int -> obj
abstract nth: i: int * notFound: obj -> obj
This interface provides indexing, i.e., access to vector elements by integer index. Counted
you’ve seen already.
Reversible
just provides for sequencing in reverse order:
[<AllowNullLiteral>]
type Reversible =
abstract rseq: unit -> ISeq
IPersistentStack
allows the vector be treated like a stack, with the highest-indexed element being the top of the stack. We can peek
at the top element, or we can pop
the stack. pop
does not return the element on the top of the stack. Rather, it returns a new PersistentVector
that is missing the top element of the original. This is the nature of having an immutable structure – we can’t modify it to exclude the top element but must create a new object.
[<AllowNullLiteral>]
type IPersistentStack =
inherit IPersistentCollection
abstract peek: unit -> obj
abstract pop: unit -> IPersistentStack
Wnat about pushing a new item onto the vector-as-stack? That’s the cons
operation, part of IPersistentVector
.
What we consider standard operations for a vector are accomplished thus:
v.nth(i)
– access the i-th elementv.assocN(i,newValue)
– assign a new value to the i-th element. (A new vector is returned.)v.cons(o)
– create a vector with a new element added at the top endv.pop()
– create a new vector with the top element removed.
IMeta
and IObj
allow for metadata (an IPersistentMap
) to be associated with an object and for a new object with new metadata to be created. In face, PersistentList
and some others also support it. I’ve just not wanted to take the time to talk about it.
[<AllowNullLiteral>]
type IMeta =
abstract meta: unit -> IPersistentMap
[<AllowNullLiteral>]
type IObj =
inherit IMeta
abstract withMeta: meta: IPersistentMap -> IObj
I still don’t want to take time to talk about. The implementations are pretty much all the same. I’ll cover it at some point.
IKVReduce
is a form of IReduceinit
where the function take the previous value and a key and value (key here is the index). Given our previous coverage of IReduce(Init)
, there’s nothing to learn here.
IEditableCollection
relates to transient collections. That will get its own post.
Enough of the general picture. Time to dig in.