EdisonCore-1.3.1.1: A library of efficent, purely-functional data structures (Core Implementations)

CopyrightCopyright (c) 1998-1999 2008 Chris Okasaki
LicenseMIT; see COPYRIGHT file for terms and conditions
Maintainerrobdockins AT fastmail DOT fm
Stabilitystable
PortabilityGHC, Hugs (MPTC and FD)
Safe HaskellNone
LanguageHaskell2010

Data.Edison.Seq.RevSeq

Contents

Description

This module defines a sequence adaptor Rev s. If s is a sequence type constructor, then Rev s is a sequence type constructor that is identical to s, except that it is kept in the opposite order. Also keeps explicit track of the size of the sequence, similar to the Sized adaptor in Data.Edison.Seq.SizedSeq.

This module is most useful when s is a sequence type that offers fast access to the front but slow access to the rear, and your application needs the opposite (i.e., fast access to the rear but slow access to the front).

All time complexities are determined by the underlying sequence, except that the complexities for accessing the left and right sides of the sequence are exchanged, and size becomes O( 1 ).

Synopsis

Rev Sequence Type

data Rev s a Source #

Instances

Sequence s => Monad (Rev s) Source # 

Methods

(>>=) :: Rev s a -> (a -> Rev s b) -> Rev s b #

(>>) :: Rev s a -> Rev s b -> Rev s b #

return :: a -> Rev s a #

fail :: String -> Rev s a #

Sequence s => Functor (Rev s) Source # 

Methods

fmap :: (a -> b) -> Rev s a -> Rev s b #

(<$) :: a -> Rev s b -> Rev s a #

Sequence s => Applicative (Rev s) Source # 

Methods

pure :: a -> Rev s a #

(<*>) :: Rev s (a -> b) -> Rev s a -> Rev s b #

(*>) :: Rev s a -> Rev s b -> Rev s b #

(<*) :: Rev s a -> Rev s b -> Rev s a #

Sequence s => Sequence (Rev s) Source # 

Methods

lcons :: a -> Rev s a -> Rev s a #

rcons :: a -> Rev s a -> Rev s a #

fromList :: [a] -> Rev s a #

copy :: Int -> a -> Rev s a #

lview :: Monad m => Rev s a -> m (a, Rev s a) #

lhead :: Rev s a -> a #

lheadM :: Monad m => Rev s a -> m a #

ltail :: Rev s a -> Rev s a #

ltailM :: Monad m => Rev s a -> m (Rev s a) #

rview :: Monad m => Rev s a -> m (a, Rev s a) #

rhead :: Rev s a -> a #

rheadM :: Monad m => Rev s a -> m a #

rtail :: Rev s a -> Rev s a #

rtailM :: Monad m => Rev s a -> m (Rev s a) #

null :: Rev s a -> Bool #

size :: Rev s a -> Int #

toList :: Rev s a -> [a] #

concat :: Rev s (Rev s a) -> Rev s a #

reverse :: Rev s a -> Rev s a #

reverseOnto :: Rev s a -> Rev s a -> Rev s a #

fold :: (a -> b -> b) -> b -> Rev s a -> b #

fold' :: (a -> b -> b) -> b -> Rev s a -> b #

fold1 :: (a -> a -> a) -> Rev s a -> a #

fold1' :: (a -> a -> a) -> Rev s a -> a #

foldr :: (a -> b -> b) -> b -> Rev s a -> b #

foldr' :: (a -> b -> b) -> b -> Rev s a -> b #

foldl :: (b -> a -> b) -> b -> Rev s a -> b #

foldl' :: (b -> a -> b) -> b -> Rev s a -> b #

foldr1 :: (a -> a -> a) -> Rev s a -> a #

foldr1' :: (a -> a -> a) -> Rev s a -> a #

foldl1 :: (a -> a -> a) -> Rev s a -> a #

foldl1' :: (a -> a -> a) -> Rev s a -> a #

reducer :: (a -> a -> a) -> a -> Rev s a -> a #

