Data.Trie

A map from ByteStrings to a. For all the generic functions, note that tries are strict in the Maybe but not in a.

The Monad instance is strange. If a key k1 is a prefix of other keys, then results from binding the value at k1 will override values from longer keys when they collide. If this is useful for anything, or if there's a more sensible instance, I'd be curious to know.

\mathcal{O}(1). Construct the empty trie.

\mathcal{O}(1). Is the trie empty?

\mathcal{O}(1). Construct a singleton trie.

\mathcal{O}(n). Get count of elements in trie.

Convert association list into a trie. On key conflict, values earlier in the list shadow later ones.

Convert a trie into a list using a function. Resulting values are in key-sorted order.

Warning: This function suffers Bug #25.

Convert trie into association list. The list is ordered according to the keys.

Warning: This function suffers Bug #25.

Return all keys in the trie, in sorted order.

Warning: This function suffers Bug #25.

Return all values in the trie, in key-sorted order.

Note: Prior to version 0.2.7, this function suffered Bug #25; but it no longer does.

Generic function to find a value (if it exists) and the subtrie rooted at the prefix.

Return the value associated with a query string if it exists.

Does a string have a value in the trie?

Return the subtrie containing all keys beginning with a prefix.

Given a query, find the longest prefix with an associated value in the trie, and return that prefix, its value, and the remainder of the query.

Given a query, find the shortest prefix with an associated value in the trie, and return that prefix, its value, and the remainder of the query.

Given a query, find all prefixes with associated values in the trie, and return their (prefix, value, remainder) triples in order from shortest prefix to longest. This function is a good producer for list fusion.

Insert a new key. If the key is already present, overrides the old value

Apply a function to the value at a key. If the key is not present, then the trie is returned unaltered.

Alter the value associated with a given key. If the key is not present, then the trie is returned unaltered. See alterBy if you are interested in inserting new keys or deleting old keys. Because this function does not need to worry about changing the trie structure, it is somewhat faster than alterBy.

Note: Prior to version 0.2.6 this function was exported from Data.Trie.Internal instead.

Generic function to alter a trie by one element with a function to resolve conflicts (or non-conflicts).

Remove the value stored at a key.

Remove all keys beginning with a prefix.

Take the union of two tries, using a function to resolve collisions. This can only define the space of functions between union and symmetric difference but, with those two, all set operations can be defined (albeit inefficiently).

Take the union of two tries, resolving conflicts by choosing the value from the left trie.

Take the union of two tries, resolving conflicts by choosing the value from the right trie.

Take the intersection of two tries, using a function to resolve collisions.

Take the intersection of two tries, with values from the left trie.

Take the intersection of two tries, with values from the right trie.

Keyed version of filterMap.

Warning: This function suffers Bug #25.

Apply a function to all values, potentially removing them.

Laws

Fission

filterMap f ≡ fmap (fromJust . f) . filter (isJust . f)

Fusion

fmap f . filter g ≡ filterMap (\v -> f v <$ guard (g v))

Conservation

filterMap (Just . f) ≡ fmap f

Composition

filterMap f . filterMap g ≡ filterMap (f <=< g)

The fission/fusion laws are essentially the same, they differ only in which direction is more "natural" for use as a rewrite rule. The conservation law is just a special case of fusion, but it's a particularly helpful one to take note of.