| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Agda.Utils.Trie
Description
Strict tries (based on Data.Map.Strict and Agda.Utils.Maybe.Strict).
Note that if delete or adjust are used, one may end up with non-canonical
subtries, i.e., those that do not contain any value (Data.List.null . toList)
but may be Eq-different to other empty tries (/= empty).
Synopsis
- data Trie k v = Trie !(Maybe v) !(Map k (Trie k v))
- empty :: Null a => a
- singleton :: [k] -> v -> Trie k v
- everyPrefix :: [k] -> v -> Trie k v
- insert :: Ord k => [k] -> v -> Trie k v -> Trie k v
- insertWith :: Ord k => (v -> v -> v) -> [k] -> v -> Trie k v -> Trie k v
- union :: Ord k => Trie k v -> Trie k v -> Trie k v
- unionWith :: Ord k => (v -> v -> v) -> Trie k v -> Trie k v -> Trie k v
- adjust :: Ord k => [k] -> (Maybe v -> Maybe v) -> Trie k v -> Trie k v
- delete :: Ord k => [k] -> Trie k v -> Trie k v
- toList :: Ord k => Trie k v -> [([k], v)]
- toAscList :: Ord k => Trie k v -> [([k], v)]
- toListOrderedBy :: Ord k => (v -> v -> Ordering) -> Trie k v -> [([k], v)]
- lookup :: Ord k => [k] -> Trie k v -> Maybe v
- member :: Ord k => [k] -> Trie k v -> Bool
- lookupPath :: Ord k => [k] -> Trie k v -> [v]
- lookupTrie :: Ord k => [k] -> Trie k v -> Trie k v
- mapSubTries :: Ord k => (Trie k u -> Maybe v) -> Trie k u -> Trie k v
- filter :: Ord k => (v -> Bool) -> Trie k v -> Trie k v
- valueAt :: Ord k => [k] -> Lens' (Trie k v) (Maybe v)
Documentation
Instances
| Foldable (Trie k) Source # | |
Defined in Agda.Utils.Trie Methods fold :: Monoid m => Trie k m -> m # foldMap :: Monoid m => (a -> m) -> Trie k a -> m # foldMap' :: Monoid m => (a -> m) -> Trie k a -> m # foldr :: (a -> b -> b) -> b -> Trie k a -> b # foldr' :: (a -> b -> b) -> b -> Trie k a -> b # foldl :: (b -> a -> b) -> b -> Trie k a -> b # foldl' :: (b -> a -> b) -> b -> Trie k a -> b # foldr1 :: (a -> a -> a) -> Trie k a -> a # foldl1 :: (a -> a -> a) -> Trie k a -> a # elem :: Eq a => a -> Trie k a -> Bool # maximum :: Ord a => Trie k a -> a # minimum :: Ord a => Trie k a -> a # | |
| Functor (Trie k) Source # | |
| (Ord a, EmbPrj a, EmbPrj b) => EmbPrj (Trie a b) Source # | |
| Null (Trie k v) Source # | Empty trie. |
| (Show v, Show k) => Show (Trie k v) Source # | |
| (NFData k, NFData v) => NFData (Trie k v) Source # | |
Defined in Agda.Utils.Trie | |
| (Eq v, Eq k) => Eq (Trie k v) Source # | |
everyPrefix :: [k] -> v -> Trie k v Source #
everyPrefix k v is a trie where every prefix of k (including
k itself) is mapped to v.
insert :: Ord k => [k] -> v -> Trie k v -> Trie k v Source #
Insert. Overwrites existing value if present.
insert = insertWith ( new old -> new)
insertWith :: Ord k => (v -> v -> v) -> [k] -> v -> Trie k v -> Trie k v Source #
Insert with function merging new value with old value.
union :: Ord k => Trie k v -> Trie k v -> Trie k v Source #
Left biased union.
union = unionWith ( new old -> new).
unionWith :: Ord k => (v -> v -> v) -> Trie k v -> Trie k v -> Trie k v Source #
Pointwise union with merge function for values.
adjust :: Ord k => [k] -> (Maybe v -> Maybe v) -> Trie k v -> Trie k v Source #
Adjust value at key, leave subtree intact.
Disclaimer: may return a non-canoncial trie because it does not clean up subtries that become empty.
delete :: Ord k => [k] -> Trie k v -> Trie k v Source #
Delete value at key, but leave subtree intact.
Disclaimer: may return a non-canoncial trie because it does not clean up subtries that become empty.
toListOrderedBy :: Ord k => (v -> v -> Ordering) -> Trie k v -> [([k], v)] Source #
Convert to list where nodes at the same level are ordered according to the given ordering.
lookup :: Ord k => [k] -> Trie k v -> Maybe v Source #
Returns the value associated with the given key, if any.
lookupPath :: Ord k => [k] -> Trie k v -> [v] Source #
Collect all values along a given path.