Copyright	(c) Edward Kmett 2009-2012
License	BSD-style
Maintainer	ekmett@gmail.com
Stability	experimental
Portability	portable
Safe Haskell	Trustworthy
Language	Haskell98

Data.Compressed.RunLengthEncoding

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

newtype RLE a = RLE {
- getRLE :: FingerTree Count (Run a)
}
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

Documentation

newtype RLE a #

A Generator which supports efficient mapReduce operations over run-length encoded data.

Constructors

RLE
Fields getRLE :: FingerTree Count (Run a)

Instances

Monad RLE #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods (>>=) :: RLE a -> (a -> RLE b) -> RLE b # (>>) :: RLE a -> RLE b -> RLE b # return :: a -> RLE a # fail :: String -> RLE a #
Functor RLE #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods fmap :: (a -> b) -> RLE a -> RLE b # (<$) :: a -> RLE b -> RLE a #
Applicative RLE #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods pure :: a -> RLE a # (<>) :: RLE (a -> b) -> RLE a -> RLE b # liftA2 :: (a -> b -> c) -> RLE a -> RLE b -> RLE c # (>) :: RLE a -> RLE b -> RLE b # (<*) :: RLE a -> RLE b -> RLE a #
Foldable RLE #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods fold :: Monoid m => RLE m -> m # foldMap :: Monoid m => (a -> m) -> RLE a -> m # foldr :: (a -> b -> b) -> b -> RLE a -> b # foldr' :: (a -> b -> b) -> b -> RLE a -> b # foldl :: (b -> a -> b) -> b -> RLE a -> b # foldl' :: (b -> a -> b) -> b -> RLE a -> b # foldr1 :: (a -> a -> a) -> RLE a -> a # foldl1 :: (a -> a -> a) -> RLE a -> a # toList :: RLE a -> [a] # null :: RLE a -> Bool # length :: RLE a -> Int # elem :: Eq a => a -> RLE a -> Bool # maximum :: Ord a => RLE a -> a # minimum :: Ord a => RLE a -> a # sum :: Num a => RLE a -> a # product :: Num a => RLE a -> a #
MonadZip RLE #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods mzip :: RLE a -> RLE b -> RLE (a, b) # mzipWith :: (a -> b -> c) -> RLE a -> RLE b -> RLE c # munzip :: RLE (a, b) -> (RLE a, RLE b) #
Zip RLE #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods zipWith :: (a -> b -> c) -> RLE a -> RLE b -> RLE c # zip :: RLE a -> RLE b -> RLE (a, b) # zap :: RLE (a -> b) -> RLE a -> RLE b #
Lookup RLE #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods lookup :: Key RLE -> RLE a -> Maybe a #
Adjustable RLE #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods adjust :: (a -> a) -> Key RLE -> RLE a -> RLE a # replace :: Key RLE -> a -> RLE a -> RLE a #
Pointed RLE #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods point :: a -> RLE a #
Apply RLE #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods (<.>) :: RLE (a -> b) -> RLE a -> RLE b # (.>) :: RLE a -> RLE b -> RLE b # (<.) :: RLE a -> RLE b -> RLE a # liftF2 :: (a -> b -> c) -> RLE a -> RLE b -> RLE c #
Bind RLE #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods (>>-) :: RLE a -> (a -> RLE b) -> RLE b # join :: RLE (RLE a) -> RLE a #
Eq a => Reducer a (RLE a) #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods unit :: a -> RLE a # snoc :: RLE a -> a -> RLE a # cons :: a -> RLE a -> RLE a #
Eq a => Eq (RLE a) #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods (==) :: RLE a -> RLE a -> Bool # (/=) :: RLE a -> RLE a -> Bool #
Eq a => Semigroup (RLE a) #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods (<>) :: RLE a -> RLE a -> RLE a # sconcat :: NonEmpty (RLE a) -> RLE a # stimes :: Integral b => b -> RLE a -> RLE a #
Eq a => Monoid (RLE a) #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods mempty :: RLE a # mappend :: RLE a -> RLE a -> RLE a # mconcat :: [RLE a] -> RLE a #
Hashable a => Hashable (RLE a) #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods hashWithSalt :: Int -> RLE a -> Int # hash :: RLE a -> Int #
Generator (RLE a) #
Instance details Defined in Data.Compressed.RunLengthEncoding Associated Types type Elem (RLE a) :: * # Methods mapReduce :: (Reducer e m, Monoid m) => (Elem (RLE a) -> e) -> RLE a -> m # mapTo :: (Reducer e m, Monoid m) => (Elem (RLE a) -> e) -> m -> RLE a -> m # mapFrom :: (Reducer e m, Monoid m) => (Elem (RLE a) -> e) -> RLE a -> m -> m #
type Key RLE #
Instance details Defined in Data.Compressed.RunLengthEncoding type Key RLE = Int
type Elem (RLE a) #
Instance details Defined in Data.Compressed.RunLengthEncoding type Elem (RLE a) = a

