-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Predicative tries
--   
--   Predicative tries
@package pred-trie
@version 0.5.1.2


module Data.Trie.Pred.Base.Step
data PredStep k c s a
PredStep :: !k -> !(s -> Maybe r) -> !(Maybe (r -> a)) -> !(c s (r -> a)) -> PredStep k c s a

-- | Unique identifier for the predicate - used for combination
[predTag] :: PredStep k c s a -> !k

-- | The predicate, existentially quantified in the successful result
--   <tt>r</tt>
[predPred] :: PredStep k c s a -> !(s -> Maybe r)

-- | The result function, capturing the quantified result <tt>r</tt> and
--   turning it into a top-level variable <tt>a</tt>.
[predData] :: PredStep k c s a -> !(Maybe (r -> a))

-- | Any sub-trie must have <b>all</b> results preceeded in arity with the
--   result at this step.
[predSub] :: PredStep k c s a -> !(c s (r -> a))

-- | Lookup and delete only - can't arbitrarilly construct a predicated
--   trie.
singletonPred :: (Monoid (c s (r -> a)), Typeable r) => k -> (s -> Maybe r) -> (r -> a) -> PredStep k c s a

-- | Adjacent steps
newtype PredSteps k c s a
PredSteps :: [PredStep k c s a] -> PredSteps k c s a
[unPredSteps] :: PredSteps k c s a -> [PredStep k c s a]

-- | Lookup and delete only - can't arbitrarilly construct a predicated
--   trie.

-- | <tt>Last</tt>-style instance
unionPred :: (Eq k) => PredSteps k c s a -> PredSteps k c s a -> PredSteps k c s a
instance GHC.Base.Functor (c s) => GHC.Base.Functor (Data.Trie.Pred.Base.Step.PredSteps k c s)
instance (GHC.Show.Show k, GHC.Show.Show s) => GHC.Show.Show (Data.Trie.Pred.Base.Step.PredSteps k c s a)
instance Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty s c => Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty s (Data.Trie.Pred.Base.Step.PredSteps k c)
instance (GHC.Classes.Eq s, GHC.Classes.Eq k) => GHC.Base.Monoid (Data.Trie.Pred.Base.Step.PredSteps k c s a)
instance (GHC.Show.Show s, GHC.Show.Show k) => GHC.Show.Show (Data.Trie.Pred.Base.Step.PredStep k c s a)
instance GHC.Base.Functor (c s) => GHC.Base.Functor (Data.Trie.Pred.Base.Step.PredStep k c s)
instance Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty s c => Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty s (Data.Trie.Pred.Base.Step.PredStep k c)


-- | A "predicative" trie is a lookup table where you can use
--   <i>predicates</i> as a method to match a query path, where success is
--   also enriched with <i>any</i> auxiliary data. This library allows you
--   to match a path-chunk (if you consider a query to the different levels
--   of the tree as a <i>list</i>) with a Boolean predicate, augmented with
--   existentially quantified data. This lets us use parsers, regular
--   expressions, and other functions that can be turned into the form of:
--   
--   <pre>
--   forall a. p -&gt; Maybe a
--   </pre>
--   
--   However, because the communicated data is existentially quantified, we
--   <b>cannot</b> revisit a definition - we cannot <tt>update</tt> a
--   predicative node, or change any of its children. The current version
--   of this library forces you to use <a>PredTrie</a> and
--   <a>RootedPredTrie</a> directly (i.e. the data constructors) to build
--   your trie manually.
--   
--   This isn't the actual code, but it's a general idea for how you could
--   build a trie. We build a "tagged" <a>rose-tree</a>, where each node
--   has either a literal name (and is a singleton of the <tt>k</tt> type
--   in our lookup path) or a predicate to consider the current node or its
--   children as the target. You could imagine a "step" of the trie
--   structure as something like this:
--   
--   <pre>
--   data PredTrie k a
--     = Nil
--     | Lit
--         { litTag       :: k
--         , litResult    :: Maybe a
--         , litChildren  :: Maybe (PredTrie k a)
--         }
--     | forall t. Pred
--         { predMatch    :: k -&gt; Maybe t
--         , predResult   :: Maybe (t -&gt; a)
--         , predChildren :: Maybe (PredTrie k a)
--         }
--   </pre>
--   
--   Notice how in the <tt>Pred</tt> constructor, we first <i>create</i>
--   the <tt>t</tt> data in <tt>predMatch</tt>, then <i>consume</i> it in
--   <tt>predResult</tt>. We make a tree out of steps by recursing over the
--   steps.
--   
--   This isn't how it's actually represented internally, but serves to
--   help see the representation. If you want to build tries and perform
--   lookups casually, please see the <a>Data.Trie.Pred.Interface</a>
--   module.
module Data.Trie.Pred.Base
data PredTrie k a
PredTrie :: !(HashMapStep PredTrie k a) -> !(PredSteps k PredTrie k a) -> PredTrie k a

