O(1). Is this the empty Trie?

O(n). The number of members in the Trie.

O(n). Is the element in the Trie?

O(n). Creates a Trie of all of the completions of a given member.

let t = fromList ["hello", "house", "roundabout"]
complete "h" t == fromList ["ello", "ouse"]

O(n). Does the Trie contain a member with this prefix?

let t = fromList ["hello", "house", "roundabout"]
hasPref "hell"  t == True
hasPref "hello" t == True
hasPref "abc"   t == False

O(n * m), where m is the longest member of the Trie. Does the Trie contain a member with this suffix?

let t = fromList ["hello", "house", "roundabout"]
hasSuff "hell"  t == False
hasSuff "about" t == True

O(n * m), where m is the longest member of the Trie. Does the Trie contain a member with this infix?

A universal function for querying a Trie with a Foldable. When calling follow base f, a function which takes a Foldable and a Trie is created such that the Foldable is followed until either the Foldable runs out, or its next element can't be found in the Trie.

• If the Foldable is exhausted, f is called on the remaining Trie.
• If the next element in the Foldable cannot be found, base is returned.

This function can be thought of as parallel to alter, but it discards the Trie that's being queried, and only keeps the final level reached with the Foldable.

Examples:

• Member

member = follow False endHere

Here, the first argument False is returned if any element of the Foldable cannot be found, and endHere is called on the final Trie found. i.e., this function follows the Foldable along the Trie, until it can't find the next element, so it returns False, or it ends, so it asks the current Trie if it's a final Trie.

• Complete

complete = follow empty id

Here, the empty Trie is returned if the entire Foldable can't be found, or the final Trie you reach is returned if the Foldable is exhausted.

O(1). The empty Trie.

O(n). Constructs a Trie with one member.

O(n). Insert a new member into the Trie.

O(n). Removes a member from the Trie.

O(n). Removes a member from the Trie if it is present, or inserts it if it is not.

A universal function for modifying a Trie with a Foldable. When called with two arguments, alter atFind atEnd, a function is created, such that

• atEnd is called on the lowest level Trie, i.e., the one reached if the entire Foldable is followed and exhausted.
• atFind is called on the looked-up Trie at every element of the Foldable. This should apply the rest of the alter function, with the rest of the Foldable, depending on the result of the lookup.

This can be thought of as parallel to follow, where follow follows a Foldable, and then deals with either the Foldable being exhausted, or the next element not being found. alter similarly follows a Foldable down a Trie, but it preserves the rest of the Trie, and performs the required cleanup. (i.e, a branch of a Trie with no endHeres set to True is not preserved.)

Examples:

• Insert

insert = alter (. fromMaybe empty) (overEnd (const True))

Here, the first argument to alter says that if the next element of the Foldable can't be found, then just give an empty Trie in its place. When the Foldable is exhausted, though, call 'overEnd (const True)' on the final Trie found. ( 'overEnd (const True)' sets the boolean end flag to True.)

• Delete

delete = alter (=<<) (overEnd (const False))

Here, the first argument says that if the next element cannot be found, pass the Nothing back up along the chain. Otherwise, turns the end to False.

Returns a Trie of the members of the first Trie not existing in the second Trie.

Returns a Trie of the members that exist in eithe the first Trie, or the second Trie, or both.

Returns a Trie of the members that exist in either Trie.

Union of a foldable of Tries.

Returns a Trie of the elements in both the first and second Trie

Folds over the members of a Trie, in list form.

Converts a Trie to a list of its members, in list form.

Creates a Trie from a Foldable of Foldables.

Returns a Trie of the members that begin with the given prefix.

Returns a Trie of the members that end with the given suffix.

A textual representation of the Trie, suitable for debugging.

let t = fromList $ words "house car roundabout round rounders \
                         \carpet cat cap carpentry"
putStrLn (showTrie t)

'c' 'a' 'p'|
        'r'|'p' 'e' 'n' 't' 'r' 'y'|
                    't'|
        't'|
'h' 'o' 'u' 's' 'e'|
'r' 'o' 'u' 'n' 'd'|'a' 'b' 'o' 'u' 't'|
                    'e' 'r' 's'|