reducer' :: (a -> a -> a) -> a -> Rev s a -> a #

reducel :: (a -> a -> a) -> a -> Rev s a -> a #

reducel' :: (a -> a -> a) -> a -> Rev s a -> a #

reduce1 :: (a -> a -> a) -> Rev s a -> a #

reduce1' :: (a -> a -> a) -> Rev s a -> a #

take :: Int -> Rev s a -> Rev s a #

drop :: Int -> Rev s a -> Rev s a #

splitAt :: Int -> Rev s a -> (Rev s a, Rev s a) #

subseq :: Int -> Int -> Rev s a -> Rev s a #

filter :: (a -> Bool) -> Rev s a -> Rev s a #

partition :: (a -> Bool) -> Rev s a -> (Rev s a, Rev s a) #

takeWhile :: (a -> Bool) -> Rev s a -> Rev s a #

dropWhile :: (a -> Bool) -> Rev s a -> Rev s a #

splitWhile :: (a -> Bool) -> Rev s a -> (Rev s a, Rev s a) #

inBounds :: Int -> Rev s a -> Bool #

lookup :: Int -> Rev s a -> a #

lookupM :: Monad m => Int -> Rev s a -> m a #

lookupWithDefault :: a -> Int -> Rev s a -> a #

update :: Int -> a -> Rev s a -> Rev s a #

adjust :: (a -> a) -> Int -> Rev s a -> Rev s a #

mapWithIndex :: (Int -> a -> b) -> Rev s a -> Rev s b #

foldrWithIndex :: (Int -> a -> b -> b) -> b -> Rev s a -> b #

foldrWithIndex' :: (Int -> a -> b -> b) -> b -> Rev s a -> b #

foldlWithIndex :: (b -> Int -> a -> b) -> b -> Rev s a -> b #

foldlWithIndex' :: (b -> Int -> a -> b) -> b -> Rev s a -> b #

zip :: Rev s a -> Rev s b -> Rev s (a, b) #

zip3 :: Rev s a -> Rev s b -> Rev s c -> Rev s (a, b, c) #

zipWith :: (a -> b -> c) -> Rev s a -> Rev s b -> Rev s c #

zipWith3 :: (a -> b -> c -> d) -> Rev s a -> Rev s b -> Rev s c -> Rev s d #

unzip :: Rev s (a, b) -> (Rev s a, Rev s b) #

unzip3 :: Rev s (a, b, c) -> (Rev s a, Rev s b, Rev s c) #

unzipWith :: (a -> b) -> (a -> c) -> Rev s a -> (Rev s b, Rev s c) #

unzipWith3 :: (a -> b) -> (a -> c) -> (a -> d) -> Rev s a -> (Rev s b, Rev s c, Rev s d) #

strict :: Rev s a -> Rev s a #

strictWith :: (a -> b) -> Rev s a -> Rev s a #

structuralInvariant :: Rev s a -> Bool #

instanceName :: Rev s a -> String #

Sequence s => Alternative (Rev s) Source # 

Methods

empty :: Rev s a #

(<|>) :: Rev s a -> Rev s a -> Rev s a #

some :: Rev s a -> Rev s [a] #

many :: Rev s a -> Rev s [a] #

Sequence s => MonadPlus (Rev s) Source # 

Methods

mzero :: Rev s a #

mplus :: Rev s a -> Rev s a -> Rev s a #

Eq (s a) => Eq (Rev s a) Source # 

Methods

(==) :: Rev s a -> Rev s a -> Bool #

(/=) :: Rev s a -> Rev s a -> Bool #

(Sequence s, Ord a, Eq (s a)) => Ord (Rev s a) Source # 

Methods

compare :: Rev s a -> Rev s a -> Ordering #

(<) :: Rev s a -> Rev s a -> Bool #

(<=) :: Rev s a -> Rev s a -> Bool #

(>) :: Rev s a -> Rev s a -> Bool #

(>=) :: Rev s a -> Rev s a -> Bool #

max :: Rev s a -> Rev s a -> Rev s a #