-- | a <i>literal</i> step
[predLits] :: PredTrie k a -> !(HashMapStep PredTrie k a)

-- | a <i>predicative</i> step
[predPreds] :: PredTrie k a -> !(PredSteps k PredTrie k a)
emptyPT :: PredTrie k a

-- | Find the nearest parent node of the requested query, while returning
--   the split of the string that was matched, and what wasn't.
matchPT :: (Hashable k, Eq k) => NonEmpty k -> PredTrie k a -> Maybe (NonEmpty k, a, [k])
matchesPT :: (Hashable k, Eq k) => NonEmpty k -> PredTrie k a -> [(NonEmpty k, a, [k])]
data RootedPredTrie k a
RootedPredTrie :: !(Maybe a) -> !(PredTrie k a) -> RootedPredTrie k a

-- | The "root" node - the path at <tt>[]</tt>
[rootedBase] :: RootedPredTrie k a -> !(Maybe a)

-- | The actual predicative trie
[rootedSub] :: RootedPredTrie k a -> !(PredTrie k a)
emptyRPT :: RootedPredTrie k a
matchRPT :: (Hashable k, Eq k) => [k] -> RootedPredTrie k a -> Maybe ([k], a, [k])
matchesRPT :: (Hashable k, Eq k) => [k] -> RootedPredTrie k a -> [([k], a, [k])]
instance GHC.Base.Functor (Data.Trie.Pred.Base.RootedPredTrie k)
instance (GHC.Show.Show k, GHC.Show.Show a) => GHC.Show.Show (Data.Trie.Pred.Base.RootedPredTrie k a)
instance GHC.Base.Functor (Data.Trie.Pred.Base.PredTrie k)
instance (GHC.Show.Show a, GHC.Show.Show k) => GHC.Show.Show (Data.Trie.Pred.Base.PredTrie k a)
instance (Data.Hashable.Class.Hashable k, GHC.Classes.Eq k) => Data.Trie.Class.Trie [] k Data.Trie.Pred.Base.RootedPredTrie
instance (Data.Hashable.Class.Hashable k, GHC.Classes.Eq k) => GHC.Base.Monoid (Data.Trie.Pred.Base.RootedPredTrie k a)
instance (Test.QuickCheck.Arbitrary.Arbitrary k, Test.QuickCheck.Arbitrary.Arbitrary a, GHC.Classes.Eq k, Data.Hashable.Class.Hashable k) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Trie.Pred.Base.PredTrie k a)
instance (Data.Hashable.Class.Hashable k, GHC.Classes.Eq k) => Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty k Data.Trie.Pred.Base.PredTrie
instance (Data.Hashable.Class.Hashable k, GHC.Classes.Eq k) => GHC.Base.Monoid (Data.Trie.Pred.Base.PredTrie k a)


module Data.Trie.Pred.Interface.Types

-- | Creates a string of nodes - a trie with a width of 1.
class Singleton chunks a trie | chunks a -> trie
singleton :: Singleton chunks a trie => chunks -> a -> trie

-- | Turn a list of tries (<tt>Rooted</tt>) into a node with those children
class Extend eitherUrlChunk child result | eitherUrlChunk child -> result
extend :: Extend eitherUrlChunk child result => eitherUrlChunk -> child -> result

-- | <pre>
--   FoldR Extend start chunks ~ result
--   </pre>
class Extrude chunks start result | chunks start -> result
extrude :: Extrude chunks start result => chunks -> start -> result

