| Safe Haskell | Trustworthy |
|---|---|
| Language | Haskell98 |
Data.VectorClock.Approximate
Description
An approximate vector clock implementation in terms of Data.VectorClock.Simple.
- data VectorClock a b
- empty :: Int -> VectorClock a b
- singleton :: Hashable a => Int -> a -> b -> VectorClock a b
- fromList :: Hashable a => Int -> [(a, b)] -> VectorClock a b
- toList :: VectorClock a b -> [(Int, b)]
- null :: VectorClock a b -> Bool
- size :: VectorClock a b -> Int
- member :: Hashable a => a -> VectorClock a b -> Bool
- lookup :: Hashable a => a -> VectorClock a b -> Maybe b
- insert :: Hashable a => a -> b -> VectorClock a b -> VectorClock a b
- inc :: (Hashable a, Num b) => a -> VectorClock a b -> Maybe (VectorClock a b)
- incWithDefault :: (Hashable a, Num b) => a -> VectorClock a b -> b -> VectorClock a b
- delete :: Hashable a => a -> VectorClock a b -> VectorClock a b
- combine :: Ord b => (Int -> Maybe b -> Maybe b -> Maybe b) -> VectorClock a b -> VectorClock a b -> VectorClock a b
- max :: Ord b => VectorClock a b -> VectorClock a b -> VectorClock a b
- diff :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> Maybe (VectorClock a b)
- data Relation
- = Causes
- | CausedBy
- | Concurrent
- relation :: Ord b => VectorClock a b -> VectorClock a b -> Relation
- causes :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> Bool
- valid :: Ord b => VectorClock a b -> Bool
Usage example
See Data.VectorClock.Simple for a more detailed example of using vector clock.
An approximate vector clock, is like a normal one, but maps multiple keys to the same entry. Concretely, this is done by first hashing the keys, then using them modulo the vector clock's size. So, an approximate vector clock of size 1 would map all the keys to the same entry; an approximate vector clock of size 2 would map roughly half its keys to the first entry, and half to the second entry.
To create an approximate vector clock, start from empty and
insert elements into it. As a shortcut, fromList just inserts
all the elements in a list, in order. You must also specify the
vector clock's maximum size when creating it. Experimental results
suggest that small maximum sizes (e.g. 3 or 4) will yield good
resulsts in practice. Higher maximum sizes will have no adverse
effects, and will effectively turn approximate vector clocks into
normal ones.
let vc = empty 4 in
let vc' = insert 'a' 1 vc in
let vc'' = insert 'b' 2 vc in
vc'' == fromList 4 [('a', 1), ('b', 2)]Vector clock type
data VectorClock a b Source #
An approximate vector clock is a normal vector clock, but several
keys are mapped to the same value. This can lead to false
positive relations. In other words, the fact that one vector
clock causes another is no longer enough information to say that
one message causes the other. That said, experimental results show
that approximate vector clocks have good results in practice; see
the paper by R. Baldoni and M. Raynal for details.
Instances
| Functor (VectorClock a) Source # | |
| Foldable (VectorClock a) Source # | |
| Traversable (VectorClock a) Source # | |
| Eq b => Eq (VectorClock a b) Source # | |
| (Data a, Data b) => Data (VectorClock a b) Source # | |
| Show b => Show (VectorClock a b) Source # | |
| Generic (VectorClock a b) Source # | |
| Binary b => Binary (VectorClock a b) Source # | |
| type Rep (VectorClock a b) Source # | |
Construction
Arguments
| :: Int | size: the maximum number of entries in the vector clock |
| -> VectorClock a b |
O(1). The empty vector clock.
Arguments
| :: Hashable a | |
| => Int | size: the maximum number of entries in the vector clock |
| -> a | key: the key for the entry |
| -> b | value: the value for the entry |
| -> VectorClock a b |
O(1). A vector clock with a single element.
Arguments
| :: Hashable a | |
| => Int | size: the maximum number of entries in the vector clock |
| -> [(a, b)] | entries: the entries to insert in the newly created vector clock |
| -> VectorClock a b |
O(N). Insert each entry in the list one at a time.
toList :: VectorClock a b -> [(Int, b)] Source #
O(1). All the entries in the vector clock. Note that this is
not the inverse of fromList. Note that the keys are returned
hashed.
Query
null :: VectorClock a b -> Bool Source #
O(1). Is the vector clock empty?
size :: VectorClock a b -> Int Source #
O(N). The number of entries in the vector clock. Note that this may be less than the size at construction.
member :: Hashable a => a -> VectorClock a b -> Bool Source #
O(N). Is the given key a key in an entry of the vector clock?
lookup :: Hashable a => a -> VectorClock a b -> Maybe b Source #
O(N). Lookup the value for a key in the vector clock.
Insertion
insert :: Hashable a => a -> b -> VectorClock a b -> VectorClock a b Source #
O(N). Insert or replace the entry for a key.
inc :: (Hashable a, Num b) => a -> VectorClock a b -> Maybe (VectorClock a b) Source #
O(N). Increment the entry for a key.
Arguments
| :: (Hashable a, Num b) | |
| => a | key: the key of the entry |
| -> VectorClock a b | vc: the vector clock |
| -> b | default: if the key is not found, assume its value was the default and increment that |
| -> VectorClock a b |
O(N). Increment the entry for a key. If the key does not exist, assume it was the default.
Deletion
delete :: Hashable a => a -> VectorClock a b -> VectorClock a b Source #
O(N). Delete an entry from the vector clock. If the requested entry does not exist, does nothing.
Merges
Arguments
| :: Ord b | |
| => (Int -> Maybe b -> Maybe b -> Maybe b) | a function that takes the hashed key, the value of the entry in the left hand vector clock, if it exists, the value in the right hand vector clock, if it exists, and, if it wishes to keep a value for this key in the resulting vector clock, returns it. |
| -> VectorClock a b | lhs: the left hand vector clock |
| -> VectorClock a b | rhs: the right hand vector clock |
| -> VectorClock a b |
O(max(N, M)). Combine two vector clocks entry-by-entry. The size of the resulting vector clock is the maximum of the sizes of the given ones.
max :: Ord b => VectorClock a b -> VectorClock a b -> VectorClock a b Source #
O(max(N, M)). The maximum of the two vector clocks.
diff :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> Maybe (VectorClock a b) Source #
O(M). If vc2 , compute the smallest causes vc1vc3
s.t. max vc3 vc2 == vc1. Note that the first parameter is the
newer vector clock.
Relations
The relations two vector clocks may find themselves in.
Constructors
| Causes | |
| CausedBy | |
| Concurrent |
relation :: Ord b => VectorClock a b -> VectorClock a b -> Relation Source #
O(min(N, M)). The relation between the two vector clocks.
causes :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> Bool Source #
O(min(N, M)). Short-hand for relation vc1 vc2 == Causes.