min :: Rev s a -> Rev s a -> Rev s a #

(Sequence s, Read (s a)) => Read (Rev s a) Source # 

Methods

readsPrec :: Int -> ReadS (Rev s a) #

readList :: ReadS [Rev s a] #

readPrec :: ReadPrec (Rev s a) #

readListPrec :: ReadPrec [Rev s a] #

(Sequence s, Show (s a)) => Show (Rev s a) Source # 

Methods

showsPrec :: Int -> Rev s a -> ShowS #

show :: Rev s a -> String #

showList :: [Rev s a] -> ShowS #

Sequence s => Monoid (Rev s a) Source # 

Methods

mempty :: Rev s a #

mappend :: Rev s a -> Rev s a -> Rev s a #

mconcat :: [Rev s a] -> Rev s a #

(Sequence s, Arbitrary (s a)) => Arbitrary (Rev s a) Source # 

Methods

arbitrary :: Gen (Rev s a) #

shrink :: Rev s a -> [Rev s a] #

(Sequence s, CoArbitrary (s a)) => CoArbitrary (Rev s a) Source # 

Methods

coarbitrary :: Rev s a -> Gen b -> Gen b #

Sequence Operations

empty :: Sequence s => Rev s a Source #

singleton :: Sequence s => a -> Rev s a Source #

lcons :: Sequence s => a -> Rev s a -> Rev s a Source #

rcons :: Sequence s => a -> Rev s a -> Rev s a Source #

append :: Sequence s => Rev s a -> Rev s a -> Rev s a Source #

lview :: (Sequence s, Monad m) => Rev s a -> m (a, Rev s a) Source #

lhead :: Sequence s => Rev s a -> a Source #

ltail :: Sequence s => Rev s a -> Rev s a Source #

rview :: (Sequence s, Monad m) => Rev s a -> m (a, Rev s a) Source #

rhead :: Sequence s => Rev s a -> a Source #

rtail :: Sequence s => Rev s a -> Rev s a Source #

lheadM :: (Sequence s, Monad m) => Rev s a -> m a Source #

ltailM :: (Sequence s, Monad m) => Rev s a -> m (Rev s a) Source #

rheadM :: (Sequence s, Monad m) => Rev s a -> m a Source #

rtailM :: (Sequence s, Monad m) => Rev s a -> m (Rev s a) Source #

null :: Sequence s => Rev s a -> Bool Source #

size :: Sequence s => Rev s a -> Int Source #

concat :: Sequence s => Rev s (Rev s a) -> Rev s a Source #

reverse :: Sequence s => Rev s a -> Rev s a Source #

reverseOnto :: Sequence s => Rev s a -> Rev s a -> Rev s a Source #

fromList :: Sequence s => [a] -> Rev s a Source #

toList :: Sequence s => Rev s a -> [a] Source #

map :: Sequence s => (a -> b) -> Rev s a -> Rev s b Source #

concatMap :: Sequence s => (a -> Rev s b) -> Rev s a -> Rev s b Source #

fold :: Sequence s => (a -> b -> b) -> b -> Rev s a -> b Source #

fold' :: Sequence s => (a -> b -> b) -> b -> Rev s a -> b Source #

fold1 :: Sequence s => (a -> a -> a) -> Rev s a -> a Source #

fold1' :: Sequence s => (a -> a -> a) -> Rev s a -> a Source #

foldr :: Sequence s => (a -> b -> b) -> b -> Rev s a -> b Source #

foldr' :: Sequence s => (a -> b -> b) -> b -> Rev s a -> b Source #

foldl :: Sequence s => (b -> a -> b) -> b -> Rev s a -> b Source #

foldl' :: Sequence s => (b -> a -> b) -> b -> Rev s a -> b Source #

foldr1 :: Sequence s => (a -> a -> a) -> Rev s a -> a Source #

foldr1' :: Sequence s => (a -> a -> a) -> Rev s a -> a Source #

foldl1 :: Sequence s => (a -> a -> a) -> Rev s a -> a Source #

