| Safe Haskell | Safe |
|---|
Data.VectorClock.Simple
Contents
Description
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 members, 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
inccrement 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 relationship, 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.
Instances
| (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.
Constructors
| Causes | |
| CausedBy | |
| Concurrent |
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.