[auto ekmett@gmail.com**20090329071655] { addfile ./doc/html/monoids/Data-Monoid-Generator-RLE.html addfile ./doc/html/monoids/src/Data-Monoid-Generator-RLE.html hunk ./doc/html/monoids/Data-Monoid-Generator-LZ78.html 47 +>
Portabilityportable
Stabilityexperimental
Maintainerlibraries@haskell.org
DescriptionCompression 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. Since we aren't storing these as a + bitstream the LZSS refinement of only encoding pointers once you cross + the break-even point is a net loss. +Synopsis
module Data.Monoid.Generator
newtype LZ78 a = LZ78 {
getLZ78 :: [(Int, a)]
}
decode :: LZ78 a -> [a]
encode :: Ord a => [a] -> LZ78 a
encodeEq :: Eq a => [a] -> LZ78 a
prop_decode_encode :: Ord a => [a] -> Bool
prop_decode_encodeEq :: Eq a => [a] -> Bool
An LZ78 compressing Generator, which supports efficient mapReduce operations +a type-constrained reduce operation +contruct an LZ78-compressed Generator using a Map internally, requires an instance of Ord. +contruct an LZ78-compressed Generator using a list internally, requires an instance of Eq. +QuickCheck property: decode . encode = id +QuickCheck property: decode . encodeEq = id + + +Data.Monoid.Generator.RLE
monoids-0.1.8: Lots of MonoidsSource codeContentsIndex
Data.Monoid.Generator.RLE
Portabilityportable
Stabilityexperimental
Maintainerlibraries@haskell.org
Description
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. +
Synopsis
module Data.Monoid.Generator
newtype RLE f a = RLE {
getRLE :: f (Run a)
}
decode :: Foldable f => RLE f a -> [a]
encode :: (Generator c, Eq (Elem c)) => c -> RLE Seq (Elem c)
encodeEq :: Eq a => [a] -> RLE [] a
prop_decode_encode :: (Generator c, Eq (Elem c)) => c -> Bool
prop_decode_encodeEq :: Eq a => [a] -> Bool
Documentation
module Data.Monoid.Generator
newtype RLE f a Source
A Generator which supports efficient mapReduce operations over run-length encoded data. +
Constructors
RLE
getRLE :: f (Run a)
show/hide Instances
Eq a => Reducer a (RLE Seq a)
Functor f => Functor (RLE f)
Eq a => Monoid (RLE Seq a)
Foldable f => Generator (RLE f a)
decode :: Foldable f => RLE f a -> [a]Source
encode :: (Generator c, Eq (Elem c)) => c -> RLE Seq (Elem c)Source
encodeEq :: Eq a => [a] -> RLE [] aSource
naive left to right encoder +
prop_decode_encode :: (Generator c, Eq (Elem c)) => c -> BoolSource
prop_decode_encodeEq :: Eq a => [a] -> BoolSource
QuickCheck property: decode . encode = id +
Produced by Haddock version 2.3.0
hunk ./doc/html/monoids/Data-Monoid-Generator.html 707 +>Foldable f => Generator (RLE f a)Eq a => Reducer a (RLE Seq a)(Integral n, Reducer c m) => Reducer ((,) n c) (RLE n m)(Integral n, Reducer c m) => Reducer ((,) n c) (RLE n m)Data.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiation, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Union, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Union, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE1 (Function)2 (Function)Data.Monoid.Generator.RLEData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiation, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLE1 (Function)2 (Function)Data.Monoid.Generator.RLE1 (Function)2 (Function)Data.Monoid.Generator.RLEData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiation, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLEData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiation, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLEData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiation, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLEData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Lexical.RunLengthEncodingData.Monoid.Generator.RLEData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiation, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLEData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiation, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLEData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Union, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Monoid.Ord, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Union, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Monoid.Ord, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiation, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLEData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Union, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Monoid.Ord, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Union, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Monoid.Ord, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Union, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Monoid.Ord, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Union, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Monoid.Ord, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiation1 (Function)2 (Function)Data.Monoid.Generator.RLE1 (Function)2 (Function)Data.Monoid.Generator.RLE, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Union, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Ord, Data.Ring.Semi.Tropical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Union, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Ord, Data.Ring.Semi.Tropical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLEData.Monoid.Lexical.RunLengthEncodingData.Monoid.Generator.RLEData.Monoid.Lexical.RunLengthEncodingData.Monoid.Generator.RLE, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Union, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Union, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLEData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Ring.Module.AutomaticDifferentiationData.Monoid.Reducer, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Additive, Data.Monoid.Additive.Sugar, Data.Monoid.Multiplicative, Data.Monoid.Multiplicative.Sugar, Data.Ring.Semi.Near, Data.Ring.Semi, Data.Ring.Semi.Tropical, Data.Ring.Semi.Ord, Data.Ring.Sugar, Data.Group, Data.Group.Combinators, Data.Group.Sugar, Data.Ring, Data.Ring.Boolean, Data.Ring.FromNum, Data.Ring.Module, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Ring.Module.AutomaticDifferentiation, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Union, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Ord, Data.Ring.Semi.Tropical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Lexical.RunLengthEncoding, Data.Monoid.Reducer.Char, Data.Monoid.Reducer.With, Data.Monoid.Union, Data.Monoid.Lexical.UTF8.Decoder, Data.Monoid.Generator, Data.Monoid.Lexical.SourcePosition, Data.Monoid.Lexical.Words, Data.Monoid.Self, Data.Monoid.Generator.LZ78, Data.Monoid.FromString, Data.Monoid.Categorical, Data.Monoid.Ord, Data.Ring.Semi.Tropical, Data.Monoid.Applicative, Data.Monoid.Monad, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLE, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.LZ78, Data.Monoid.Combinators, Data.Monoid.Generator.RLEData.Monoid.Generator.RLEData.Monoid.Lexical.RunLengthEncodingmodule Data.Monoid.Generator.LZ78 - ( module Data.Monoid.Generator - , LZ78(LZ78, getLZ78) - , decode - , encode - , encodeEq - , prop_decode_encode - , prop_decode_encodeEq - ) where - -import qualified Data.Sequence as Seq -import Data.Sequence (Seq,(|>)) -import qualified Data.Map as Map -import Data.Map (Map) -import qualified Data.List as List -import Data.Monoid.Generator -import Data.Monoid.Self - -newtype LZ78 a = LZ78 { getLZ78 :: [(Int,a)] } - -emptyDict :: Monoid m => Seq m -emptyDict = Seq.singleton mempty - -instance Generator (LZ78 a) where - type Elem (LZ78 a) = a - mapTo f m (LZ78 xs) = mapTo' f m emptyDict xs - -mapTo' :: (e `Reducer` m) => (a -> e) -> m -> Seq m -> [(Int,a)] -> m -mapTo' _ m _ [] = m -mapTo' f m s ((w,c):ws) = mapTo' f (m `mappend` v) (s |> v) ws - where - v = Seq.index s w `mappend` unit (f c) - -decode :: LZ78 a -> [a] -decode = reduce - -encode :: Ord a => [a] -> LZ78 a -encode = LZ78 . encode' Map.empty 1 0 - -encode' :: Ord a => Map (Int,a) Int -> Int -> Int -> [a] -> [(Int,a)] -encode' _ _ p [c] = [(p,c)] -encode' d f p (c:cs) = case Map.lookup (p,c) d of - Just p' -> encode' d f p' cs - Nothing -> (p,c):encode' (Map.insert (p,c) f d) (succ f) 0 cs -encode' _ _ _ [] = [] - -encodeEq :: Eq a => [a] -> LZ78 a -encodeEq = LZ78 . encodeEq' [] 1 0 - -encodeEq' :: Eq a => [((Int,a),Int)] -> Int -> Int -> [a] -> [(Int,a)] -encodeEq' _ _ p [c] = [(p,c)] -encodeEq' d f p (c:cs) = case List.lookup (p,c) d of - Just p' -> encodeEq' d f p' cs - Nothing -> (p,c):encodeEq' (((p,c),f):d) (succ f) 0 cs -encodeEq' _ _ _ [] = [] - --- QuickCheck properties, this holds as long as Ord is structural -prop_decode_encode :: Ord a => [a] -> Bool -prop_decode_encode xs = decode (encode xs) == xs - --- QuickCheck properties, this holds as long as Eq is structural -prop_decode_encodeEq :: Eq a => [a] -> Bool -prop_decode_encodeEq xs = decode (encodeEq xs) == xs + +----------------------------------------------------------------------------- +-- | +-- Module : Data.Monoid.Generator.LZ78 +-- Copyright : (c) Edward Kmett 2009 +-- License : BSD-style +-- Maintainer : libraries@haskell.org +-- Stability : experimental +-- Portability : portable +-- +-- 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. Since we aren't storing these as a +-- bitstream the LZSS refinement of only encoding pointers once you cross +-- the break-even point is a net loss. +----------------------------------------------------------------------------- + + +module Data.Monoid.Generator.LZ78 + ( module Data.Monoid.Generator + , LZ78(LZ78, getLZ78) + , decode + , encode + , encodeEq + , prop_decode_encode + , prop_decode_encodeEq + ) where + +import qualified Data.Sequence as Seq +import Data.Sequence (Seq,(|>)) +import qualified Data.Map as Map +import Data.Map (Map) +import qualified Data.List as List +import Data.Monoid.Generator +import Data.Monoid.Self + +-- | An LZ78 compressing 'Generator', which supports efficient 'mapReduce' operations + +newtype LZ78 a = LZ78 { getLZ78 :: [(Int,a)] } + +emptyDict :: Monoid m => Seq m +emptyDict = Seq.singleton mempty + +instance Generator (LZ78 a) where + type Elem (LZ78 a) = a + mapTo f m (LZ78 xs) = mapTo' f m emptyDict xs + +mapTo' :: (e `Reducer` m) => (a -> e) -> m -> Seq m -> [(Int,a)] -> m +mapTo' _ m _ [] = m +mapTo' f m s ((w,c):ws) = mapTo' f (m `mappend` v) (s |> v) ws + where + v = Seq.index s w `mappend` unit (f c) + +-- | a type-constrained 'reduce' operation + +decode :: LZ78 a -> [a] +decode = reduce + +-- | contruct an LZ78-compressed 'Generator' using a 'Map' internally, requires an instance of Ord. + +encode :: Ord a => [a] -> LZ78 a +encode = LZ78 . encode' Map.empty 1 0 + +encode' :: Ord a => Map (Int,a) Int -> Int -> Int -> [a] -> [(Int,a)] +encode' _ _ p [c] = [(p,c)] +encode' d f p (c:cs) = case Map.lookup (p,c) d of + Just p' -> encode' d f p' cs + Nothing -> (p,c):encode' (Map.insert (p,c) f d) (succ f) 0 cs +encode' _ _ _ [] = [] + +-- | contruct an LZ78-compressed 'Generator' using a list internally, requires an instance of Eq. + +encodeEq :: Eq a => [a] -> LZ78 a +encodeEq = LZ78 . encodeEq' [] 1 0 + +encodeEq' :: Eq a => [((Int,a),Int)] -> Int -> Int -> [a] -> [(Int,a)] +encodeEq' _ _ p [c] = [(p,c)] +encodeEq' d f p (c:cs) = case List.lookup (p,c) d of + Just p' -> encodeEq' d f p' cs + Nothing -> (p,c):encodeEq' (((p,c),f):d) (succ f) 0 cs +encodeEq' _ _ _ [] = [] + +-- | QuickCheck property: decode . encode = id +prop_decode_encode :: Ord a => [a] -> Bool +prop_decode_encode xs = decode (encode xs) == xs + +-- | QuickCheck property: decode . encodeEq = id +prop_decode_encodeEq :: Eq a => [a] -> Bool +prop_decode_encodeEq xs = decode (encodeEq xs) == xs hunk ./doc/html/monoids/src/Data-Monoid-Generator-RLE.html 1 + + + + +Data/Monoid/Generator/RLE.hs + + + +
{-# LANGUAGE TypeFamilies, MultiParamTypeClasses, TypeOperators, FlexibleInstances, FlexibleContexts #-}
+
+-----------------------------------------------------------------------------
+-- |
+-- Module      :  Data.Monoid.Generator.RLE
+-- Copyright   :  (c) Edward Kmett 2009
+-- License     :  BSD-style
+-- Maintainer  :  libraries@haskell.org
+-- Stability   :  experimental
+-- Portability :  portable
+--
+-- 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.Monoid.Generator.RLE
+    ( module Data.Monoid.Generator
+    , RLE(RLE, getRLE)
+    , decode
+    , encode
+    , encodeEq
+    , prop_decode_encode
+    , prop_decode_encodeEq
+    ) where
+
+import qualified Data.Sequence as Seq
+import Data.Sequence (Seq,(|>),(<|),ViewL(..),ViewR(..),(><),viewl,viewr)
+import Data.Foldable
+import Data.Monoid.Generator
+import qualified Data.Monoid.Combinators as Monoid 
+import Control.Functor.Pointed
+
+-- | A single run with a strict length
+data Run a = Run a {-# UNPACK #-} !Int
+
+instance Functor Run where
+    fmap f (Run a n) = Run (f a) n
+
+instance Pointed Run where
+    point a = Run a 1
+
+-- | A 'Generator' which supports efficient 'mapReduce' operations over run-length encoded data.
+newtype RLE f a = RLE { getRLE :: f (Run a) } 
+
+instance Functor f => Functor (RLE f) where
+    fmap f = RLE . fmap (fmap f) . getRLE
+
+instance Foldable f => Generator (RLE f a) where
+    type Elem (RLE f a) = a
+    mapReduce f = foldMap run . getRLE where
+        run (Run a n) = unit (f a) `Monoid.replicate` n
+
+decode :: Foldable f => RLE f a -> [a]
+decode = reduce
+
+-- | naive left to right encoder
+
+encodeEq :: Eq a => [a] -> RLE [] a
+encodeEq [] = RLE []
+encodeEq (a:as) = RLE (point a `before` as)
+
+before :: Eq a => Run a -> [a] -> [Run a]
+r           `before` []                 = [r]
+r@(Run a n) `before` (b:bs) | a == b    = Run a (n+1) `before` bs
+                            | otherwise = r : point b `before` bs
+
+-- | QuickCheck property: decode . encode = id
+prop_decode_encodeEq :: Eq a => [a] -> Bool
+prop_decode_encodeEq xs = decode (encode xs) == xs
+
+-- One nice property that run-length encoding has is that it can be computed monoidally as follows
+
+instance Eq a => Monoid (RLE Seq a) where
+    mempty = RLE Seq.empty
+    RLE l `mappend` RLE r = viewr l `merge` viewl r where
+        (l' :> Run a m) `merge` (Run b n :< r')
+            | a == b     = RLE ((l' |> Run a (m+n)) >< r')
+            | otherwise  = RLE (l >< r)
+        EmptyR `merge` _ = RLE r
+        _ `merge` EmptyL = RLE l
+
+instance Eq a => Reducer a (RLE Seq a) where
+    unit = RLE . Seq.singleton . point
+    cons a (RLE r) = case viewl r of
+            Run b n :< r' | a == b    -> RLE (Run a (n+1) <| r')
+                          | otherwise -> RLE (Run a 1     <| r )
+            EmptyL                    -> RLE (return (point a))
+    snoc (RLE l) a = case viewr l of
+            l' :> Run b n | a == b    -> RLE (l' |> Run b (n+1))
+                          | otherwise -> RLE (l  |> Run a 1    )
+            EmptyR                    -> RLE (return (point a))
+
+encode :: (Generator c, Eq (Elem c)) => c -> RLE Seq (Elem c)
+encode = reduce
+
+prop_decode_encode :: (Generator c, Eq (Elem c)) => c -> Bool
+prop_decode_encode xs = decode (encode xs) == reduce xs
+
+ }