An unordered map from Patterns of strings of type s to values of type a.

The value at the root of the trie, i.e.

value t == lookup mempty t

A pattern is a sequence of Matchers and serves as a key in a pattern trie.

If two patterns are overlapping for an input string, the preference for a match is given by the partial order EqStr > AnyStr on the competing matchers, i.e. towards the more specific pattern. This partial order is witnessed and subsumed by the total order MatchOrd.

The preference for a prefix match is reversed, i.e. for an input string where only a proper prefix is a match for overlapping patterns, the preference is given by the partial order AnyStr > EqStr, i.e. towards the more general pattern. This partial order is witnessed and subsumed by the total order PrefixMatchOrd.

A (chunked) input string to match on a Pattern in a trie.

Note: Input strings can be infinite. Since the tries are always finite, an infinite input string is only consumed until either a match has been found or the applicable paths in the trie have been exhaustively searched.

A Matcher is applied on a single chunk of an input String while looking for a match and either succeeds or fails. If it succeeds, it may Capture the chunk.

A captured chunk of an input String.

Check whether two patterns are overlapping, i.e. whether there exists a String that is a (full) match for both patterns.

>>> let p1 = mempty |> EqStr "a" |> AnyStr
>>> let p2 = mempty |> AnyStr    |> EqStr "b"
>>> let p3 = mempty |> EqStr "a" |> EqStr "c"
>>> overlapping p1 p1
False
>>> overlapping p1 p2
True
>>> overlapping p1 p3
True
>>> overlapping p2 p3
False

A total order for matchers that subsumes the partial order for the preference between overlapping patterns on a match.

>>> MatchOrd AnyStr < MatchOrd (EqStr "a")
True

>>> let p1 = mempty |> EqStr "a" |> EqStr "b"
>>> let p2 = mempty |> AnyStr    |> EqStr "b"
>>> matchOrd p1 > matchOrd p2
True

A total order for matchers that subsumes the partial order for the preference between overlapping patterns on a matchPrefix.

>>> MatchPrefixOrd AnyStr > MatchPrefixOrd (EqStr "a")
True

>>> let p1 = mempty |> EqStr "a" |> EqStr "b"
>>> let p2 = mempty |> AnyStr    |> EqStr "b"
>>> matchPrefixOrd p1 < matchPrefixOrd p2
True

Apply a string to a pattern, returning the unmatched suffix of the pattern together with the captured chunks and the remaining (unmatched) suffix of the input string.

>>> let p = mempty |> EqStr "a" |> AnyStr |> EqStr "c"
>>> let s = ["a", "b", "d"]
>>> apply s p
(fromList [EqStr "c"],fromList [Capture {captured = "b"}],["d"])

Apply a string to a pattern, returning the captures.

>>> let p = mempty |> EqStr "a" |> AnyStr |> EqStr "c"
>>> let s = ["a", "b", "d"]
>>> applyCapture s p
fromList [Capture {captured = "b"}]

(Re)Construct the longest input String matching a prefix of a pattern, using the given captures to satisfy matchers. As long as there are enough captures to satisfy all matchers in the pattern, the resulting string will always be a (full) match for the pattern.

Furthermore, if an input string s is a (full) match for a pattern p, then

unapplyCapture p (applyCapture s p) == s

>>> let p = mempty |> EqStr "a" |> AnyStr |> EqStr "c"
>>> let s = ["a", "b", "c"]
>>> unapplyCapture p (applyCapture s p)
["a","b","c"]

Apply a string to a pattern, returning the captures iff the string is a (full) match for the pattern.

>>> let p = mempty |> EqStr "a" |> AnyStr |> EqStr "c"
>>> applyMatch ["a", "b", "c", "d"] p
Nothing
>>> applyMatch ["a", "b", "c"] p
Just (fromList [Capture {captured = "b"}])

Apply a string to a pattern, returning True iff the string is a (full) match for the pattern.

Apply a string to a pattern, returning the captures iff the string is a prefix match for the pattern.

>>> let p = mempty |> EqStr "a" |> AnyStr |> EqStr "c"
>>> applyMatchPrefix ["a", "b", "c", "d"] p
Just (fromList [Capture {captured = "b"}])

Apply a string to a pattern, returning True iff the string is a prefix match for the pattern.

Create a pattern trie from a list of patterns and associated values.

\(\mathcal{O}(n \cdot k)\), where \(n\) is the length of the list and \(k\) is the length of the longest pattern in the list.

Create a list of patterns and associated values from a pattern trie.

\(\mathcal{O}(n \cdot k)\), where \(n\) is the number of values in the trie and \(k\) is the length of the longest pattern in the trie.

Insert the value for the given pattern into the trie.

\(\Theta(k)\), where \(k\) is the length of the pattern.

Update the value of the given pattern in the trie, if it exists.

\(\mathcal{O}(k)\), where \(k\) is the length of the pattern.

Remove the value for the given pattern from the trie, if it exists.

\(\mathcal{O}(k)\), where \(k\) is the length of the pattern.

Lookup the value of a pattern. If there is no value in the trie for the given pattern, the result is Nothing.

Lookup the value for the longest matching prefix of a pattern, returning it together with the remaining suffix of the pattern. If there is no value in the trie for any prefix of the given pattern, the result is Nothing.

Lookup the trie rooted at the longest prefix of a pattern, returning it together with the remaining suffix of the pattern.

Lookup the value for an input string by matching it against the patterns of a trie. The value of the matching pattern, if any, is returned together with any captured parts of the input string. If the input string does not match any pattern in the trie, the result is Nothing.

Lookup the value for the longest matching prefix of the input string, returning it together with any captured parts and the remaining (unmatched) suffix of the input string. If no prefix of the input string matches any pattern in the trie, the result is Nothing.

Lookup the trie rooted at the longest matching prefix of the input string, returning it together with any captured parts and the remaining (unmatched) suffix of the input string.

In particular, if the input string is a (full) match for a pattern, the returned trie is the subtrie that is rooted at the associated value.

\( O(1) \). Add an element to the right end of a sequence. Mnemonic: a triangle with the single element at the pointy end.