Safe Haskell | None |
---|---|

Language | Haskell2010 |

## Synopsis

- data AnchoredSeq v a b where
- pattern Empty :: Anchorable v a b => a -> AnchoredSeq v a b
- pattern (:>) :: Anchorable v a b => AnchoredSeq v a b -> b -> AnchoredSeq v a b
- pattern (:<) :: Anchorable v a b => b -> AnchoredSeq v a b -> AnchoredSeq v a b

- class (Ord v, Bounded v) => Anchorable v a b | a -> v where
- asAnchor :: b -> a
- getAnchorMeasure :: Proxy b -> a -> v

- anchor :: AnchoredSeq v a b -> a
- head :: Anchorable v a b => AnchoredSeq v a b -> Either a b
- headAnchor :: Anchorable v a b => AnchoredSeq v a b -> a
- last :: Anchorable v a b => AnchoredSeq v a b -> Either a b
- toNewestFirst :: AnchoredSeq v a b -> [b]
- toOldestFirst :: AnchoredSeq v a b -> [b]
- fromNewestFirst :: Anchorable v a b => a -> [b] -> AnchoredSeq v a b
- fromOldestFirst :: Anchorable v a b => a -> [b] -> AnchoredSeq v a b
- splitAt :: Anchorable v a b => Int -> AnchoredSeq v a b -> (AnchoredSeq v a b, AnchoredSeq v a b)
- splitAtMeasure :: Anchorable v a b => v -> AnchoredSeq v a b -> (AnchoredSeq v a b, AnchoredSeq v a b)
- dropNewest :: Anchorable v a b => Int -> AnchoredSeq v a b -> AnchoredSeq v a b
- takeOldest :: Anchorable v a b => Int -> AnchoredSeq v a b -> AnchoredSeq v a b
- dropWhileNewest :: Anchorable v a b => (b -> Bool) -> AnchoredSeq v a b -> AnchoredSeq v a b
- takeWhileOldest :: Anchorable v a b => (b -> Bool) -> AnchoredSeq v a b -> AnchoredSeq v a b
- length :: Anchorable v a b => AnchoredSeq v a b -> Int
- null :: AnchoredSeq v a b -> Bool
- contains :: Anchorable v a b => v -> (b -> Bool) -> AnchoredSeq v a b -> Bool
- withinBounds :: Anchorable v a b => v -> (Either a b -> Bool) -> AnchoredSeq v a b -> Bool
- map :: Anchorable v2 a b2 => (b1 -> b2) -> AnchoredSeq v1 a b1 -> AnchoredSeq v2 a b2
- bimap :: Anchorable v2 a2 b2 => (a1 -> a2) -> (b1 -> b2) -> AnchoredSeq v1 a1 b1 -> AnchoredSeq v2 a2 b2
- mapPreservingMeasure :: (b1 -> b2) -> AnchoredSeq v a b1 -> AnchoredSeq v a b2
- bimapPreservingMeasure :: (a1 -> a2) -> (b1 -> b2) -> AnchoredSeq v a1 b1 -> AnchoredSeq v a2 b2
- rollback :: Anchorable v a b => v -> (Either a b -> Bool) -> AnchoredSeq v a b -> Maybe (AnchoredSeq v a b)
- isPrefixOf :: forall v a b. (Eq a, Eq b) => AnchoredSeq v a b -> AnchoredSeq v a b -> Bool
- isPrefixOfByMeasure :: Anchorable v a b => AnchoredSeq v a b -> AnchoredSeq v a b -> Bool
- lookupByMeasure :: Anchorable v a b => v -> AnchoredSeq v a b -> [b]
- splitAfterMeasure :: Anchorable v a b => v -> (Either a b -> Bool) -> AnchoredSeq v a b -> Maybe (AnchoredSeq v a b, AnchoredSeq v a b)
- splitBeforeMeasure :: Anchorable v a b => v -> (b -> Bool) -> AnchoredSeq v a b -> Maybe (AnchoredSeq v a b, AnchoredSeq v a b)
- join :: Anchorable v a b => (Either a b -> a -> Bool) -> AnchoredSeq v a b -> AnchoredSeq v a b -> Maybe (AnchoredSeq v a b)
- anchorNewest :: Anchorable v a b => Word64 -> AnchoredSeq v a b -> AnchoredSeq v a b
- selectOffsets :: Anchorable v a b => [Int] -> AnchoredSeq v a b -> [Either a b]
- filter :: Anchorable v a b => (b -> Bool) -> AnchoredSeq v a b -> [AnchoredSeq v a b]
- filterWithStop :: Anchorable v a b => (b -> Bool) -> (b -> Bool) -> AnchoredSeq v a b -> [AnchoredSeq v a b]
- prettyPrint :: String -> (a -> String) -> (b -> String) -> AnchoredSeq v a b -> String
- filterWithStopSpec :: Anchorable v a b => (b -> Bool) -> (b -> Bool) -> AnchoredSeq v a b -> [AnchoredSeq v a b]