data Run a #

A single run with a strict length

Instances

Monad Run #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods (>>=) :: Run a -> (a -> Run b) -> Run b # (>>) :: Run a -> Run b -> Run b # return :: a -> Run a # fail :: String -> Run a #
Functor Run #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods fmap :: (a -> b) -> Run a -> Run b # (<$) :: a -> Run b -> Run a #
Applicative Run #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods pure :: a -> Run a # (<>) :: Run (a -> b) -> Run a -> Run b # liftA2 :: (a -> b -> c) -> Run a -> Run b -> Run c # (>) :: Run a -> Run b -> Run b # (<*) :: Run a -> Run b -> Run a #
Foldable Run #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods fold :: Monoid m => Run m -> m # foldMap :: Monoid m => (a -> m) -> Run a -> m # foldr :: (a -> b -> b) -> b -> Run a -> b # foldr' :: (a -> b -> b) -> b -> Run a -> b # foldl :: (b -> a -> b) -> b -> Run a -> b # foldl' :: (b -> a -> b) -> b -> Run a -> b # foldr1 :: (a -> a -> a) -> Run a -> a # foldl1 :: (a -> a -> a) -> Run a -> a # toList :: Run a -> [a] # null :: Run a -> Bool # length :: Run a -> Int # elem :: Eq a => a -> Run a -> Bool # maximum :: Ord a => Run a -> a # minimum :: Ord a => Run a -> a # sum :: Num a => Run a -> a # product :: Num a => Run a -> a #
Comonad Run #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods extract :: Run a -> a # duplicate :: Run a -> Run (Run a) # extend :: (Run a -> b) -> Run a -> Run b #
ComonadApply Run #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods (<@>) :: Run (a -> b) -> Run a -> Run b # (@>) :: Run a -> Run b -> Run b # (<@) :: Run a -> Run b -> Run a #
Pointed Run #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods point :: a -> Run a #
Apply Run #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods (<.>) :: Run (a -> b) -> Run a -> Run b # (.>) :: Run a -> Run b -> Run b # (<.) :: Run a -> Run b -> Run a # liftF2 :: (a -> b -> c) -> Run a -> Run b -> Run c #
Foldable1 Run #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods fold1 :: Semigroup m => Run m -> m # foldMap1 :: Semigroup m => (a -> m) -> Run a -> m # toNonEmpty :: Run a -> NonEmpty a #
Bind Run #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods (>>-) :: Run a -> (a -> Run b) -> Run b # join :: Run (Run a) -> Run a #
Extend Run #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods duplicated :: Run a -> Run (Run a) # extended :: (Run a -> b) -> Run a -> Run b #
Measured Count (Run a) #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods measure :: Run a -> Count #
Eq a => Eq (Run a) #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods (==) :: Run a -> Run a -> Bool # (/=) :: Run a -> Run a -> Bool #
Ord a => Ord (Run a) #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods compare :: Run a -> Run a -> Ordering # (<) :: Run a -> Run a -> Bool # (<=) :: Run a -> Run a -> Bool # (>) :: Run a -> Run a -> Bool # (>=) :: Run a -> Run a -> Bool # max :: Run a -> Run a -> Run a # min :: Run a -> Run a -> Run a #
Show a => Show (Run a) #
Instance details Defined in Data.Compressed.RunLengthEncoding Methods showsPrec :: Int -> Run a -> ShowS # show :: Run a -> String # showList :: [Run a] -> ShowS #

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 #