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


-- | Grammar-based compression algorithms SEQUITUR
--   
--   Please see the README on GitHub at
--   <a>https://github.com/msakai/haskell-sequitur#readme</a>
@package sequitur
@version 0.1.0.0


-- | <i>SEQUITUR</i> is a linear-time, online algorithm for producing a
--   context-free grammar from an input sequence. The resulting grammar is
--   a compact representation of original sequence and can be used for data
--   compression.
--   
--   Example:
--   
--   <ul>
--   <li>Input string: <tt>abcabcabcabcabc</tt></li>
--   <li>Resulting grammar<ul><li><tt>S</tt> →
--   <tt>AAB</tt></li><li><tt>A</tt> → <tt>BB</tt></li><li><tt>B</tt> →
--   <tt>abc</tt></li></ul></li>
--   </ul>
--   
--   <i>SEQUITUR</i> consumes input symbols one-by-one and append each
--   symbol at the end of the grammar's start production (<tt>S</tt> in the
--   above example), then substitutes repeating patterns in the given
--   sequence with new rules. <i>SEQUITUR</i> maintains two invariants:
--   
--   <ul>
--   <li><i><i>Digram Uniqueness</i></i> <i>SEQUITUR</i> ensures that no
--   digram (a.k.a. bigram) occurs more than once in the grammar. If a
--   digram (e.g. <tt>ab</tt>) occurs twice, SEQUITUR introduce a fresh
--   non-terminal symbol (e.g. <tt>M</tt>) and a rule (e.g. <tt>M</tt> →
--   <tt>ab</tt>) and replace original occurences with the newly introduced
--   non-terminals. One exception is the cases where two occurrence
--   overlap.</li>
--   <li><i><i>Rule Utility</i></i> If a non-terminal symbol occurs only
--   once, <i>SEQUITUR</i> removes the associated rule and substitute the
--   occurence with the right-hand side of the rule.</li>
--   </ul>
--   
--   References:
--   
--   <ul>
--   <li><a>Sequitur algorithm - Wikipedia</a></li>
--   <li><a>sequitur.info</a></li>
--   <li>Nevill-Manning, C.G. and Witten, I.H. (1997) "<a>Identifying
--   Hierarchical Structure in Sequences: A linear-time algorithm</a>,"
--   Journal of Artificial Intelligence Research, 7, 67-82.</li>
--   </ul>
module Language.Grammar.Sequitur

-- | A grammar is a mappping from non-terminal (left-hand side of the rule)
--   to sequnce of symbols (right hand side of the rule).
--   
--   Non-terminal is represented as a <a>RuleId</a>.
type Grammar a = IntMap [Symbol a]

-- | A non-terminal symbol is represented by an <a>Int</a>.
--   
--   The number <tt>0</tt> is reserved for the start symbol of the grammar.
type RuleId = Int

-- | A symbol is either a terminal symbol (from user-specified type) or a
--   non-terminal symbol which we represent using <a>RuleId</a> type.
data Symbol a
NonTerminal :: !RuleId -> Symbol a
Terminal :: !a -> Symbol a

-- | Construct a grammer from a given sequence of symbols using
--   <i>SEQUITUR</i>.
encode :: (Eq a, Hashable a) => [a] -> Grammar a

-- | Reconstruct a input sequence from a grammar.
--   
--   This is a left-inverse of <a>encode</a>.
--   
--   This function is implemented as
--   
--   <pre>
--   decode = <a>toList</a> . <a>decodeToSeq</a>
--   </pre>
--   
--   and provided just for convenience. For serious usage, use
--   <a>decodeToSeq</a> or <a>decodeLazy</a>.
decode :: HasCallStack => Grammar a -> [a]

-- | A variant of <a>decode</a> but you can consume from the beginning
--   before constructing entire sequence.
decodeLazy :: HasCallStack => Grammar a -> [a]

-- | A variant of <a>decode</a> with possibly better performance.
decodeToSeq :: HasCallStack => Grammar a -> Seq a

-- | <a>Monoid</a>-based folding over the decoded sequence.
--   
--   This function is equivalent to the following definition, is more
--   efficent due to the utilization of sharing.b
--   
--   <pre>
--   decodeToMonoid f = <a>mconcat</a> . <a>map</a> f . <a>decode</a>
--   </pre>
decodeToMonoid :: (Monoid m, HasCallStack) => (a -> m) -> Grammar a -> m

-- | <a>Builder</a> denotes a internal state of the <i>SEQUITUR</i>
--   algorithm.
data Builder s a

-- | Create a new <a>Builder</a>.
newBuilder :: PrimMonad m => m (Builder (PrimState m) a)

-- | Add a new symbol to the end of grammar's start production, and perform
--   normalization to keep the invariants of <i>SEQUITUR</i> algorithm.
add :: (PrimMonad m, Eq a, Hashable a) => Builder (PrimState m) a -> a -> m ()

-- | Retrieve a grammar (as a persistent data structure) from
--   <a>Builder</a>'s internal state.
build :: PrimMonad m => Builder (PrimState m) a -> m (Grammar a)
instance GHC.Generics.Generic (Language.Grammar.Sequitur.Symbol a)
instance GHC.Show.Show a => GHC.Show.Show (Language.Grammar.Sequitur.Symbol a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Language.Grammar.Sequitur.Symbol a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Language.Grammar.Sequitur.Symbol a)
instance GHC.Generics.Generic (Language.Grammar.Sequitur.Node s a)
instance GHC.Classes.Eq (Language.Grammar.Sequitur.Rule s a)
instance Data.Hashable.Class.Hashable (Language.Grammar.Sequitur.Rule s a)
instance GHC.Classes.Eq (Language.Grammar.Sequitur.Node s a)
instance Data.Hashable.Class.Hashable a => Data.Hashable.Class.Hashable (Language.Grammar.Sequitur.Symbol a)