Source

Data.Sequitur / src / Data / Sequitur.hs

module Data.Sequitur ( init
                     , compress
                     , expand
                     , feed
                     , rule
                     , ruleCount
                     , Symbol (Literal, Rule)
                     , Compressor (Compressor)
                     ) where

import Prelude hiding (init)
import qualified Data.Map as M
import qualified Data.Sequence as S

-- Operations:
--  * appending a symbol to rule S;
--  * using an existing rule (substituting a non-terminal symbol for two symbols);
--  * creating a new rule (creating a new non-terminal symbol and inserting two new symbols on the right-hand side); and
--  * deleting a rule (removing rule and inserting its definition into another rule).


-- | This is a Symbol in a rule.
data Symbol a =
      Literal a         -- A literal input symbol.
    | Rule Integer      -- A rule.
    deriving (Show, Eq)

-- | This is a rule's body
type RuleBody a = S.Seq (Symbol a)

-- | This is the compressor data types.
data Compressor a = Compressor {
      rules     :: M.Map Integer (RuleBody a)       -- The list of rules defined.
    , ruleCount :: Integer                      -- The number of rules defined.
    }

-- | This serializes a 

-- | This returns the rule of a given number.
rule :: Eq a => Compressor a -> Integer -> RuleBody a
rule compressor key =
    M.findWithDefault S.empty key $ rules compressor

-- | This returns a new, empty compressor.
init :: Compressor a
init = Compressor M.empty 0

-- | This compresses an input sequence and returns the Compressor.
compress :: Eq a => [a] -> Compressor a
compress = foldl feed init

-- | This takes a compressor and returns the input that generated it.
expand :: Eq a => Compressor a -> [a]
expand _ = []

-- | This feeds an input literal to a compressor and returns a new compressor
-- that includes it.
feed :: Eq a => Compressor a -> a -> Compressor a
feed compressor _ = compressor

-- | This appends a symbol to a rule.
append :: Eq a => Compressor a -> Integer -> a -> Compressor a
append compressor _ _ = compressor

-- | This uses an existing rule.
use :: Compressor a -> Integer -> Compressor a
use compressor _ = compressor

-- | This creates a new rule.
create :: Compressor a -> (Integer, Compressor a)
create compressor = (0, compressor)

-- | This deletes a rule.
delete :: Compressor a -> Integer -> Compressor a
delete compressor _ = compressor