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

Language | Haskell98 |

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

- data 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)]
- 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]
- tests :: IO Bool

# Documentation

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.

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.