compressed-3.10: Compressed containers and reducers

Portabilitynon-portable (type families)
Safe HaskellTrustworthy




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.


Lempel-Ziv 78

data Token a Source


Token !Int a 

data LZ78 a Source

An LZ78 compressed Generator.


Cons !(Token a) (LZ78 a) 


encode :: (Hashable a, Eq a) => [a] -> LZ78 aSource

O(n) Construct an LZ78-compressed Generator using a HashMap internally.

encodeOrd :: Ord a => [a] -> LZ78 aSource

O(n log n) Contruct an LZ78-compressed Generator using a Map internally.

encodeEq :: Eq a => [a] -> LZ78 aSource

O(n^2) Contruct an LZ78-compressed Generator using a list internally, requires an instance of Eq, less efficient than encode.

Decoding (reduce)

decode :: LZ78 a -> [a]Source

A type-constrained reduce operation


recode :: (Eq a, Hashable a) => LZ78 a -> LZ78 aSource

O(n). Recompress with Hashable

recodeOrd :: Ord a => LZ78 a -> LZ78 aSource

O(n log n). Recompress with Ord

recodeEq :: Eq a => LZ78 a -> LZ78 aSource

O(n^2). Recompress with Eq

Unsafe (exposes internal structure)

data Entry i a Source


Entry !i a 


Functor (Entry i) 
Comonad (Entry i) 
Extend (Entry i) 
Eq i => Eq (Entry i a) 
Ord i => Ord (Entry i a) 
(Read i, Read a) => Read (Entry i a) 
(Show i, Show a) => Show (Entry i a) 
Hashable i => Hashable (Entry i a) 

entries :: LZ78 a -> LZ78 (Entry Int a)Source

exposes internal structure