úÎ!pÛm)@      !"#$%&'()*+,-./0123456789:;<=>?None68:KNkí @ pattern-trie8A choice point for backtracking to alternative branches. pattern-trieqA total order for matchers that subsumes the partial order for the preference between overlapping patterns on a #.&MatchOrd AnyStr < MatchOrd (EqStr "a")True)let p1 = mempty |> EqStr "a" |> EqStr "b")let p2 = mempty |> AnyStr |> EqStr "b"matchOrd p1 > matchOrd p2True pattern-trieqA total order for matchers that subsumes the partial order for the preference between overlapping patterns on a ".2MatchPrefixOrd AnyStr > MatchPrefixOrd (EqStr "a")True)let p1 = mempty |> EqStr "a" |> EqStr "b")let p2 = mempty |> AnyStr |> EqStr "b"%matchPrefixOrd p1 < matchPrefixOrd p2True pattern-trieA * is applied on a single chunk of an input  ing while looking for a # and either succeeds or fails. If it succeeds, it may  the chunk. pattern-trie8Match and capture an arbitrary chunk of an input string. pattern-trie<Match a chunk of an input string exactly, capturing nothing. pattern-trieA captured chunk of an input  ing.  pattern-trieA (chunked) input string to # on a   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.  pattern-trieA pattern is a sequence of )s and serves as a key in a pattern trie.KIf two patterns are overlapping for an input string, the preference for a # 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 .·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 > EqStrk, i.e. towards the more general pattern. This partial order is witnessed and subsumed by the total order PrefixMatchOrd.  pattern-trieAn unordered map from  s of strings of type s to values of type a. pattern-trie'The value at the root of the trie, i.e.  value t ==   mempty t  pattern-trieICheck whether two patterns are overlapping, i.e. whether there exists a  -ing 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 p1Falseoverlapping p1 p2Trueoverlapping p1 p3Trueoverlapping p2 p3False pattern-trie¨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.2let p = mempty |> EqStr "a" |> AnyStr |> EqStr "c"let s = ["a", "b", "d"] apply s p@(fromList [EqStr "c"],fromList [Capture {captured = "b"}],["d"]) pattern-trie4Apply a string to a pattern, returning the captures.2let p = mempty |> EqStr "a" |> AnyStr |> EqStr "c"let s = ["a", "b", "d"]applyCapture s p#fromList [Capture {captured = "b"}] pattern-trie (Re)Construct the longest input  æing 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 2let p = mempty |> EqStr "a" |> AnyStr |> EqStr "c"let s = ["a", "b", "c"]#unapplyCapture p (applyCapture s p) ["a","b","c"] pattern-triefApply a string to a pattern, returning the captures iff the string is a (full) match for the pattern.2let p = mempty |> EqStr "a" |> AnyStr |> EqStr "c"!applyMatch ["a", "b", "c", "d"] pNothingapplyMatch ["a", "b", "c"] p*Just (fromList [Capture {captured = "b"}]) pattern-trie'Apply a string to a pattern, returning A3 iff the string is a (full) match for the pattern. pattern-triefApply a string to a pattern, returning the captures iff the string is a prefix match for the pattern.2let p = mempty |> EqStr "a" |> AnyStr |> EqStr "c"'applyMatchPrefix ["a", "b", "c", "d"] p*Just (fromList [Capture {captured = "b"}]) pattern-trie'Apply a string to a pattern, returning A3 iff the string is a prefix match for the pattern. pattern-trieDCreate 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 k2 is the length of the longest pattern in the list. pattern-trieDCreate 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 k2 is the length of the longest pattern in the trie. pattern-trie5Insert the value for the given pattern into the trie. \Theta(k), where k is the length of the pattern. pattern-trie@Update the value of the given pattern in the trie, if it exists.\mathcal{O}(k), where k is the length of the pattern. pattern-trieCRemove the value for the given pattern from the trie, if it exists.\mathcal{O}(k), where k is the length of the pattern. pattern-trie{Lookup the trie rooted at the longest prefix of a pattern, returning it together with the remaining suffix of the pattern. pattern-trieÖ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 B.  pattern-triegLookup the value of a pattern. If there is no value in the trie for the given pattern, the result is B.! pattern-trie´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 ." pattern-trieÿ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 B.# pattern-trieÿ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 B.' pattern-trieNote: mappend = (<>).( pattern-trieNote (left preference)2: If two tries have a value attached to the same   (i.e. to the same key), then t1 <> t2 preserves the value of t1.'  !"#$%&'    #"!$%&C       !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGH)pattern-trie-0.1.0-D9GRwK2wxQCEPaAGzi8DAQData.Trie.Patterncontainers-0.5.11.0Data.Sequence.Internal|>MatchOrdMatchPrefixOrdMatcherAnyStrEqStrCapturecapturedStrPatternTrievaluematchPrefixOrdmatchOrd overlappingapply applyCaptureunapplyCapture applyMatch applyMatchesapplyMatchPrefixapplyMatchesPrefix fromAssocList toAssocListinsertadjustdeletelookupPrefixTrie lookupPrefixlookupmatchPrefixTrie matchPrefixmatchtraverseWithKeyfoldMapWithKey foldrWithKey $fMonoidTrie$fSemigroupTrie$fFoldableTrie $fFunctorTrie$fTraversableTrie$fOrdMatchPrefixOrd $fOrdMatchOrd$fEqTrie $fShowTrie $fReadTrie $fGenericTrie $fNFDataTrie $fEqCapture $fOrdCapture $fShowCapture $fReadCapture$fGenericCapture$fNFDataCapture $fEqMatcher $fShowMatcher $fReadMatcher$fGenericMatcher$fNFDataMatcher$fEqMatchPrefixOrd $fEqMatchOrdChoiceghc-prim GHC.TypesTruebaseGHC.BaseNothing