-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Compressed containers and reducers -- -- Compressed containers and reducers. @package compressed @version 3.11 -- | 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 (GHC.Read.Read a, GHC.Read.Read i) => GHC.Read.Read (Data.Compressed.Internal.LZ78.Entry i a) instance (GHC.Show.Show a, GHC.Show.Show i) => GHC.Show.Show (Data.Compressed.Internal.LZ78.Entry i a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Compressed.Internal.LZ78.Token a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Compressed.Internal.LZ78.Token a) instance GHC.Base.Functor (Data.Compressed.Internal.LZ78.Entry i) instance Data.Functor.Extend.Extend (Data.Compressed.Internal.LZ78.Entry i) instance Control.Comonad.Comonad (Data.Compressed.Internal.LZ78.Entry i) instance GHC.Classes.Eq i => GHC.Classes.Eq (Data.Compressed.Internal.LZ78.Entry i a) instance GHC.Classes.Ord i => GHC.Classes.Ord (Data.Compressed.Internal.LZ78.Entry i a) instance Data.Hashable.Class.Hashable i => Data.Hashable.Class.Hashable (Data.Compressed.Internal.LZ78.Entry i a) instance GHC.Base.Applicative Data.Compressed.Internal.LZ78.LZ78 instance GHC.Base.Monad Data.Compressed.Internal.LZ78.LZ78 instance Data.Key.Adjustable Data.Compressed.Internal.LZ78.LZ78 instance Data.Key.Zip Data.Compressed.Internal.LZ78.LZ78 instance GHC.Show.Show a => GHC.Show.Show (Data.Compressed.Internal.LZ78.LZ78 a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Compressed.Internal.LZ78.LZ78 a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Compressed.Internal.LZ78.LZ78 a) instance (GHC.Read.Read a, Data.Hashable.Class.Hashable a, GHC.Classes.Eq a) => GHC.Read.Read (Data.Compressed.Internal.LZ78.LZ78 a) instance Data.Generator.Generator (Data.Compressed.Internal.LZ78.LZ78 a) instance GHC.Base.Functor Data.Compressed.Internal.LZ78.LZ78 instance Data.Pointed.Pointed Data.Compressed.Internal.LZ78.LZ78 instance Data.Foldable.Foldable Data.Compressed.Internal.LZ78.LZ78 instance Control.Monad.Zip.MonadZip Data.Compressed.Internal.LZ78.LZ78 instance Data.Key.Lookup Data.Compressed.Internal.LZ78.LZ78 instance Data.Key.Indexable Data.Compressed.Internal.LZ78.LZ78 instance Data.Key.FoldableWithKey Data.Compressed.Internal.LZ78.LZ78 instance GHC.Base.Functor Data.Compressed.Internal.LZ78.Token instance Data.Foldable.Foldable Data.Compressed.Internal.LZ78.Token instance Data.Traversable.Traversable Data.Compressed.Internal.LZ78.Token instance Data.Functor.Extend.Extend Data.Compressed.Internal.LZ78.Token instance Control.Comonad.Comonad Data.Compressed.Internal.LZ78.Token instance Data.Hashable.Class.Hashable a => Data.Hashable.Class.Hashable (Data.Compressed.Internal.LZ78.Token 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.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 -- | 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) encodeList :: Eq a => [a] -> RLE a recode :: Eq a => RLE a -> RLE a toRuns :: RLE a -> [Run a] fromRuns :: [Run a] -> RLE a instance GHC.Show.Show a => GHC.Show.Show (Data.Compressed.RunLengthEncoding.Run a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Compressed.RunLengthEncoding.Run a) instance GHC.Classes.Eq a => Data.Semigroup.Semigroup (Data.Compressed.RunLengthEncoding.RLE a) instance GHC.Base.Functor Data.Compressed.RunLengthEncoding.RLE instance Data.Pointed.Pointed Data.Compressed.RunLengthEncoding.RLE instance Data.Functor.Bind.Class.Apply Data.Compressed.RunLengthEncoding.RLE instance GHC.Base.Applicative Data.Compressed.RunLengthEncoding.RLE instance Data.Functor.Bind.Class.Bind Data.Compressed.RunLengthEncoding.RLE instance GHC.Base.Monad Data.Compressed.RunLengthEncoding.RLE instance Control.Monad.Zip.MonadZip Data.Compressed.RunLengthEncoding.RLE instance GHC.Classes.Eq a => Data.Semigroup.Reducer.Reducer a (Data.Compressed.RunLengthEncoding.RLE a) instance GHC.Classes.Eq a => GHC.Base.Monoid (Data.Compressed.RunLengthEncoding.RLE a) instance Data.Foldable.Foldable Data.Compressed.RunLengthEncoding.RLE instance Data.Generator.Generator (Data.Compressed.RunLengthEncoding.RLE a) instance Data.Hashable.Class.Hashable a => Data.Hashable.Class.Hashable (Data.Compressed.RunLengthEncoding.RLE a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Compressed.RunLengthEncoding.RLE a) instance Data.Key.Zip Data.Compressed.RunLengthEncoding.RLE instance Data.Key.Lookup Data.Compressed.RunLengthEncoding.RLE instance Data.Key.Adjustable Data.Compressed.RunLengthEncoding.RLE instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Compressed.RunLengthEncoding.Run a) instance Data.Functor.Extend.Extend Data.Compressed.RunLengthEncoding.Run instance Control.Comonad.Comonad Data.Compressed.RunLengthEncoding.Run instance GHC.Base.Functor Data.Compressed.RunLengthEncoding.Run instance Data.Pointed.Pointed Data.Compressed.RunLengthEncoding.Run instance Data.Functor.Bind.Class.Apply Data.Compressed.RunLengthEncoding.Run instance Control.Comonad.ComonadApply Data.Compressed.RunLengthEncoding.Run instance GHC.Base.Applicative Data.Compressed.RunLengthEncoding.Run instance Data.Functor.Bind.Class.Bind Data.Compressed.RunLengthEncoding.Run instance GHC.Base.Monad Data.Compressed.RunLengthEncoding.Run instance Data.Foldable.Foldable Data.Compressed.RunLengthEncoding.Run instance Data.Semigroup.Foldable.Class.Foldable1 Data.Compressed.RunLengthEncoding.Run instance Data.FingerTree.Measured Data.Semigroup.Reducer.Count (Data.Compressed.RunLengthEncoding.Run a)