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

Language | Haskell2010 |

Strict tries (based on Data.Map.Strict and Agda.Utils.Maybe.Strict).

## 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' (Maybe v) (Trie k v)

# Documentation

## Instances

Functor (Trie k) Source # | |

Foldable (Trie k) Source # | |

Defined in Agda.Utils.Trie fold :: Monoid m => Trie k m -> 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 # | |

(Eq v, Eq k) => Eq (Trie k v) Source # | |

(Show v, Show k) => Show (Trie k v) Source # | |

Null (Trie k v) Source # | Empty trie. |

(Ord a, EmbPrj a, EmbPrj b) => EmbPrj (Trie a b) 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.

delete :: Ord k => [k] -> Trie k v -> Trie k v Source #

Delete value at key, but leave subtree intact.

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.