Safe Haskell | Safe |
---|

A vector clock implementation in terms of simply-linked lists.

- data VectorClock a b
- empty :: VectorClock a b
- singleton :: a -> b -> VectorClock a b
- fromList :: Ord a => [(a, b)] -> VectorClock a b
- null :: VectorClock a b -> Bool
- size :: VectorClock a b -> Int
- member :: Ord a => a -> VectorClock a b -> Bool
- lookup :: Ord a => a -> VectorClock a b -> Maybe b
- toList :: VectorClock a b -> [(a, b)]
- insert :: Ord a => a -> b -> VectorClock a b -> VectorClock a b
- inc :: (Ord a, Num b) => a -> VectorClock a b -> Maybe (VectorClock a b)
- incWithDefault :: (Ord a, Num b) => a -> VectorClock a b -> b -> VectorClock a b
- delete :: Ord a => a -> VectorClock a b -> VectorClock a b
- combine :: (Ord a, Ord b) => (a -> Maybe b -> Maybe b -> Maybe b) -> VectorClock a b -> VectorClock a b -> VectorClock a b
- max :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> VectorClock a b
- data Relation
- = Causes
- | CausedBy
- | Concurrent

- relation :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> Relation
- causes :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> Bool
- valid :: (Ord a, Ord b) => VectorClock a b -> Bool

# Usage example

To create a vector clock, start from `empty`

and `insert`

elements
into it. As a shortcut, `fromList`

just inserts all the elements
in a list, in order.

let vc = empty in let vc' = insert 'a' 1 vc in let vc'' = insert 'b' 2 vc in vc'' == fromList [('a', 1), ('b', 2)]

Note that, *for different keys*, the order of insertion does not
matter:

fromList [('a', 1), ('b', 2)] == fromList [('b', 2), ('a', 1)]

Once you have a given vector clock, you can `lookup`

its fields,
check that keys are `member`

s, or convert it back `toList`

form.

lookup 'a' [('a', 1), ('b', 2)] == Just 1 lookup 'c' [('a', 1), ('b', 2)] == Nothing

The main operations that you would do with a vector clcok are to
`inc`

crement the entry corresponding to the current process and to
update the process's vector clock with the `max`

of its and the
received message's clocks.

inc 'a' [('a', 1), ('b', 2)] = Just [('a', 2), ('b', 2)] max [('a', 1), ('b', 2)] [('c', 3), ('b', 1)] == [('a', 1), ('b', 2), ('c' 3)]

Finally, upon receiving different messages, you may wish to
discover the `relation`

ship, if any, between them. This
information could be useful in determining the correct order to
process the messages.

relation (fromList [('a', 1), ('b', 2)]) (fromList [('a', 2), ('b', 2)]) == Causes relation (fromList [('a', 2), ('b', 2)]) (fromList [('a', 1), ('b', 2)]) == CausedBy relation (fromList [('a', 2), ('b', 2)]) (fromList [('a', 1), ('b', 3)]) == Concurrent

# Vector clock type

data VectorClock a b Source

A vector clock is, conceptually, an associtive list sorted by the value of the key, where each key appears only once.

(Eq a, Eq b) => Eq (VectorClock a b) | |

(Show a, Show b) => Show (VectorClock a b) | |

(Binary a, Binary b) => Binary (VectorClock a b) |

# Construction

empty :: VectorClock a bSource

*O(1)*. The empty vector clock.

singleton :: a -> b -> VectorClock a bSource

*O(1)*. A vector clock with a single element.

fromList :: Ord a => [(a, b)] -> VectorClock a bSource

*O(N)*. Insert each entry in the list one at a time.

# Query

null :: VectorClock a b -> BoolSource

*O(1)*. Is the vector clock empty?

size :: VectorClock a b -> IntSource

*O(N)*. The number of entries in the vector clock.

member :: Ord a => a -> VectorClock a b -> BoolSource

*O(N)*. Is the given key a key in an entry of the vector clock?

lookup :: Ord a => a -> VectorClock a b -> Maybe bSource

*O(N)*. Lookup the value for a key in the vector clock.

toList :: VectorClock a b -> [(a, b)]Source

*O(1)*. All the entries in the vector clock. Note that this is
*not* the inverse of `fromList`

.

# Insertion

insert :: Ord a => a -> b -> VectorClock a b -> VectorClock a bSource

*O(N)*. Insert or replace the entry for a key.

inc :: (Ord a, Num b) => a -> VectorClock a b -> Maybe (VectorClock a b)Source

*O(N)*. Increment the entry for a key.

incWithDefault :: (Ord a, Num b) => a -> VectorClock a b -> b -> VectorClock a bSource

*O(N)*. Increment the entry for a key. If the key does not
exist, assume it was the default.

# Deletion

delete :: Ord a => a -> VectorClock a b -> VectorClock a bSource

*O(N)*. Delete an entry from the vector clock. If the requested
entry does not exist, does nothing.

# Merges

combine :: (Ord a, Ord b) => (a -> Maybe b -> Maybe b -> Maybe b) -> VectorClock a b -> VectorClock a b -> VectorClock a bSource

*O(max(N, M))*. Combine two vector clocks entry-by-entry.

max :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> VectorClock a bSource

*O(max(N, M))*. The maximum of the two vector clocks.

# Relations

The relations two vector clocks may find themselves in.

relation :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> RelationSource

*O(min(N, M))*. The relation between the two vector clocks.

causes :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> BoolSource

*O(min(N, M))*. Short-hand for `relation vc1 vc2 == Causes`

.