-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Grammar-based compression algorithms SEQUITUR -- -- Please see the README on GitHub at -- https://github.com/msakai/haskell-sequitur#readme @package sequitur @version 0.2.0.0 -- | SEQUITUR is a linear-time, online algorithm for producing a -- context-free grammar from an input sequence. The resulting grammar is -- a compact representation of the original sequence and can be used for -- data compression. -- -- Example: -- -- -- -- SEQUITUR consumes input symbols one-by-one and appends each -- symbol at the end of the grammar's start production (S in the -- above example), then substitutes repeating patterns in the given -- sequence with new rules. SEQUITUR maintains two invariants: -- -- -- -- References: -- -- module Language.Grammar.Sequitur -- | Since a grammar generated by SEQUITUR has exactly one rule for -- each non-terminal symbol, a grammar is represented as a mapping from -- non-terminal symbols (left-hand sides of the rules) to sequences of -- symbols (right-hand side of the rules). -- -- For example, a grammar -- -- -- -- is represented as -- -- 
--   Grammar (fromList
--     [ (0, [NonTerminal 1, NonTerminal 1, NonTerminal 2])
--     , (1, [NonTerminal 2, NonTerminal 2])
--     , (2, [Terminal 'a', Terminal 'b', Terminal 'c'])
--     ])
--
-- -- Since a grammar generated by SEQUITUR produces exactly one -- sequence, we can identify the grammar with the produced sequence. -- Therefore, Grammar type is an instance of Foldable, -- IsList, and IsString. newtype Grammar a Grammar :: IntMap [Symbol a] -> Grammar a [unGrammar] :: Grammar a -> IntMap [Symbol a] -- | A symbol is either a terminal symbol (from a user-specified type) or a -- non-terminal symbol. data Symbol a NonTerminal :: !NonTerminalSymbol -> Symbol a Terminal :: a -> Symbol a -- | Non-terminal symbols are represented by Int. -- -- The number 0 is reserved for the start symbol of the grammar. type NonTerminalSymbol = Int -- | IsTerminalSymbol is a class synonym for absorbing the -- difference between hashable <1.4.0.0 and -- >=1.4.0.0. -- -- hashable-1.4.0.0 makes Eq be a superclass of -- Hashable. Therefore we define -- -- 
--   type IsTerminalSymbol a = Hashable a
--
-- -- on hashable >=1.4.0.0, while we define -- -- 
--   type IsTerminalSymbol a = (Eq a, Hashable a)
--
-- -- on hashable <1.4.0.0. -- -- Also, developers can temporarily add other classes (e.g. Show) -- to ease debugging. type IsTerminalSymbol a = Hashable a -- | Construct a grammar from a given sequence of symbols using -- SEQUITUR. -- -- fromList and fromString can also be used. encode :: IsTerminalSymbol a => [a] -> Grammar a -- | Builder denotes an internal state of the SEQUITUR -- algorithm. data Builder s a -- | Create a new Builder. 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 the SEQUITUR algorithm. add :: (PrimMonad m, IsTerminalSymbol a) => Builder (PrimState m) a -> a -> m () -- | Retrieve a grammar (as a persistent data structure) from the -- Builder's internal state. build :: PrimMonad m => Builder (PrimState m) a -> m (Grammar a) -- | Reconstruct an input sequence from a grammar. -- -- It is lazy in the sense that you can consume from the beginning before -- constructing the entire sequence. This function is suitable if you -- just need to access the resulting sequence only once and from -- beginning to end. If you need to use the resulting sequence in a more -- complex way, decodeToSeq would be more suitable. -- -- This is a left-inverse of encode, and is equivalent to -- toList of Foldable class and toList of -- IsList. decode :: HasCallStack => Grammar a -> [a] -- | A variant of decode in which the result type is Seq. decodeToSeq :: HasCallStack => Grammar a -> Seq a -- | Monoid-based folding over the decoded sequence. -- -- This function is equivalent to the following definition but is more -- efficient due to the utilization of sharing. -- -- 
--   decodeToMonoid f = mconcat . map f . decode
--
-- -- This is equivalent to foldMap of Foldable class. decodeToMonoid :: (Monoid m, HasCallStack) => (a -> m) -> Grammar a -> m -- | Monoid-based folding over the decoded sequence of each -- non-terminal symbol. -- -- For example, in the following grammar -- -- 
--   g = Grammar (IntMap.fromList
--     [ (0, [NonTerminal 1, Terminal 'c', NonTerminal 1])
--     , (1, [Terminal 'a', Terminal 'b'])
--     ])
--
-- -- non-terminal symbol 0 and 1 produces -- "abcab" and "ab" respectively. Therefore, -- decodeNonTerminalsToMonoid f yields -- -- 
--   IntMap.fromList
--     [ (0, mconcat (map f "abcab"))
--     , (1, mconcat (map f "ab"))
--     ]
--
decodeNonTerminalsToMonoid :: (Monoid m, HasCallStack) => (a -> m) -> Grammar a -> IntMap m 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.Show.Show a => GHC.Show.Show (Language.Grammar.Sequitur.Grammar a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Language.Grammar.Sequitur.Grammar 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 Language.Grammar.Sequitur.IsTerminalSymbol a => GHC.IsList.IsList (Language.Grammar.Sequitur.Grammar a) instance GHC.Base.Functor Language.Grammar.Sequitur.Grammar instance Data.Foldable.Foldable Language.Grammar.Sequitur.Grammar instance Data.String.IsString (Language.Grammar.Sequitur.Grammar GHC.Types.Char) instance Data.Hashable.Class.Hashable a => Data.Hashable.Class.Hashable (Language.Grammar.Sequitur.Symbol a) instance GHC.Base.Functor Language.Grammar.Sequitur.Symbol