EdisonCore-1.3.2: A library of efficient, 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.SizedSeq

Contents

Description

This module defines a sequence adaptor Sized s. If s is a sequence type constructor, then Sized s is a sequence type constructor that is identical to s, except that it also keeps track of the current size of each sequence.

All time complexities are determined by the underlying sequence, except that size becomes O( 1 ).

Synopsis

Sized Sequence Type

data Sized s a Source #

Instances

Sequence s => Monad (Sized s) Source # 

Methods

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

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

return :: a -> Sized s a #

fail :: String -> Sized s a #

Sequence s => Functor (Sized s) Source # 

Methods

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

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

Sequence s => Applicative (Sized s) Source # 

Methods

pure :: a -> Sized s a #

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

liftA2 :: (a -> b -> c) -> Sized s a -> Sized s b -> Sized s c #

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

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

Sequence s => Sequence (Sized s) Source # 

Methods

lcons :: a -> Sized s a -> Sized s a #

rcons :: a -> Sized s a -> Sized s a #

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

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

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

lhead :: Sized s a -> a #

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

ltail :: Sized s a -> Sized s a #

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

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

rhead :: Sized s a -> a #

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

rtail :: Sized s a -> Sized s a #

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

null :: Sized s a -> Bool #

size :: Sized s a -> Int #

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

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

reverse :: Sized s a -> Sized s a #

reverseOnto :: Sized s a -> Sized s a -> Sized s a #

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

strict :: Sized s a -> Sized s a #

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

structuralInvariant :: Sized s a -> Bool #

instanceName :: Sized s a -> String #

Sequence s => Alternative (Sized s) Source # 

Methods

empty :: Sized s a #

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

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

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

Sequence s => MonadPlus (Sized s) Source # 

Methods

mzero :: Sized s a #

mplus :: Sized s a -> Sized s a -> Sized s a #

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

Methods

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

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

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

Methods

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

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

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

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

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

max :: Sized s a -> Sized s a -> Sized s a #

min :: Sized s a -> Sized s a -> Sized s a #

(Sequence s, Read (s a)) => Read (Sized s a) Source # 
(Sequence s, Show (s a)) => Show (Sized s a) Source # 

Methods

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

show :: Sized s a -> String #

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

Sequence s => Semigroup (Sized s a) Source # 

Methods

(<>) :: Sized s a -> Sized s a -> Sized s a #

sconcat :: NonEmpty (Sized s a) -> Sized s a #

stimes :: Integral b => b -> Sized s a -> Sized s a #

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

Methods

mempty :: Sized s a #

mappend :: Sized s a -> Sized s a -> Sized s a #

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

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

Methods

arbitrary :: Gen (Sized s a) #

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

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

Methods

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

Sequence Operations

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Unit testing

Documentation

Other supported operations

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

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