Sequence

This is a prototype of a CRDT for sequential data written in Elm.

Work in progress! Use with caution.

Implementation stems from Nedelec et al. "LSEQ: an adaptive structure for sequences in distributed collaborative editing" (2013).

Definition

type Sequence a

The data type itself. Takes a user-defined type as its value type.

type Path

The unique identifier of a Entry's position in the sequence. It's called "path" because the data type consists of multiple layers comparable to a filesystem's directories. A path to a value works like a path to a file.

type alias Op b =

{ origin : String

, target : String

, path : Path

, op : Operation b

}

The complete self-contained op(eration). origin is the identifier for the creating user/instance. If the Entry at path already contains a MVR apply the operation at target's value.

type Entry a

= Single String (Value a)

| Concurrent (MVR a)

An entry in the sequence might be a single value (just one user applied an operation on it) or a multi-value registry (MVR) in case multiple users a applied operation at this path.

type Value a

= Value a

| Tomb (TombValue a)

The actual value. After applying an Insert operation it is Value a, after a Remove operation it is a Tomb (TombValue a). So storage of removed values never gets freed.

type TombValue a

= TombValue a

| TombUnknown

If a remove operation is applied at a path which has a value, it's turned into Tomb (TombValue a). If the operation is applied on a free path it becomes TombUnknown. If an insert operation is applied after this, it's turned into TombValue a finally. This way it does not matter in which order insert and remove operation are applied.

type Operation a

= Insert a

| Remove

All data manipulation happens through Operations. It either is an Insert a or Remove.

type MVR a

A multi-value registry is a dictionary of user identifiers and Values. Get its contents with mvrToList.

Operations

alloc : Path -> Path -> Path

Allocate a path given it's lower and upper bounds (non-inclusive). The bounds should be paths that are already taken and the possible path's between should all be free.

createInsert : String -> Path -> a -> Op a

Create an insert operation. Pass it the user identifier, a path and the value to insert.

createRemove : String -> String -> Path -> Op a

Create a remove operation. Pass it the removing user's identifier, the user identifier of the removed value (ie. to target it in a MVR) and the path.

apply : List (Op a) -> Sequence a -> ( Sequence a, List (Op a) )

Apply multiple ops at once to a sequence. Returns the updated sequence and list of successful operations (which actually changed something).

Sequence handling

empty : Sequence a

An empty sequence.

get : Path -> Sequence a -> Maybe (Entry a)

Lookup an entry at the given path.

first : Sequence a -> Maybe ( Path, Entry a )

Return the first entry of the sequence and its path. If the sequence is empty returns Nothing.

last : Sequence a -> Maybe ( Path, Entry a )

Return the last entry of the sequence and its path. If the sequence is empty returns Nothing.

after : Path -> Sequence a -> Maybe ( Path, Entry a )

Return the entry and its path after the given path in the sequence. Returns Nothing if there none.

before : Path -> Sequence a -> Maybe ( Path, Entry a )

Return the entry and its path before the given path in the sequence. Returns Nothing if there none.

foldl : (Path -> Entry a -> b -> b) -> b -> Sequence a -> b

Fold a sequence from the left.

foldr : (Path -> Entry a -> b -> b) -> b -> Sequence a -> b

Fold a sequence from the right.

MVR handling

mvrToList : MVR a -> List ( String, Value a )

Inspect an MVR by turning it into a list of tuples of the user identifier and the Value.

Decoders

decodeOp : Decoder a -> Decoder (Op a)

Decode an Op.

encodeOp : (a -> Value) -> Op a -> Value

Encoder an Op given an value specific encoder.

Constants

minPath : Path

The lowest path possible

maxPath : Path

The greatest path possible

Modules

Sequence

brightdb/sequence/1.0.0