`AnchoredSeq`

type

data AnchoredSeq v a b where Source #

Generalisation of a `Sequence`

with elements of type `b`

with a custom
measure `v`

and an anchor `a`

.

This type is strict in the elements, but not strict in the spine.

For example, an `AnchoredSeq`

can represent a fragment of a chain containing
blocks that is anchored at a certain point. It can also represent a history
of ledger states with the anchor being the "immutable" ledger state.

NOTE: there might be multiple elements with the same measure, e.g., multiple
blocks with the same `WithOrigin SlotNo`

. That is why functions operating on
an `AnchoredSeq`

often take a predicate in addition to a measure. At most one
element should satisfy that predicate, e.g., the block must have a certain
hash. The behaviour is undefined when multiple elements satisfy the
predicate.

pattern Empty :: Anchorable v a b => a -> AnchoredSeq v a b | \( O(1) \). Pattern for matching on or creating an empty |

pattern (:>) :: Anchorable v a b => AnchoredSeq v a b -> b -> AnchoredSeq v a b infixl 5 | \( O(1) \). Add an element to the right of the anchored sequence. |

pattern (:<) :: Anchorable v a b => b -> AnchoredSeq v a b -> AnchoredSeq v a b infixl 5 | \( O(1) \). View the first, leftmost block of the anchored sequence. Note that the anchor shifts, i.e., the anchor of the second argument will correspond to the first argument. This is only a view, not a constructor, as adding a block to the left would change the anchor of the sequence, but we have no information about the predecessor of the block we'd be prepending. |

#### Instances

`Anchorable`

class (Ord v, Bounded v) => Anchorable v a b | a -> v where Source #

Constaint needed to use an `AnchoredSeq`

.

`b`

as anchor

getAnchorMeasure :: Proxy b -> a -> v Source #

#### Instances

HasHeader block => Anchorable (WithOrigin SlotNo) (Anchor block) block Source # | |

Defined in Ouroboros.Network.AnchoredFragment |

# Basic operations

anchor :: AnchoredSeq v a b -> a Source #

head :: Anchorable v a b => AnchoredSeq v a b -> Either a b Source #

\( O(1) \). When the sequence is empty, return the anchor, otherwise the most recently added element.

headAnchor :: Anchorable v a b => AnchoredSeq v a b -> a Source #

\( O(1) \). The anchor corresponding to the most recently added element
(i.e., the anchor that would be needed for a sequence starting *after* this).
When the anchored sequence is empty, the anchor is returned.

last :: Anchorable v a b => AnchoredSeq v a b -> Either a b Source #

\( O(1) \). When the sequence is empty, return the anchor, otherwise the leftmost element.

toNewestFirst :: AnchoredSeq v a b -> [b] Source #

\( O(n) \). Return the elements in the `AnchoredSeq`

in newest-to-oldest
order.

toOldestFirst :: AnchoredSeq v a b -> [b] Source #

\( O(n) \). Return the elements in the `AnchoredSeq`

in oldest-to-newest
order.

fromNewestFirst :: Anchorable v a b => a -> [b] -> AnchoredSeq v a b Source #

\( O(n) \). Make an `AnchoredSeq`

from a list of elements in
newest-to-oldest order. The last element in the list will be the one after
the given anchor.

fromOldestFirst :: Anchorable v a b => a -> [b] -> AnchoredSeq v a b Source #

\( O(n) \). Make an `AnchoredSeq`

from a list of elements in
oldest-to-newest order. The first element in the list will be the one after
the given anchor.

splitAt :: Anchorable v a b => Int -> AnchoredSeq v a b -> (AnchoredSeq v a b, AnchoredSeq v a b) Source #

