-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Compressed containers and reducers -- -- Compressed containers and reducers @package compressed @version 0.3 -- | Compression algorithms are all about exploiting redundancy. When -- applying an expensive Reducer to a redundant source, it may be -- better to extract the structural redundancy that is present. Run -- length encoding can do so for long runs of identical inputs. module Data.Compressed.RunLengthEncoding -- | A Generator which supports efficient mapReduce -- operations over run-length encoded data. newtype RLE a RLE :: FingerTree Count (Run a) -> RLE a getRLE :: RLE a -> FingerTree Count (Run a) -- | A single run with a strict length data Run a runLength :: Run a -> Int decode :: RLE a -> [a] encode :: (Generator c, Eq (Elem c)) => c -> RLE (Elem c) recode :: Eq a => RLE a -> RLE a toRuns :: RLE a -> [Run a] fromRuns :: [Run a] -> RLE a instance Eq a => Eq (Run a) instance Show a => Show (Run a) instance Adjustable RLE instance Lookup RLE instance Zip RLE instance Eq a => Eq (RLE a) instance Hashable a => Hashable (RLE a) instance Generator (RLE a) instance Foldable RLE instance Eq a => Monoid (RLE a) instance Eq a => Reducer a (RLE a) instance Monad RLE instance Bind RLE instance Applicative RLE instance Apply RLE instance Pointed RLE instance Functor RLE instance Eq a => Semigroup (RLE a) instance Measured Count (Run a) instance Foldable1 Run instance Foldable Run instance Monad Run instance Bind Run instance Applicative Run instance Apply Run instance Pointed Run instance Functor Run instance Comonad Run instance Extend Run instance Ord a => Ord (Run a) -- | Compression algorithms are all about exploiting redundancy. When -- applying an expensive Reducer to a redundant source, it may be -- better to extract the structural redundancy that is present. -- LZ78 is a compression algorithm that does so, without requiring -- the dictionary to be populated with all of the possible values of a -- data type unlike its later refinement LZW, and which has fewer -- comparison reqirements during encoding than its earlier counterpart -- LZ77. module Data.Compressed.Internal.LZ78 data Token a Token :: {-# UNPACK #-} !Int -> a -> Token a -- | An LZ78 compressed Generator. data LZ78 a Cons :: {-# UNPACK #-} !Token a -> (LZ78 a) -> LZ78 a Nil :: LZ78 a -- | O(n) Construct an LZ78-compressed Generator using a -- HashMap internally. encode :: (Hashable a, Eq a) => [a] -> LZ78 a -- | O(n log n) Contruct an LZ78-compressed Generator using a -- Map internally. encodeOrd :: Ord a => [a] -> LZ78 a -- | O(n^2) Contruct an LZ78-compressed Generator using a -- list internally, requires an instance of Eq, less efficient than -- encode. encodeEq :: Eq a => [a] -> LZ78 a -- | A type-constrained reduce operation decode :: LZ78 a -> [a] -- | O(n). Recompress with Hashable recode :: (Eq a, Hashable a) => LZ78 a -> LZ78 a -- | O(n log n). Recompress with Ord recodeOrd :: Ord a => LZ78 a -> LZ78 a -- | O(n^2). Recompress with Eq recodeEq :: Eq a => LZ78 a -> LZ78 a data Entry i a Entry :: !i -> a -> Entry i a -- | exposes internal structure entries :: LZ78 a -> LZ78 (Entry Int a) instance Eq a => Eq (Token a) instance Ord a => Ord (Token a) instance (Show i, Show a) => Show (Entry i a) instance (Read i, Read a) => Read (Entry i a) instance Zip LZ78 instance FoldableWithKey LZ78 instance Indexable LZ78 instance Lookup LZ78 instance Adjustable LZ78 instance Monad LZ78 instance Applicative LZ78 instance Hashable i => Hashable (Entry i a) instance Ord i => Ord (Entry i a) instance Eq i => Eq (Entry i a) instance Comonad (Entry i) instance Extend (Entry i) instance Functor (Entry i) instance Foldable LZ78 instance Pointed LZ78 instance Functor LZ78 instance Generator (LZ78 a) instance (Read a, Hashable a, Eq a) => Read (LZ78 a) instance Ord a => Ord (LZ78 a) instance Eq a => Eq (LZ78 a) instance Show a => Show (LZ78 a) instance Hashable a => Hashable (Token a) instance Comonad Token instance Extend Token instance Traversable Token instance Foldable Token instance Functor Token -- | Compression algorithms are all about exploiting redundancy. When -- applying an expensive Reducer to a redundant source, it may -- be better to extract the structural redundancy that is present. -- LZ78 is a compression algorithm that does so, without requiring -- the dictionary to be populated with all of the possible values of a -- data type unlike its later refinement LZW, and which has fewer -- comparison reqirements during encoding than its earlier counterpart -- LZ77. module Data.Compressed.LZ78 -- | An LZ78 compressed Generator. data LZ78 a -- | O(n) Construct an LZ78-compressed Generator using a -- HashMap internally. encode :: (Hashable a, Eq a) => [a] -> LZ78 a -- | O(n log n) Contruct an LZ78-compressed Generator using a -- Map internally. encodeOrd :: Ord a => [a] -> LZ78 a -- | O(n^2) Contruct an LZ78-compressed Generator using a -- list internally, requires an instance of Eq, less efficient than -- encode. encodeEq :: Eq a => [a] -> LZ78 a -- | A type-constrained reduce operation decode :: LZ78 a -> [a] -- | O(n). Recompress with Hashable recode :: (Eq a, Hashable a) => LZ78 a -> LZ78 a -- | O(n log n). Recompress with Ord recodeOrd :: Ord a => LZ78 a -> LZ78 a -- | O(n^2). Recompress with Eq recodeEq :: Eq a => LZ78 a -> LZ78 a