Data.Compressed.RunLengthEncoding

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.

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

Methods

(>>=) :: RLE a -> (a -> RLE b) -> RLE b

(>>) :: RLE a -> RLE b -> RLE b

return :: a -> RLE a

fail :: String -> RLE a

Functor RLE

Methods

fmap :: (a -> b) -> RLE a -> RLE b

(<$) :: a -> RLE b -> RLE a

Applicative RLE

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

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

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

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

Methods

lookup :: Key RLE -> RLE a -> Maybe a

Adjustable RLE

Methods

adjust :: (a -> a) -> Key RLE -> RLE a -> RLE a

replace :: Key RLE -> a -> RLE a -> RLE a

Pointed RLE

Methods

point :: a -> RLE a

Apply RLE

Methods

(<.>) :: RLE (a -> b) -> RLE a -> RLE b

(.>) :: RLE a -> RLE b -> RLE b

(<.) :: RLE a -> RLE b -> RLE a

Bind RLE

Methods

(>>-) :: RLE a -> (a -> RLE b) -> RLE b

join :: RLE (RLE a) -> RLE a

Eq a => Reducer a (RLE a)

Methods

unit :: a -> RLE a

snoc :: RLE a -> a -> RLE a

cons :: a -> RLE a -> RLE a

Eq a => Eq (RLE a)

Methods

(==) :: RLE a -> RLE a -> Bool

(/=) :: RLE a -> RLE a -> Bool

Eq a => Semigroup (RLE a)

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)

Methods

mempty :: RLE a

mappend :: RLE a -> RLE a -> RLE a

mconcat :: [RLE a] -> RLE a

Hashable a => Hashable (RLE a)

Methods

hashWithSalt :: Int -> RLE a -> Int

hash :: RLE a -> Int

Generator (RLE a)

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

type Key RLE = Int

type Elem (RLE a)

type Elem (RLE a) = a

data Run a

A single run with a strict length

Instances

Monad Run

Methods

(>>=) :: Run a -> (a -> Run b) -> Run b

(>>) :: Run a -> Run b -> Run b

return :: a -> Run a

fail :: String -> Run a

Functor Run

Methods

fmap :: (a -> b) -> Run a -> Run b

(<$) :: a -> Run b -> Run a

Applicative Run

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

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

Methods

extract :: Run a -> a

duplicate :: Run a -> Run (Run a)

extend :: (Run a -> b) -> Run a -> Run b

ComonadApply Run

Methods

(<@>) :: Run (a -> b) -> Run a -> Run b

(@>) :: Run a -> Run b -> Run b

(<@) :: Run a -> Run b -> Run a

Pointed Run

Methods

point :: a -> Run a

Apply Run

Methods

(<.>) :: Run (a -> b) -> Run a -> Run b

(.>) :: Run a -> Run b -> Run b

(<.) :: Run a -> Run b -> Run a

Foldable1 Run

Methods

fold1 :: Semigroup m => Run m -> m

foldMap1 :: Semigroup m => (a -> m) -> Run a -> m

toNonEmpty :: Run a -> NonEmpty a

Bind Run

Methods

(>>-) :: Run a -> (a -> Run b) -> Run b

join :: Run (Run a) -> Run a

Extend Run

Methods

duplicated :: Run a -> Run (Run a)

extended :: (Run a -> b) -> Run a -> Run b

Measured Count (Run a)

Methods

measure :: Run a -> Count

Eq a => Eq (Run a)

Methods

(==) :: Run a -> Run a -> Bool

(/=) :: Run a -> Run a -> Bool

Ord a => Ord (Run a)

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)

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