[auto ekmett@gmail.com**20090329084031] { hunk ./doc/html/monoids/Data-Group-Combinators.html 22 ->monoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsnewtypedata a = LZ78 {
getLZ78 :: [(Int, a)]
} anewtypedataAn LZ78 compressing Generator, which supports efficient mapReduce operations -Constructors
LZ78
getLZ78 :: [(Int, a)]
Functor LZ78monoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of MonoidsA single run with a strict length +>A single run with a strict length. hunk ./doc/html/monoids/Data-Monoid-Generator.html 22 ->monoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoids (Index)monoids-0.1.11: Lots of Monoids (Index)monoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of MonoidsgetLZ78Data.Monoid.Generator.LZ781 (Type/Class)2 (Data Constructor)Data.Monoid.Generator.LZ78monoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoidsmonoids-0.1.10: Lots of Monoidsmonoids-0.1.11: Lots of Monoids , LZ78(LZ78, getLZ78) + , LZ78 hunk ./doc/html/monoids/src/Data-Monoid-Generator-LZ78.html 52 -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 +data Token a = Token a {-# UNPACK #-} !Int + deriving (Eq,Ord,Show,Read) + +-- after using the Functor instance the encoding may no longer be minimal +instance Functor Token where + fmap f (Token a n) = Token (f a) n + +newtype LZ78 a = LZ78 { getLZ78 :: [Token a] } hunk ./doc/html/monoids/src/Data-Monoid-Generator-LZ78.html 61 -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 +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 + +instance Functor LZ78 where + fmap f = LZ78 . fmap (fmap f) . getLZ78 + +mapTo' :: (e `Reducer` m) => (a -> e) -> m -> Seq m -> [Token a] -> m +mapTo' _ m _ [] = m +mapTo' f m s (Token c w:ws) = mapTo' f (m `mappend` v) (s |> v) ws + where + v = Seq.index s w `mappend` unit (f c) hunk ./doc/html/monoids/src/Data-Monoid-Generator-LZ78.html 77 -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' _ _ _ [] = [] +-- | 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. hunk ./doc/html/monoids/src/Data-Monoid-Generator-LZ78.html 84 --- | 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' _ _ _ [] = [] +encode :: Ord a => [a] -> LZ78 a +encode = LZ78 . encode' Map.empty 1 0 + +encode' :: Ord a => Map (Token a) Int -> Int -> Int -> [a] -> [Token a] +encode' _ _ p [c] = [Token c p] +encode' d f p (c:cs) = let t = Token c p in case Map.lookup t d of + Just p' -> encode' d f p' cs + Nothing -> t : encode' (Map.insert t f d) (succ f) 0 cs +encode' _ _ _ [] = [] + +-- | contruct an LZ78-compressed 'Generator' using a list internally, requires an instance of Eq. hunk ./doc/html/monoids/src/Data-Monoid-Generator-LZ78.html 96 --- | 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 +encodeEq :: Eq a => [a] -> LZ78 a +encodeEq = LZ78 . encodeEq' [] 1 0 + +encodeEq' :: Eq a => [(Token a,Int)] -> Int -> Int -> [a] -> [Token a] +encodeEq' _ _ p [c] = [Token c p] +encodeEq' d f p (c:cs) = let t = Token c p in case List.lookup t d of + Just p' -> encodeEq' d f p' cs + Nothing -> t : encodeEq' ((t,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 44 --- | A single run with a strict length +-- | A single run with a strict length. }