\( O(\log(\min(i,n-i)) \). Split the `AnchoredSeq`

at a given
position.

POSTCONDITION: `(before, after) = splitAt i s`

, then:

anchor before == anchor s headAnchor before == anchor after headAnchor after == headAnchor s join before after == Just s

splitAtMeasure :: Anchorable v a b => v -> AnchoredSeq v a b -> (AnchoredSeq v a b, AnchoredSeq v a b) Source #

\( O(\log(\min(i,n-i)) \). Split the `AnchoredSeq`

at a given
measure.

POSTCONDITION: `(before, after) = splitAtMeasure v s`

, then:

anchor before == anchor s headAnchor before == anchor after headAnchor after == headAnchor s toOldestFirst before == filter ((< v) . getAnchorMeasure @v @a (Proxy @b) . asAnchor) (toOldestFirst s) toOldestFirst after == filter ((v <=) . getAnchorMeasure @v @a (Proxy @b) . asAnchor) (toOldestFirst s)

dropNewest :: Anchorable v a b => Int -> AnchoredSeq v a b -> AnchoredSeq v a b Source #

\( O(\log(\min(i,n-i)) \). Drop the newest `n`

elements from the
`AnchoredSeq`

. The anchor does not change.

takeOldest :: Anchorable v a b => Int -> AnchoredSeq v a b -> AnchoredSeq v a b Source #

\( O(\log(\min(i,n-i)) \). Take the oldest `n`

elements from the
`AnchoredSeq`

. The anchor does not change.

dropWhileNewest :: Anchorable v a b => (b -> Bool) -> AnchoredSeq v a b -> AnchoredSeq v a b Source #

\( O(n) \). Drop the newest elements that satisfy the predicate, keeping the remainder. The anchor does not change.

takeWhileOldest :: Anchorable v a b => (b -> Bool) -> AnchoredSeq v a b -> AnchoredSeq v a b Source #

\( O(n) \). Take the oldest elements that satisfy the predicate. The anchor does not change.

length :: Anchorable v a b => AnchoredSeq v a b -> Int Source #

\( O(1) \). Return the number of elements. The anchor is not counted.

null :: AnchoredSeq v a b -> Bool Source #

\( O(1) \). The anchor is not counted.

contains :: Anchorable v a b => v -> (b -> Bool) -> AnchoredSeq v a b -> Bool Source #

\( O(\log(\min(i,n-i)) \). Does the anchored sequence contain an element with the given measure that satisfies the predicate? The anchor is ignored.

withinBounds :: Anchorable v a b => v -> (Either a b -> Bool) -> AnchoredSeq v a b -> Bool Source #

\( O(\log(\min(i,n-i)) \). Does the anchored sequence contain an element
with the given measure that satisfies the predicate? The anchor is *not*
ignored.

map :: Anchorable v2 a b2 => (b1 -> b2) -> AnchoredSeq v1 a b1 -> AnchoredSeq v2 a b2 Source #

\( O(n) \). Maps over the elements and the elements.

bimap :: Anchorable v2 a2 b2 => (a1 -> a2) -> (b1 -> b2) -> AnchoredSeq v1 a1 b1 -> AnchoredSeq v2 a2 b2 Source #

\( O(n) \). Maps over the elements.

mapPreservingMeasure :: (b1 -> b2) -> AnchoredSeq v a b1 -> AnchoredSeq v a b2 Source #

\( O(n) \). Maps over the elements.

NOTE: the functions must preserve the measure.

More efficient than `map`

bimapPreservingMeasure :: (a1 -> a2) -> (b1 -> b2) -> AnchoredSeq v a1 b1 -> AnchoredSeq v a2 b2 Source #

\( O(n) \). Maps over the anchor and the elements.

NOTE: the functions must preserve the measure.

More efficient than `bimap`

# Special operations

rollback :: Anchorable v a b => v -> (Either a b -> Bool) -> AnchoredSeq v a b -> Maybe (AnchoredSeq v a b) Source #

\( O(\log(\min(i,n-i)) \). Roll back the anchored sequence such that its
new head has the same measure as the given one and satisfies the predicate.
When there is no such element or anchor, return `Nothing`

.

isPrefixOf :: forall v a b. (Eq a, Eq b) => AnchoredSeq v a b -> AnchoredSeq v a b -> Bool Source #

\( O(\max(n_1, n_2)) \). Check whether the first anchored sequence is a
prefix of the second. Comparisons are done based on the `Eq`

instances.

The two `AnchoredSeq`

s must have the same anchor, otherwise the first cannot
be a prefix of the second.

isPrefixOfByMeasure :: Anchorable v a b => AnchoredSeq v a b -> AnchoredSeq v a b -> Bool Source #

\( O(\max(n_1, n_2)) \). Check whether the first anchored sequence is a prefix of the second. Comparisons are done based on the measure.

The two `AnchoredSeq`

s must have the same anchor, otherwise the first cannot
be a prefix of the second.

lookupByMeasure :: Anchorable v a b => v -> AnchoredSeq v a b -> [b] Source #

\( O(\log(\min(i,n-i) + s) \) where *s* is the number of elements with the
same measure. Return all elements in the anchored sequence with a measure
(`k`

) equal to the given one. The elements will be ordered from oldest to
newest. Does not look at the anchor.

splitAfterMeasure :: Anchorable v a b => v -> (Either a b -> Bool) -> AnchoredSeq v a b -> Maybe (AnchoredSeq v a b, AnchoredSeq v a b) Source #

\( O(\log(\min(i,n-i)) \). Split the `AnchoredSeq`

after an element or
anchor with the given measure that satisfies the predicate. Return `Nothing`

if there is no element or anchor with the given measure that satisfies the
predicate.

If the given measure corresponds to the anchor and it satisfies the predicate, an empty sequence with the given anchor, and the original sequence are returned.

PRECONDITION: there can be multiple elements with the same measure, but there should be at most one element (or anchor) with the given measure satisfying the predicate.

POSTCONDITION: when `Just (before, after) = splitAfterMeasure k f s`

, then:

anchor before == anchor s headMeasure before == pt anchorMeasure after == pt headAnchor after == headAnchor s join before after == Just s

splitBeforeMeasure :: Anchorable v a b => v -> (b -> Bool) -> AnchoredSeq v a b -> Maybe (AnchoredSeq v a b, AnchoredSeq v a b) Source #

\( O(\log(\min(i,n-i)) \). Split the `AnchoredSeq`

before an element with
the given measure that satisfies the predicate. Return `Nothing`

if the
anchored sequence does not contain an element with the given measure that
satisfies the predicate.

Unlike `splitAfterMeasure`

we can't split before the anchor.

PRECONDITION: there can be multiple elements with the same measure, but there should be at most one element (or anchor) with the given measure satisfying the predicate.

POSTCONDITION: joining (`join`

) the two anchored sequences gives back the
original anchored sequence.

POSTCONDITION: the last element (oldest) in the second sequence has the given measure and satisfies the predicate.

join :: Anchorable v a b => (Either a b -> a -> Bool) -> AnchoredSeq v a b -> AnchoredSeq v a b -> Maybe (AnchoredSeq v a b) Source #

\( O(\log(\min(n_1, n_2))) \). Join two anchored sequences if the given
function returns `True`

for the head (newest element or anchor when empty) of
the first sequence and the anchor of the second sequence, e.g., when they
match.

The returned sequence will have the same anchor as the first sequence.

:: Anchorable v a b | |

=> Word64 | n |

-> AnchoredSeq v a b | |

-> AnchoredSeq v a b |

Take the `n`

newest elements from the anchored sequence.

WARNING: this may change the anchor

When the anchored sequence contains fewer than `n`

elements, the anchored
sequence will be returned unmodified.

selectOffsets :: Anchorable v a b => [Int] -> AnchoredSeq v a b -> [Either a b] Source #

\( O(o \log(\min(i,n-i))) \). Select the elements and optionally the anchor
based on the given offsets, starting from the head of the `AnchoredSeq`

.

The list of offsets must be increasing monotonically (/strictly increasing is not required).

**Note**: offset `n`

, where `n`

equals the length of the `AnchoredSeq`

,
corresponds to the anchor. When the sequence is empty, offset 0 will thus
correspond to the anchor.

:: Anchorable v a b | |

=> (b -> Bool) | Filtering predicate |

-> AnchoredSeq v a b | |

-> [AnchoredSeq v a b] |

\( O(n) \). Variation on `filterWithStop`

without a stop condition.

:: Anchorable v a b | |

=> (b -> Bool) | Filtering predicate |

-> (b -> Bool) | Stop condition |

-> AnchoredSeq v a b | |

-> [AnchoredSeq v a b] |

\( O(n + r * \log(\min(i,n-i)) \) where *r* is the number of consecutive
ranges of elements to be included in the result.

Filter out elements that don't match the predicate.

As filtering removes elements the result is a sequence of disconnected sequences. The sequences are in the original order and are of maximum size.

As soon as the stop condition is true, the filtering stops and the remaining sequence (starting with the first element for which the stop condition is true) is the final sequence in the returned list.

The stop condition wins from the filtering predicate: if the stop condition is true for an element, but the filter predicate not, then the element still ends up in final sequence.

For example, given the sequence containing `[0: 1, 2, 3, 4, 5, 6]`

where the
anchor is separated from the elements by `:`

:

filter odd -> [[0: 1], [2: 3], [4: 5]] filterWithStop odd (>= 4) -> [[0: 1], [2: 3], [3: 4, 5, 6]]

# Helper functions

prettyPrint :: String -> (a -> String) -> (b -> String) -> AnchoredSeq v a b -> String Source #

# Reference implementations for testing

:: Anchorable v a b | |

=> (b -> Bool) | Filtering predicate |

-> (b -> Bool) | Stop condition |

-> AnchoredSeq v a b | |

-> [AnchoredSeq v a b] |

\( O(n) \). Naive reference implementation of `filterWithStop`

.

While the asymptotic complexity of this function is better than that of
`filterWithStop`

, the allocation cost is high. This function deconstructs and
reconstructs the anchored sequence (until the stop condition is reached),
even when no elements are removed.