-- | A simple proof showing that the list version and function version are
--   interchangable.
type ExtrudeSoundly k cleanxs xs c r = (cleanxs ~ CatMaybes xs, ArityTypeListIso c cleanxs r, Extrude (PathChunks k xs) (RootedPredTrie k c) (RootedPredTrie k r))

-- | Convenience type-level function for removing <a>Nothing</a>s from a
--   type list.

-- | Match a literal key
only :: k -> PathChunk k  'Nothing

-- | Match with a predicate against the url chunk directly.
pred :: k -> (k -> Maybe r) -> PathChunk k ( 'Just r)

-- | The cons-cell for building a query path.
(./) :: PathChunk k mx -> PathChunks k xs -> PathChunks k (mx : xs)
infixr 9 ./

-- | The basis, equivalent to <tt>[]</tt>
nil :: PathChunks k '[]

-- | Constrained to AttoParsec, Regex-Compat and T.Text
data PathChunk k (mx :: Maybe *)

-- | Container when defining route paths
data PathChunks k (xs :: [Maybe *])
instance Data.Trie.Pred.Interface.Types.Singleton (Data.Trie.Pred.Interface.Types.PathChunks k '[]) a (Data.Trie.Pred.Base.RootedPredTrie k a)
instance (Data.Trie.Pred.Interface.Types.Singleton (Data.Trie.Pred.Interface.Types.PathChunks k xs) new trie0, Data.Trie.Pred.Interface.Types.Extend (Data.Trie.Pred.Interface.Types.PathChunk k x) trie0 trie1) => Data.Trie.Pred.Interface.Types.Singleton (Data.Trie.Pred.Interface.Types.PathChunks k (x : xs)) new trie1
instance Data.Trie.Pred.Interface.Types.Extrude (Data.Trie.Pred.Interface.Types.PathChunks k '[]) (Data.Trie.Pred.Base.RootedPredTrie k a) (Data.Trie.Pred.Base.RootedPredTrie k a)
instance (Data.Trie.Pred.Interface.Types.Extrude (Data.Trie.Pred.Interface.Types.PathChunks k xs) trie0 trie1, Data.Trie.Pred.Interface.Types.Extend (Data.Trie.Pred.Interface.Types.PathChunk k x) trie1 trie2) => Data.Trie.Pred.Interface.Types.Extrude (Data.Trie.Pred.Interface.Types.PathChunks k (x : xs)) trie0 trie2
instance (GHC.Classes.Eq k, Data.Hashable.Class.Hashable k) => Data.Trie.Pred.Interface.Types.Extend (Data.Trie.Pred.Interface.Types.PathChunk k 'GHC.Base.Nothing) (Data.Trie.Pred.Base.RootedPredTrie k a) (Data.Trie.Pred.Base.RootedPredTrie k a)
instance (GHC.Classes.Eq k, Data.Hashable.Class.Hashable k, Data.Typeable.Internal.Typeable r) => Data.Trie.Pred.Interface.Types.Extend (Data.Trie.Pred.Interface.Types.PathChunk k ('GHC.Base.Just r)) (Data.Trie.Pred.Base.RootedPredTrie k (r -> a)) (Data.Trie.Pred.Base.RootedPredTrie k a)
instance Data.String.IsString k => Data.String.IsString (Data.Trie.Pred.Interface.Types.PathChunk k 'GHC.Base.Nothing)


-- | This module defines a "builder" monad, which aides in the process of
--   building a trie. It's a monad transformer, so you can use it alongside
--   whichever context you're already working in.
--   
--   <pre>
--   myBuilder :: ( Eq k
--                , Hashable k
--                , MonadIO m
--                ) =&gt; PTBuilder String Int m ()
--   myBuilder = do
--     insertHere 0
--     insert ("some" ./ "path" ./ nil) 1
--     insert ("some" ./ pred "pred-chunk" upperPred ./ nil) 2
--     prefix ("some") $ do
--       insert ("thing" ./ nil) 3
--       insert ("else" ./ nil) 4
--       data &lt;- liftIO (doSomething)
--       insert ("another" ./ "thing" ./ nil) data
--     where
--       uppderPred :: String -&gt; Maybe String
--       uppderPred s | all isUpperCase s = Just s
--                    | otherwise         = Nothing
--   </pre>
--   
--   Then we can get our trie to perform lookups by executing the monad:
--   
--   <pre>
--   main :: IO ()
--   main = do
--     trie &lt;- execPTBuilderT myBuilder
--     print (lookup ["foo", "bar", "baz"] trie)
--   </pre>
module Data.Trie.Pred.Interface
newtype PTBuilderT k v m a
PTBuilderT :: StateT (RootedPredTrie k v) m a -> PTBuilderT k v m a
[runPTBuilderT] :: PTBuilderT k v m a -> StateT (RootedPredTrie k v) m a
execPTBuilderT :: (Monad m, Eq k, Hashable k) => PTBuilderT k v m a -> m (RootedPredTrie k v)
insert :: (Monad m, Eq k, Hashable k, Singleton (PathChunks k xs) childContent (RootedPredTrie k resultContent), cleanxs ~ CatMaybes xs, ArityTypeListIso childContent cleanxs resultContent) => PathChunks k xs -> childContent -> PTBuilderT k resultContent m ()
insertHere :: (Monad m, Eq k, Hashable k) => v -> PTBuilderT k v m ()
prefix :: (Monad m, Eq k, Hashable k, cleanxs ~ CatMaybes xs, ExtrudeSoundly k cleanxs xs childContent resultContent) => PathChunks k xs -> PTBuilderT k childContent m () -> PTBuilderT k resultContent m ()

-- | Match a literal key
only :: k -> PathChunk k  'Nothing

-- | Match with a predicate against the url chunk directly.
pred :: k -> (k -> Maybe r) -> PathChunk k ( 'Just r)

-- | The cons-cell for building a query path.
(./) :: PathChunk k mx -> PathChunks k xs -> PathChunks k (mx : xs)
infixr 9 ./

-- | The basis, equivalent to <tt>[]</tt>
nil :: PathChunks k '[]
lookup :: (Eq k, Hashable k) => [k] -> RootedPredTrie k a -> Maybe a
match :: (Hashable k, Eq k) => [k] -> RootedPredTrie k a -> Maybe ([k], a, [k])
matches :: (Hashable k, Eq k) => [k] -> RootedPredTrie k a -> [([k], a, [k])]
delete :: (Eq k, Hashable k) => [k] -> RootedPredTrie k a -> RootedPredTrie k a
data RootedPredTrie k a

-- | Container when defining route paths
data PathChunks k (xs :: [Maybe *])

-- | Constrained to AttoParsec, Regex-Compat and T.Text
data PathChunk k (mx :: Maybe *)
instance GHC.Base.Monad m => Control.Monad.State.Class.MonadState (Data.Trie.Pred.Base.RootedPredTrie k v) (Data.Trie.Pred.Interface.PTBuilderT k v m)
instance Control.Monad.Trans.Class.MonadTrans (Data.Trie.Pred.Interface.PTBuilderT k v)
instance GHC.Base.Monad m => GHC.Base.Monad (Data.Trie.Pred.Interface.PTBuilderT k v m)
instance GHC.Base.Monad m => GHC.Base.Applicative (Data.Trie.Pred.Interface.PTBuilderT k v m)
instance GHC.Base.Functor m => GHC.Base.Functor (Data.Trie.Pred.Interface.PTBuilderT k v m)
instance (GHC.Base.Monad m, GHC.Classes.Eq k, Data.Hashable.Class.Hashable k) => Control.Monad.Writer.Class.MonadWriter (Data.Trie.Pred.Base.RootedPredTrie k v) (Data.Trie.Pred.Interface.PTBuilderT k v m)

module Data.Trie.Pred

module Data.Trie.Pred.Mutable
data PredStep s k r
PredStep :: {-# UNPACK #-} !(PredKey s k a) -> !(Maybe (a -> r)) -> !(HashTableTrie s k (a -> r)) -> PredStep s k r
[predPred] :: PredStep s k r -> {-# UNPACK #-} !(PredKey s k a)
[predData] :: PredStep s k r -> !(Maybe (a -> r))
[predSub] :: PredStep s k r -> !(HashTableTrie s k (a -> r))
data RawValue s k a
RawValue :: !(Maybe a) -> !(HashTableTrie s k a) -> RawValue s k a
[rawValue] :: RawValue s k a -> !(Maybe a)
[rawChildren] :: RawValue s k a -> !(HashTableTrie s k a)
data HashTableTrie s k a
HashTableTrie :: {-# UNPACK #-} !(HashTable s k (RawValue s k a)) -> [PredStep s k a] -> HashTableTrie s k a
[rawValues] :: HashTableTrie s k a -> {-# UNPACK #-} !(HashTable s k (RawValue s k a))
[predPreds] :: HashTableTrie s k a -> [PredStep s k a]
new :: ST s (HashTableTrie s k a)
insert :: (Eq k, Hashable k) => NonEmpty k -> a -> HashTableTrie s k a -> ST s (HashTableTrie s k a)
lookup :: (Eq k, Hashable k, Typeable s, Typeable k) => PredSet s k -> NonEmpty k -> HashTableTrie s k a -> ST s (Maybe a)
match :: (Eq k, Hashable k, Typeable s, Typeable k) => PredSet s k -> NonEmpty k -> HashTableTrie s k a -> ST s (Maybe (NonEmpty k, a, [k]))
matches :: (Eq k, Hashable k, Typeable s, Typeable k) => PredSet s k -> NonEmpty k -> HashTableTrie s k a -> ST s [(NonEmpty k, a, [k])]
data RootedHashTableTrie s k a
RootedHashTableTrie :: !(Maybe a) -> !(HashTableTrie s k a) -> {-# UNPACK #-} !(PredSet s k) -> RootedHashTableTrie s k a
[rootedBase] :: RootedHashTableTrie s k a -> !(Maybe a)
[rootedSub] :: RootedHashTableTrie s k a -> !(HashTableTrie s k a)
[rootedPredSet] :: RootedHashTableTrie s k a -> {-# UNPACK #-} !(PredSet s k)
newR :: ST s (RootedHashTableTrie s k a)
lookupR :: (Eq k, Hashable k, Typeable s, Typeable k, Typeable a) => [k] -> RootedHashTableTrie s k a -> ST s (Maybe a)
matchR :: (Eq k, Hashable k, Typeable s, Typeable k, Typeable a) => [k] -> RootedHashTableTrie s k a -> ST s (Maybe ([k], a, [k]))
matchesR :: (Eq k, Hashable k, Typeable s, Typeable k, Typeable a) => [k] -> RootedHashTableTrie s k a -> ST s [([k], a, [k])]

module Data.Trie.Pred.Mutable.Morph
toMutableRooted :: (Eq k, Hashable k, Ord k, Typeable s, Typeable k, Typeable a) => RootedPredTrie k a -> ST s (RootedHashTableTrie s k a)
toMutable :: (Eq k, Hashable k, Ord k, Typeable s, Typeable k, Typeable a) => PredSet s k -> PredTrie k a -> ST s (HashTableTrie s k a)
toHashTableTrie :: (Eq k, Hashable k, Ord k, Typeable s, Typeable k, Typeable a) => STRef s (HMap k) -> PredSet s k -> PredTrie k a -> ST s (HashTableTrie s k a)
toRawValue :: (Eq k, Hashable k, Ord k, Typeable s, Typeable k, Typeable a) => STRef s (HMap k) -> PredSet s k -> HashMapChildren PredTrie k a -> ST s (RawValue s k a)
toHashTable :: (Eq k, Hashable k) => HashMap k a -> ST s (HashTable s k a)
toMutablePredStep :: (Ord k, Eq k, Hashable k, Typeable s, Typeable k, Typeable a) => STRef s (HMap k) -> PredSet s k -> PredStep k PredTrie k a -> ST s (PredStep s k a)
type HMap k = Map k Dynamic
insertPredKey :: (Ord k', Typeable s, Typeable k, Typeable a) => k' -> PredKey s k a -> HMap k' -> HMap k'
lookupPredKey :: (Ord k', Typeable s, Typeable k, Typeable a) => k' -> ST s (k -> Maybe a) -> HMap k' -> ST s (Maybe (PredKey s k a))
