StringTrie

A trie mapping unique strings to values.

Data structure

type alias Trie a =

Trie Char a

A trie mapping keys to values, where the keys are String.

This version of Trie is a lot like a Dict except the keys are must be strings. Keys that have common prefixes share space, and it is possible to efficiently search for keys matching a particular prefix.

Build

empty : Trie a

Create an empty trie.

singleton : String -> a -> Trie a

Create a trie with one key-value pair.

insert : String -> a -> Trie a -> Trie a

Insert a key-value pair into a trie. Replaces value when there is a collision.

update : String -> (Maybe a -> Maybe a) -> Trie a -> Trie a

Update the value of a trie for a specific key with a given function.

remove : String -> Trie a -> Trie a

Remove a key-value pair from a trie. If the key is not found, no changes are made.

Query

isEmpty : Trie a -> Bool

Determine if a trie is empty.

`isEmpty empty == True`

member : String -> Trie a -> Bool

Determine if a whole key is in a trie.

get : String -> Trie a -> Maybe a

Get the value associated with a key. If the key is not found, return Nothing.

size : Trie a -> Int

Determine the number of key-value pairs in the trie.

Lists

keys : Trie a -> List String

Get all of the keys in a trie, sorted from lowest to highest.

values : Trie a -> List a

Get all of the values in a trie, in the order of their keys.

toList : Trie a -> List ( String, a )

Convert a trie into an association list of key-value pairs, sorted by keys.

fromList : List ( String, a ) -> Trie a

Convert an association list into a trie.

Transform

map : (String -> a -> b) -> Trie a -> Trie b

Apply a function to all values in a trie.

foldl : (String -> a -> b -> b) -> b -> Trie a -> b

Fold over the key-value pairs in a trie from lowest key to highest key.

foldr : (String -> a -> b -> b) -> b -> Trie a -> b

Fold over the key-value pairs in a trie from highest key to lowest key.

Due to the way shorter keys are nearer the top of the trie this fold function has to hold more pending nodes in memory in order to fold in order from the highest key to the lowest key. For this reason it is less efficient than foldl and foldl should be preferred unless the ordering is important.

filter : (String -> a -> Bool) -> Trie a -> Trie a

Keep only the key-value pairs that pass the given test.

partition : (String -> a -> Bool) -> Trie a -> ( Trie a, Trie a )

Partition a trie according to some test. The first trie contains all key-value pairs which passed the test, and the second contains the pairs that did not.

Combine

union : Trie a -> Trie a -> Trie a

Combine two tries. If there is a collision, preference is given to the first trie.

intersect : Trie a -> Trie a -> Trie a

Keep a key-value pair when its key appears in the second trie. Preference is given to values in the first dictionary.

diff : Trie a -> Trie b -> Trie a

Keep a key-value pair when its key does not appear in the second trie.

merge :

(String -> a -> result -> result)

-> (String -> a -> b -> result -> result)

-> (String -> b -> result -> result)

-> Trie a

-> Trie b

-> result

The most general way of combining two tries. You provide three accumulators for when a given key appears:

Only in the left trie.
In both tries.
Only in the right trie.

You then traverse all the keys from lowest to highest, building up whatever you want.

Trie specific search operations

type alias Match comparable =

Match comparable

Match describes how a flexible search over a trie will proceed.

Break - do not explore any more below the current prefix.
Wildcard - continue with all possible next keys below the current prefix.
ContinueIf - continue with the next key provided it exactly matches the comparable specified.
ContinueIfOneOf - continue with the next key provided it matches one of the comparables specified.

The Break, ContinueIf and ContinueIfOneOf options allow a trie to be traversed efficiently without exploring unnecessary keys.

The Wildcard and ContinueIfOneOf options allow flexible matching within a trie. Functions such as case-insensitive matching, fuzzy matching or regular expression matching can be implemented using these options.

break : Match comparable

A match step that breaks on the current node.

wildcard : Match comparable

A match step follows all nodes after the current node.

continueIf : comparable -> Match comparable

A match step that follows only one node that exactly matches the next comparable in the key.

continueIfOneOf : List comparable -> Match comparable

A match step that follows one or more nodes that exactly match the specified next comparables in the key.

match :

(Maybe Char -> Maybe a -> context -> b -> ( b, context, Match Char ))

-> b

-> context

-> Trie a

-> b

Performs a flexible matching fold over a trie from the lowest to the highest key in order.

Suppose the function passed in has this form:

searchFn maybeKeyPart maybeValue context accum = ...

The maybeKeyPart parameter will be set to the next item from the key being scanned as a list. This is a Maybe as the empty list can be a key in a trie. In practice the value Nothing will only be passed to this function on the first call when the empty key is present.

The maybeValue parameter will be set to any value found at the current position in the trie.

The context parameter will be held against the particular node in the trie being explored. When and if that node is returned to in order to explore other key paths in the trie, the context for that node will be restored. The trie is explored using a depth first search, and the contexts are held in a stack of pending nodes to explore. An example use of the context might be to hold the remaining portion of a key to be matched.

The accum parameter is used like the accumulator in a fold, it can be updated on each node explored.

The context parameter is restored when back-tracking to explore other possible keys, but the accum parameter is carried accross the whole search. In that sense context is like a local variable and accum is like a global variable.

expand : String -> Trie a -> List ( String, a )

Given a prefix, finds all keys that begin with that prefix.

isPrefix : String -> Trie a -> Bool

Given a prefix, checks if there are keys that begin with that prefix.

subtrie : String -> Trie a -> Maybe (Trie a)

Given a prefix, finds any sub-trie containing the key-value pairs where the original keys begin with that prefix. The keys in the sub-trie will only consist of the remaining portion of the key after the prefix.

String specific operations

expandIgnoreCase : String -> Trie a -> List ( String, a )

Given a prefix, finds all keys that begin with that prefix ignoring the case of characters in the prefix or in the trie.

elm-scotland/elm-tries/1.0.0