-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Pattern tries
--
-- Simple pattern tries for structured keys, where lookups can capture
-- (parts of) the input strings.
@package pattern-trie
@version 0.1.0
-- | A variant of a (radix) trie with the following characteristics:
--
--
-- - Keys are simple Patterns composed of Matchers and
-- hence a single key can match multiple input Strings.
-- - Looking up a match for a String can Capture
-- parts of the string.
-- - Both patterns and input strings are understood as being composed
-- of (indivisible) chunks of strings of a generic type s
-- (typically instantiated to either Text or ByteString).
-- More precisely, every chunk of an input String is tested
-- against a Matcher of a Pattern in sequence. As a result,
-- pattern tries usually end up less compact than more general tries,
-- since sharing of prefixes as well as all operations are limited to the
-- granularity of these chunks.
--
--
-- These characteristics hint at the primary intended use-case, whereby
-- keys have a "natural" decomposition into chunks and the same chunks
-- are heavily shared by different keys, e.g. as in directory trees. A
-- pattern trie allows to associate values with simple patterns, whereby
-- a single value can essentially be looked up by all strings matching a
-- pattern, thereby capturing parts of it.
--
-- Strictness: A Trie is strict in the spine as well as the
-- values (WHNF).
--
-- Ordering: The order of keys and thus elements is unspecified.
-- No particular order may be assumed by folds and traversals, whose
-- combining operations should hence be commutative.
--
-- Example:
--
--
-- >>> :set -XOverloadedStrings
--
--
--
-- >>> import Data.ByteString (ByteString)
--
--
--
-- >>> let p1 = mempty |> EqStr "home" |> EqStr "alice" |> EqStr "tmp"
--
-- >>> let p2 = mempty |> EqStr "home" |> AnyStr |> EqStr "music"
--
-- >>> let p3 = mempty |> EqStr "data" |> EqStr "bob" |> EqStr "books"
--
-- >>> let p4 = mempty |> EqStr "data" |> AnyStr |> EqStr "books"
--
-- >>> let p5 = mempty |> EqStr "data" |> AnyStr |> EqStr "books" |> EqStr "sicp"
--
--
--
-- >>> let trie = fromAssocList $ [p1,p2,p3,p4,p5] `zip` [1..] :: Trie ByteString Int
--
--
--
-- >>> match ["home","alice","tmp"] trie
-- Just (1,fromList [])
--
--
--
-- >>> match ["home","bob","tmp"] trie
-- Nothing
--
--
--
-- >>> match ["home","alice","music"] trie
-- Just (2,fromList [Capture {captured = "alice"}])
--
--
--
-- >>> match ["home","bob","music"] trie
-- Just (2,fromList [Capture {captured = "bob"}])
--
--
--
-- >>> match ["data","bob","books"] trie
-- Just (3,fromList [])
--
--
--
-- >>> match ["data","alice","books"] trie
-- Just (4,fromList [Capture {captured = "alice"}])
--
--
--
-- >>> match ["data","alice","books","sicp"] trie
-- Just (5,fromList [Capture {captured = "alice"}])
--
--
--
-- >>> match ["data","bob","books","sicp"] trie
-- Just (5,fromList [Capture {captured = "bob"}])
--
--
--
-- >>> matchPrefix ["data","alice","books","wonderland"] trie
-- Just (4,fromList [Capture {captured = "alice"}],["wonderland"])
--
--
--
-- >>> matchPrefix ["data","bob","books","wonderland"] trie
-- Just (4,fromList [Capture {captured = "bob"}],["wonderland"])
--
--
--
-- >>> let (t,c,s) = matchPrefixTrie ["data","bob","books","wonderland"] trie
--
-- >>> (value t, c, s)
-- (Just 4,fromList [Capture {captured = "bob"}],["wonderland"])
--
module Data.Trie.Pattern
-- | An unordered map from Patterns of strings of type s to
-- values of type a.
data Trie s a
-- | The value at the root of the trie, i.e.
--
--
-- value t == lookup mempty t
--
value :: Trie s a -> (Maybe a)
-- | 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.
type Pattern s = Seq (Matcher s)
-- | 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.
type Str s = [s]
-- | 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.
data Matcher s
-- | Match and capture an arbitrary chunk of an input string.
AnyStr :: Matcher s
-- | Match a chunk of an input string exactly, capturing nothing.
EqStr :: !s -> Matcher s
-- | A captured chunk of an input String.
newtype Capture s
Capture :: s -> Capture s
[captured] :: Capture s -> s
-- | 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
--
overlapping :: Eq s => Pattern s -> Pattern s -> Bool
-- | 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
--
newtype MatchOrd s
MatchOrd :: (Matcher s) -> MatchOrd s
-- | 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
--
newtype MatchPrefixOrd s
MatchPrefixOrd :: (Matcher s) -> MatchPrefixOrd s
matchOrd :: Pattern s -> Seq (MatchOrd s)
matchPrefixOrd :: Pattern s -> Seq (MatchPrefixOrd s)
-- | 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 :: Eq s => Str s -> Pattern s -> (Pattern s, Seq (Capture s), Str s)
-- | 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"}]
--
applyCapture :: Eq s => Str s -> Pattern s -> Seq (Capture s)
-- | (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"]
--
unapplyCapture :: Pattern s -> Seq (Capture s) -> Str s
-- | 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"}])
--
applyMatch :: Eq s => Str s -> Pattern s -> Maybe (Seq (Capture s))
-- | Apply a string to a pattern, returning True iff the string is a
-- (full) match for the pattern.
applyMatches :: Eq s => Str s -> Pattern s -> Bool
-- | 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"}])
--
applyMatchPrefix :: Eq s => Str s -> Pattern s -> Maybe (Seq (Capture s))
-- | Apply a string to a pattern, returning True iff the string is a
-- prefix match for the pattern.
applyMatchesPrefix :: Eq s => Str s -> Pattern s -> Bool
-- | Create a pattern trie from a list of patterns and associated values.
--
-- <math>, where <math> is the length of the list and
-- <math> is the length of the longest pattern in the list.
fromAssocList :: (Eq s, Hashable s) => [(Pattern s, a)] -> Trie s a
-- | Create a list of patterns and associated values from a pattern trie.
--
-- <math>, where <math> is the number of values in the trie
-- and <math> is the length of the longest pattern in the trie.
toAssocList :: (Eq s, Hashable s) => Trie s a -> [(Pattern s, a)]
-- | Insert the value for the given pattern into the trie.
--
-- <math>, where <math> is the length of the pattern.
insert :: (Eq s, Hashable s) => Pattern s -> a -> Trie s a -> Trie s a
-- | Update the value of the given pattern in the trie, if it exists.
--
-- <math>, where <math> is the length of the pattern.
adjust :: (Eq s, Hashable s) => Pattern s -> (a -> a) -> Trie s a -> Trie s a
-- | Remove the value for the given pattern from the trie, if it exists.
--
-- <math>, where <math> is the length of the pattern.
delete :: (Eq s, Hashable s) => Pattern s -> Trie s a -> Trie s a
-- | Lookup the value of a pattern. If there is no value in the trie for
-- the given pattern, the result is Nothing.
lookup :: (Eq s, Hashable s) => Pattern s -> Trie s a -> Maybe a
-- | 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.
lookupPrefix :: (Eq s, Hashable s) => Pattern s -> Trie s a -> Maybe (a, Pattern s)
-- | Lookup the trie rooted at the longest prefix of a pattern, returning
-- it together with the remaining suffix of the pattern.
lookupPrefixTrie :: (Eq s, Hashable s) => Pattern s -> Trie s a -> (Trie s a, Pattern s)
-- | 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.
match :: (Eq s, Hashable s) => Str s -> Trie s a -> Maybe (a, Seq (Capture s))
-- | 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.
matchPrefix :: (Eq s, Hashable s) => Str s -> Trie s a -> Maybe (a, Seq (Capture s), Str s)
-- | 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.
matchPrefixTrie :: (Eq s, Hashable s) => Str s -> Trie s a -> (Trie s a, Seq (Capture s), Str s)
traverseWithKey :: Applicative f => (Pattern s -> a -> f b) -> Trie s a -> f (Trie s b)
foldMapWithKey :: Monoid m => (Pattern s -> a -> m) -> Trie s a -> m
foldrWithKey :: (Pattern s -> a -> b -> b) -> b -> Trie s a -> b
-- | <math>. Add an element to the right end of a sequence. Mnemonic:
-- a triangle with the single element at the pointy end.
(|>) :: () => Seq a -> a -> Seq a
infixl 5 |>
instance GHC.Classes.Eq s => GHC.Classes.Eq (Data.Trie.Pattern.MatchOrd s)
instance GHC.Classes.Eq s => GHC.Classes.Eq (Data.Trie.Pattern.MatchPrefixOrd s)
instance Control.DeepSeq.NFData s => Control.DeepSeq.NFData (Data.Trie.Pattern.Matcher s)
instance GHC.Generics.Generic (Data.Trie.Pattern.Matcher s)
instance GHC.Read.Read s => GHC.Read.Read (Data.Trie.Pattern.Matcher s)
instance GHC.Show.Show s => GHC.Show.Show (Data.Trie.Pattern.Matcher s)
instance GHC.Classes.Eq s => GHC.Classes.Eq (Data.Trie.Pattern.Matcher s)
instance Control.DeepSeq.NFData s => Control.DeepSeq.NFData (Data.Trie.Pattern.Capture s)
instance GHC.Generics.Generic (Data.Trie.Pattern.Capture s)
instance GHC.Read.Read s => GHC.Read.Read (Data.Trie.Pattern.Capture s)
instance GHC.Show.Show s => GHC.Show.Show (Data.Trie.Pattern.Capture s)
instance GHC.Classes.Ord s => GHC.Classes.Ord (Data.Trie.Pattern.Capture s)
instance GHC.Classes.Eq s => GHC.Classes.Eq (Data.Trie.Pattern.Capture s)
instance (Control.DeepSeq.NFData s, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (Data.Trie.Pattern.Trie s a)
instance GHC.Generics.Generic (Data.Trie.Pattern.Trie s a)
instance (GHC.Classes.Eq s, Data.Hashable.Class.Hashable s, GHC.Read.Read s, GHC.Read.Read a) => GHC.Read.Read (Data.Trie.Pattern.Trie s a)
instance (GHC.Show.Show s, GHC.Show.Show a) => GHC.Show.Show (Data.Trie.Pattern.Trie s a)
instance (GHC.Classes.Eq s, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Trie.Pattern.Trie s a)
instance GHC.Classes.Ord s => GHC.Classes.Ord (Data.Trie.Pattern.MatchOrd s)
instance GHC.Classes.Ord s => GHC.Classes.Ord (Data.Trie.Pattern.MatchPrefixOrd s)
instance Data.Traversable.Traversable (Data.Trie.Pattern.Trie s)
instance GHC.Base.Functor (Data.Trie.Pattern.Trie s)
instance Data.Foldable.Foldable (Data.Trie.Pattern.Trie s)
instance (GHC.Classes.Eq s, Data.Hashable.Class.Hashable s) => GHC.Base.Semigroup (Data.Trie.Pattern.Trie s a)
instance (GHC.Classes.Eq s, Data.Hashable.Class.Hashable s) => GHC.Base.Monoid (Data.Trie.Pattern.Trie s a)