foldl1' :: Sequence s => (a -> a -> a) -> Rev s a -> a Source #

reducer :: Sequence s => (a -> a -> a) -> a -> Rev s a -> a Source #

reducer' :: Sequence s => (a -> a -> a) -> a -> Rev s a -> a Source #

reducel :: Sequence s => (a -> a -> a) -> a -> Rev s a -> a Source #

reducel' :: Sequence s => (a -> a -> a) -> a -> Rev s a -> a Source #

reduce1 :: Sequence s => (a -> a -> a) -> Rev s a -> a Source #

reduce1' :: Sequence s => (a -> a -> a) -> Rev s a -> a Source #

copy :: Sequence s => Int -> a -> Rev s a Source #

inBounds :: Sequence s => Int -> Rev s a -> Bool Source #

lookup :: Sequence s => Int -> Rev s a -> a Source #

lookupM :: (Sequence s, Monad m) => Int -> Rev s a -> m a Source #

lookupWithDefault :: Sequence s => a -> Int -> Rev s a -> a Source #

update :: Sequence s => Int -> a -> Rev s a -> Rev s a Source #

adjust :: Sequence s => (a -> a) -> Int -> Rev s a -> Rev s a Source #

mapWithIndex :: Sequence s => (Int -> a -> b) -> Rev s a -> Rev s b Source #

foldrWithIndex :: Sequence s => (Int -> a -> b -> b) -> b -> Rev s a -> b Source #

foldrWithIndex' :: Sequence s => (Int -> a -> b -> b) -> b -> Rev s a -> b Source #

foldlWithIndex :: Sequence s => (b -> Int -> a -> b) -> b -> Rev s a -> b Source #

foldlWithIndex' :: Sequence s => (b -> Int -> a -> b) -> b -> Rev s a -> b Source #

take :: Sequence s => Int -> Rev s a -> Rev s a Source #

drop :: Sequence s => Int -> Rev s a -> Rev s a Source #

splitAt :: Sequence s => Int -> Rev s a -> (Rev s a, Rev s a) Source #

subseq :: Sequence s => Int -> Int -> Rev s a -> Rev s a Source #

filter :: Sequence s => (a -> Bool) -> Rev s a -> Rev s a Source #

partition :: Sequence s => (a -> Bool) -> Rev s a -> (Rev s a, Rev s a) Source #

takeWhile :: Sequence s => (a -> Bool) -> Rev s a -> Rev s a Source #

dropWhile :: Sequence s => (a -> Bool) -> Rev s a -> Rev s a Source #

splitWhile :: Sequence s => (a -> Bool) -> Rev s a -> (Rev s a, Rev s a) Source #

zip :: Sequence s => Rev s a -> Rev s b -> Rev s (a, b) Source #

zip3 :: Sequence s => Rev s a -> Rev s b -> Rev s c -> Rev s (a, b, c) Source #

zipWith :: Sequence s => (a -> b -> c) -> Rev s a -> Rev s b -> Rev s c Source #

zipWith3 :: Sequence s => (a -> b -> c -> d) -> Rev s a -> Rev s b -> Rev s c -> Rev s d Source #

unzip :: Sequence s => Rev s (a, b) -> (Rev s a, Rev s b) Source #

unzip3 :: Sequence s => Rev s (a, b, c) -> (Rev s a, Rev s b, Rev s c) Source #

unzipWith :: Sequence s => (a -> b) -> (a -> c) -> Rev s a -> (Rev s b, Rev s c) Source #

unzipWith3 :: Sequence s => (a -> b) -> (a -> c) -> (a -> d) -> Rev s a -> (Rev s b, Rev s c, Rev s d) Source #

strict :: Sequence s => Rev s a -> Rev s a Source #

strictWith :: Sequence s => (a -> b) -> Rev s a -> Rev s a Source #

Unit testing

Documentation

Other supported operations

fromSeq :: Sequence s => s a -> Rev s a Source #

toSeq :: Sequence s => Rev s a -> s a Source #