Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
is a spine-lazy radix tree that uses byte-aligned
non-empty byte sequences as keys.LazyRadix1Tree
a
Laziness
Evaluating any particular entry in the tree to WHNF forces the evaluation of the part of the spine leading up to that entry to normal form.
Performance
Each function's time complexity is provided in the documentation.
Laziness-amortized functions specify two time complexities: time to construct the return value (denoted with a \(\texttt{+}\)) and time to fully apply the function to the tree.
\(x\) is the length of the input key.
\(k\) is the length of the longest key stored in the tree.
\(n\) refers to the total number of entries in the tree.
Parts of the tree are denoted using subscripts: \(n_L\) refers to the left side,
\(n_R\) to the right side, and \(n_M\) to entries collected with the use of a Monoid
.
Inlining
Functions that produce and consume Feed1
s are treated specially within the library,
as when combined they can be reduced in a manner similar to the
destroy/unfoldr elimination rule.
The elimination in this library is achieved by inlining both types of functions heavily. To avoid unnecessary code duplication during compilation consider creating helper functions that apply these functions one to another, e.g.
updateBS f bs =update
f (unsafeFeedByteString
bs)
N.B. To inline properly functions that consume Feed1
s must mention all of the
arguments except for the tree.
Implementation
See the implementation section in Data.RadixTree.Word8.Strict.Unsafe for the explanation of the innerworkings.
See the implementation section in Data.Patricia.Word.Strict for literary references.
Synopsis
- type LazyRadix1Tree = Radix1Tree
- data Radix1Tree a
- data RadixTree a = RadixTree !(Maybe a) (Radix1Tree a)
- module Data.Radix1Tree.Word8.Key
- empty :: Radix1Tree a
- singleton :: Feed1 -> a -> Radix1Tree a
- toStrict :: LazyRadix1Tree a -> StrictRadix1Tree a
- lookup :: Feed1 -> Radix1Tree a -> Maybe a
- find :: a -> Feed1 -> Radix1Tree a -> a
- member :: Feed1 -> Radix1Tree a -> Bool
- subtree :: Feed1 -> Radix1Tree a -> RadixTree a
- data Cursor a
- cursor :: Radix1Tree a -> Cursor a
- move :: Feed1 -> Cursor a -> Cursor a
- stop :: Cursor a -> Maybe a
- data Location
- locate :: Cursor a -> Location
- insert :: Feed1 -> a -> Radix1Tree a -> Radix1Tree a
- insertWith :: (a -> a) -> Feed1 -> a -> Radix1Tree a -> Radix1Tree a
- adjust :: (a -> a) -> Feed1 -> Radix1Tree a -> Radix1Tree a
- delete :: Feed1 -> Radix1Tree a -> Radix1Tree a
- prune :: Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a
- update :: (a -> Maybe a) -> Feed1 -> Radix1Tree a -> Radix1Tree a
- alter :: (Maybe a -> Maybe a) -> Feed1 -> Radix1Tree a -> Radix1Tree a
- shape :: (RadixTree a -> RadixTree a) -> Feed1 -> Radix1Tree a -> Radix1Tree a
- splitLookup :: Feed1 -> Radix1Tree a -> (Radix1Tree a, Maybe a, Radix1Tree a)
- data Openness
- data Lookup a = Lookup !Build a
- lookupL :: Openness -> Feed1 -> Radix1Tree a -> Maybe (Lookup1 a)
- lookupR :: Openness -> Feed1 -> Radix1Tree a -> Maybe (Lookup1 a)
- adjustL :: (a -> a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a
- adjustLWithKey :: (Build1 -> a -> a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a
- adjustR :: (a -> a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a
- adjustRWithKey :: (Build1 -> a -> a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a
- updateL :: (a -> Maybe a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a
- updateLWithKey :: (Build1 -> a -> Maybe a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a
- updateR :: (a -> Maybe a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a
- updateRWithKey :: (Build1 -> a -> Maybe a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a
- takeL :: Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a
- splitL :: Openness -> Feed1 -> Radix1Tree a -> (Radix1Tree a, Radix1Tree a)
- takeR :: Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a
- lookupMin :: Radix1Tree a -> Maybe a
- lookupMinWithKey :: Radix1Tree a -> Maybe (Lookup1 a)
- lookupMax :: Radix1Tree a -> Maybe a
- lookupMaxWithKey :: Radix1Tree a -> Maybe (Lookup1 a)
- adjustMin :: (a -> a) -> Radix1Tree a -> Radix1Tree a
- adjustMinWithKey :: (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
- adjustMax :: (a -> a) -> Radix1Tree a -> Radix1Tree a
- adjustMaxWithKey :: (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
- deleteMin :: Radix1Tree a -> Radix1Tree a
- deleteMax :: Radix1Tree a -> Radix1Tree a
- updateMin :: (a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
- updateMinWithKey :: (Build1 -> a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
- updateMax :: (a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
- updateMaxWithKey :: (Build1 -> a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
- data ViewL a = ViewL !Build a !(RadixTree a)
- minView :: Radix1Tree a -> Maybe (ViewL1 a)
- data ViewR a = ViewR !(RadixTree a) !Build a
- maxView :: Radix1Tree a -> Maybe (ViewR1 a)
- null :: Radix1Tree a -> Bool
- size :: Radix1Tree a -> Int
- prefix :: Feed1 -> RadixTree a -> Radix1Tree a
- map :: (a -> b) -> Radix1Tree a -> Radix1Tree b
- mapWithKey :: (Build1 -> a -> b) -> Radix1Tree a -> Radix1Tree b
- foldl :: (b -> a -> b) -> b -> Radix1Tree a -> b
- foldl' :: (b -> a -> b) -> b -> Radix1Tree a -> b
- foldlWithKey :: (b -> Build1 -> a -> b) -> b -> Radix1Tree a -> b
- foldlWithKey' :: (b -> Build1 -> a -> b) -> b -> Radix1Tree a -> b
- foldr :: (a -> b -> b) -> b -> Radix1Tree a -> b
- foldr' :: (a -> b -> b) -> b -> Radix1Tree a -> b
- foldrWithKey :: (Build1 -> a -> b -> b) -> b -> Radix1Tree a -> b
- foldrWithKey' :: (Build1 -> a -> b -> b) -> b -> Radix1Tree a -> b
- foldMap :: Monoid m => (a -> m) -> Radix1Tree a -> m
- foldMapWithKey :: Monoid m => (Build1 -> a -> m) -> Radix1Tree a -> m
- traverse :: Applicative f => (a -> f b) -> Radix1Tree a -> f (Radix1Tree b)
- traverseWithKey :: Applicative f => (Build1 -> a -> f b) -> Radix1Tree a -> f (Radix1Tree b)
- filter :: (a -> Bool) -> Radix1Tree a -> Radix1Tree a
- filterWithKey :: (Build1 -> a -> Bool) -> Radix1Tree a -> Radix1Tree a
- mapMaybe :: (a -> Maybe b) -> Radix1Tree a -> Radix1Tree b
- mapMaybeWithKey :: (Build1 -> a -> Maybe b) -> Radix1Tree a -> Radix1Tree b
- partition :: (a -> Bool) -> Radix1Tree a -> (Radix1Tree a, Radix1Tree a)
- partitionWithKey :: (Build1 -> a -> Bool) -> Radix1Tree a -> (Radix1Tree a, Radix1Tree a)
- mapEither :: (a -> Either b c) -> Radix1Tree a -> (Radix1Tree b, Radix1Tree c)
- mapEitherWithKey :: (Build1 -> a -> Either b c) -> Radix1Tree a -> (Radix1Tree b, Radix1Tree c)
- data PartialOrdering
- = Subset
- | Superset
- | Equal
- | Incomparable
- compare :: (a -> b -> Bool) -> Radix1Tree a -> Radix1Tree b -> PartialOrdering
- union :: Radix1Tree a -> Radix1Tree a -> Radix1Tree a
- unionL :: Radix1Tree a -> Radix1Tree a -> Radix1Tree a
- unionWith :: (a -> a -> a) -> Radix1Tree a -> Radix1Tree a -> Radix1Tree a
- unionWithKey :: (Build1 -> a -> a -> a) -> Radix1Tree a -> Radix1Tree a -> Radix1Tree a
- difference :: Radix1Tree a -> Radix1Tree b -> Radix1Tree a
- differenceWith :: (a -> b -> Maybe a) -> Radix1Tree a -> Radix1Tree b -> Radix1Tree a
- differenceWithKey :: (Build1 -> a -> b -> Maybe a) -> Radix1Tree a -> Radix1Tree b -> Radix1Tree a
- disjoint :: Radix1Tree a -> Radix1Tree b -> Bool
- intersection :: Radix1Tree a -> Radix1Tree a -> Radix1Tree a
- intersectionL :: Radix1Tree a -> Radix1Tree b -> Radix1Tree a
- intersectionWith :: (a -> b -> c) -> Radix1Tree a -> Radix1Tree b -> Radix1Tree c
- intersectionWithKey :: (Build1 -> a -> b -> c) -> Radix1Tree a -> Radix1Tree b -> Radix1Tree c
Documentation
type LazyRadix1Tree = Radix1Tree Source #
Convenience type synonym.
data Radix1Tree a Source #
Spine-strict radix tree with non-empty byte sequences as keys.
Instances
Spine-strict radix tree with byte sequences as keys.
RadixTree | |
|
Instances
Key
module Data.Radix1Tree.Word8.Key
Construct
empty :: Radix1Tree a Source #
\(\mathcal{O}(1)\). Empty tree.
singleton :: Feed1 -> a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(x)\). Tree with a single entry.
Convert
toStrict :: LazyRadix1Tree a -> StrictRadix1Tree a Source #
\(\mathcal{O}(n)\).
Create a strict Patricia
tree from a lazy one.
The resulting tree does not share its data representation with the original.
Single-key
Lookup
lookup :: Feed1 -> Radix1Tree a -> Maybe a Source #
\(\mathcal{O}(\min(x,k))\). Look up the value at a key in the tree.
find :: a -> Feed1 -> Radix1Tree a -> a Source #
\(\mathcal{O}(\min(x,k))\). Look up the value at a key in the tree, falling back to the given default value if it does not exist.
member :: Feed1 -> Radix1Tree a -> Bool Source #
\(\mathcal{O}(\min(x,k))\). Check whether the value exists at a key in the tree.
subtree :: Feed1 -> Radix1Tree a -> RadixTree a Source #
\(\mathcal{O}(\min(x,k))\). Look up the part of the tree below the given prefix.
Chunked
Chunked lookup allows providing the key piece by piece while retaining the ability to check for early failure.
Note that while subtree
can be used to achieve the same result,
it is more expensive allocation-wise, as it must ensure that
the resulting tree is well-formed after each chunk application.
A particular point in the tree.
cursor :: Radix1Tree a -> Cursor a Source #
\(\mathcal{O}(1)\). Make a cursor that points to the root of the tree.
move :: Feed1 -> Cursor a -> Cursor a Source #
\(\mathcal{O}(\min(x,k))\). Move the cursor down by the extent of the given key.
stop :: Cursor a -> Maybe a Source #
\(\mathcal{O}(1)\). Retrieve the value at which the cursor points.
Whether the cursor point to a point within the tree.
locate :: Cursor a -> Location Source #
\(\mathcal{O}(1)\). Determine whether the cursor points to a point within the tree.
Insert
insert :: Feed1 -> a -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k))\). Insert a new value in the tree at the given key. If a value already exists at that key, it is replaced.
insertWith :: (a -> a) -> Feed1 -> a -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k))\). Insert a new value in the tree at the given key. If a value already exists at that key, the function is used instead.
Map
adjust :: (a -> a) -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k))\). Apply a function to a value in the tree at the given key.
Delete
delete :: Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k))\). Delete a value in the tree at the given key.
prune :: Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k))\). Delete values in the tree below the given key.
Update
update :: (a -> Maybe a) -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k))\). Update or delete a value in the tree at the given key.
alter :: (Maybe a -> Maybe a) -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k))\). Insert, update or delete a value in the tree at the given key.
shape :: (RadixTree a -> RadixTree a) -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k))\). Update the part of the tree at the given prefix.
Take
splitLookup :: Feed1 -> Radix1Tree a -> (Radix1Tree a, Maybe a, Radix1Tree a) Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k))\). Split the tree into two, such that values with keys smaller than the given one are on the left, values with keys greater than the given one are on the right, and the value at the given key is returned separately.
Directional
Whether the endpoint itself is included in the interval.
Lookup
Key together with the value.
lookupL :: Openness -> Feed1 -> Radix1Tree a -> Maybe (Lookup1 a) Source #
\(\mathcal{O}(\min(x,k))\). Look up a value at a largest key smaller than (or equal to) the given key.
lookupR :: Openness -> Feed1 -> Radix1Tree a -> Maybe (Lookup1 a) Source #
\(\mathcal{O}(\min(x,k))\). Look up a value at a smallest key greater than (or equal to) the given key.
Map
Left
adjustL :: (a -> a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k) + n_L)\). Apply a function to every value for which the key is smaller than (or equal to) the given one.
adjustLWithKey :: (Build1 -> a -> a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k) + n_L)\). Apply a function to every value for which the key is smaller than (or equal to) the given one.
Right
adjustR :: (a -> a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k) + n_R)\). Apply a function to every value for which the key is greater than (or equal to) the given one.
adjustRWithKey :: (Build1 -> a -> a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k) + n_R)\). Apply a function to every value for which the key is greater than (or equal to) the given one.
Update
Left
updateL :: (a -> Maybe a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k) + n_L)\). Update every value for which the key is smaller than (or equal to) the given one.
updateLWithKey :: (Build1 -> a -> Maybe a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k) + n_L)\). Update every value for which the key is smaller than (or equal to) the given one.
Right
updateR :: (a -> Maybe a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k) + n_R)\). Update every value for which the key is greater than (or equal to) the given one.
updateRWithKey :: (Build1 -> a -> Maybe a) -> Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k) + n_R)\). Update every value for which the key is greater than (or equal to) the given one.
Take
Left
takeL :: Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k))\). Take values for which keys are smaller than (or equal to) the given one.
splitL :: Openness -> Feed1 -> Radix1Tree a -> (Radix1Tree a, Radix1Tree a) Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k))\). Split the tree into two, such that values with keys smaller than (or equal to) the given one are on the left, and the rest are on the right.
Right
takeR :: Openness -> Feed1 -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(x,k))\). Take values for which keys are greater than (or equal to) the given one.
Edges
Lookup
Min
lookupMin :: Radix1Tree a -> Maybe a Source #
\(\mathcal{O}(k)\). Look up a value at the leftmost key in the tree.
lookupMinWithKey :: Radix1Tree a -> Maybe (Lookup1 a) Source #
\(\mathcal{O}(k)\). Look up a value at the leftmost key in the tree.
Max
lookupMax :: Radix1Tree a -> Maybe a Source #
\(\mathcal{O}(k)\). Look up a value at the rightmost key in the tree.
lookupMaxWithKey :: Radix1Tree a -> Maybe (Lookup1 a) Source #
\(\mathcal{O}(k)\). Look up a value at the rightmost key in the tree.
Map
Min
adjustMin :: (a -> a) -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). Update a value at the leftmost key in the tree.
adjustMinWithKey :: (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). Update a value at the leftmost key in the tree.
Max
adjustMax :: (a -> a) -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). Update a value at the rightmost key in the tree.
adjustMaxWithKey :: (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). Update a value at the rightmost key in the tree.
Delete
deleteMin :: Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). Delete a value at the leftmost key in the tree.
deleteMax :: Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). Delete a value at the rightmost key in the tree.
Update
Min
updateMin :: (a -> Maybe a) -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). Update or delete a value at the leftmost key in the tree.
updateMinWithKey :: (Build1 -> a -> Maybe a) -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). Update or delete a value at the leftmost key in the tree.
Max
updateMax :: (a -> Maybe a) -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). Update or delete a value at the rightmost key in the tree.
updateMaxWithKey :: (Build1 -> a -> Maybe a) -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). Update or delete a value at the rightmost key in the tree.
View
Min
The leftmost value with its key and the rest of the tree.
minView :: Radix1Tree a -> Maybe (ViewL1 a) Source #
\(\mathcal{O}(\min(x,k))\). Look up the leftmost value and return it alongside the tree without it.
Max
The rightmost value with its key and the rest of the tree.
maxView :: Radix1Tree a -> Maybe (ViewR1 a) Source #
\(\mathcal{O}(\min(x,k))\). Look up the rightmost value and return it alongside the tree without it.
Full tree
Size
null :: Radix1Tree a -> Bool Source #
\(\mathcal{O}(1)\). Check if the tree is empty.
size :: Radix1Tree a -> Int Source #
\(\mathcal{O}(n)\). Calculate the number of elements stored in the tree. The returned number is guaranteed to be non-negative.
Extend
prefix :: Feed1 -> RadixTree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(x)\). Prefix the root of the tree with the given key.
Map
map :: (a -> b) -> Radix1Tree a -> Radix1Tree b Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n)\). Apply a function to every value in the tree.
mapWithKey :: (Build1 -> a -> b) -> Radix1Tree a -> Radix1Tree b Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n)\). Apply a function to every value in the tree.
Fold
Left-to-right
foldl :: (b -> a -> b) -> b -> Radix1Tree a -> b Source #
\(\mathcal{O}(n_R)\). Fold the tree left-to-right.
foldl' :: (b -> a -> b) -> b -> Radix1Tree a -> b Source #
\(\mathcal{O}(n)\). Fold the tree left-to-right with a strict accumulator.
foldlWithKey :: (b -> Build1 -> a -> b) -> b -> Radix1Tree a -> b Source #
\(\mathcal{O}(n_R)\). Fold the tree left-to-right.
foldlWithKey' :: (b -> Build1 -> a -> b) -> b -> Radix1Tree a -> b Source #
\(\mathcal{O}(n)\). Fold the tree left-to-right with a strict accumulator.
Right-to-left
foldr :: (a -> b -> b) -> b -> Radix1Tree a -> b Source #
\(\mathcal{O}(n_L)\). Fold the tree right-to-left.
foldr' :: (a -> b -> b) -> b -> Radix1Tree a -> b Source #
\(\mathcal{O}(n)\). Fold the tree right-to-left with a strict accumulator.
foldrWithKey :: (Build1 -> a -> b -> b) -> b -> Radix1Tree a -> b Source #
\(\mathcal{O}(n_L)\). Fold the tree right-to-left.
foldrWithKey' :: (Build1 -> a -> b -> b) -> b -> Radix1Tree a -> b Source #
\(\mathcal{O}(n)\). Fold the tree right-to-left with a strict accumulator.
Monoid
foldMap :: Monoid m => (a -> m) -> Radix1Tree a -> m Source #
\(\mathcal{O}(n_M)\). Map each element in the tree to a monoid and combine the results.
foldMapWithKey :: Monoid m => (Build1 -> a -> m) -> Radix1Tree a -> m Source #
\(\mathcal{O}(n_M)\). Map each element in the tree to a monoid and combine the results.
Traverse
traverse :: Applicative f => (a -> f b) -> Radix1Tree a -> f (Radix1Tree b) Source #
\(\mathcal{O}(n)\). Map each element in the tree to an action, evaluate these actions left-to-right and collect the results.
traverseWithKey :: Applicative f => (Build1 -> a -> f b) -> Radix1Tree a -> f (Radix1Tree b) Source #
\(\mathcal{O}(n)\). Map each element in the tree to an action, evaluate these actions left-to-right and collect the results.
Filter
One side
filter :: (a -> Bool) -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n)\). Filter values that satisfy the value predicate.
filterWithKey :: (Build1 -> a -> Bool) -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n)\). Filter values that satisfy the value predicate.
mapMaybe :: (a -> Maybe b) -> Radix1Tree a -> Radix1Tree b Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n)\).
Apply a function to every value in the tree and create one out of Just
values.
mapMaybeWithKey :: (Build1 -> a -> Maybe b) -> Radix1Tree a -> Radix1Tree b Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n)\).
Apply a function to every value in the tree and create one out of Just
values.
Both sides
partition :: (a -> Bool) -> Radix1Tree a -> (Radix1Tree a, Radix1Tree a) Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n)\). Split the tree into two, such that values that satisfy the predicate are on the left and values that do not are on the right.
partitionWithKey :: (Build1 -> a -> Bool) -> Radix1Tree a -> (Radix1Tree a, Radix1Tree a) Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n)\). Split the tree into two, such that values that satisfy the predicate are on the left and values that do not are on the right.
mapEither :: (a -> Either b c) -> Radix1Tree a -> (Radix1Tree b, Radix1Tree c) Source #
mapEitherWithKey :: (Build1 -> a -> Either b c) -> Radix1Tree a -> (Radix1Tree b, Radix1Tree c) Source #
Comparison
data PartialOrdering Source #
Comparison of two sets, \(A\) and \(B\) respectively.
Subset | \(A \subset B\). |
Superset | \(A \supset B\). |
Equal | \(A = B\). |
Incomparable | \(A \parallel B\). |
Instances
Show PartialOrdering Source # | |
Defined in Radix.Common showsPrec :: Int -> PartialOrdering -> ShowS # show :: PartialOrdering -> String # showList :: [PartialOrdering] -> ShowS # | |
Eq PartialOrdering Source # | |
Defined in Radix.Common (==) :: PartialOrdering -> PartialOrdering -> Bool # (/=) :: PartialOrdering -> PartialOrdering -> Bool # |
compare :: (a -> b -> Bool) -> Radix1Tree a -> Radix1Tree b -> PartialOrdering Source #
\(\mathcal{O}(n_A k_A + n_B k_B)\).
Compare two trees with respect to set inclusion,
using the given equality function for intersecting keys.
If any intersecting keys hold unequal values, the trees are Incomparable
.
Union
union :: Radix1Tree a -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n_A k_A + n_B k_B)\). Unbiased union of two trees.
unionL :: Radix1Tree a -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n_A k_A + n_B k_B)\). Left-biased union of two trees.
unionWith :: (a -> a -> a) -> Radix1Tree a -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n_A k_A + n_B k_B)\). Union of two trees with a combining function.
unionWithKey :: (Build1 -> a -> a -> a) -> Radix1Tree a -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n_A k_A + n_B k_B)\). Union of two trees with a combining function.
Difference
difference :: Radix1Tree a -> Radix1Tree b -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n_A k_A + n_B k_B)\). Difference of two trees.
differenceWith :: (a -> b -> Maybe a) -> Radix1Tree a -> Radix1Tree b -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n_A k_A + n_B k_B)\). Difference of two trees with a combining function.
differenceWithKey :: (Build1 -> a -> b -> Maybe a) -> Radix1Tree a -> Radix1Tree b -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n_A k_A + n_B k_B)\). Difference of two trees with a combining function.
Intersection
disjoint :: Radix1Tree a -> Radix1Tree b -> Bool Source #
\(\mathcal{O}(n_A k_A + n_B k_B)\). Determine whether two trees' key sets are disjoint.
intersection :: Radix1Tree a -> Radix1Tree a -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n_A k_A + n_B k_B)\). Unbiased intersection of two trees.
intersectionL :: Radix1Tree a -> Radix1Tree b -> Radix1Tree a Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n_A k_A + n_B k_B)\). Left-biased intersection of two trees.
intersectionWith :: (a -> b -> c) -> Radix1Tree a -> Radix1Tree b -> Radix1Tree c Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n_A k_A + n_B k_B)\). Intersection of two trees with a combining function.
intersectionWithKey :: (Build1 -> a -> b -> c) -> Radix1Tree a -> Radix1Tree b -> Radix1Tree c Source #
\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n_A k_A + n_B k_B)\). Intersection of two trees with a combining function.
Merge
See merge
.