EdisonCore-1.3: 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.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 
Sequence s => Functor (Sized s) Source 
Sequence s => Applicative (Sized s) Source 
Sequence s => Sequence (Sized s) Source 
Sequence s => Alternative (Sized s) Source 
Sequence s => MonadPlus (Sized s) Source 
Eq (s a) => Eq (Sized s a) Source 
(Sequence s, Ord a, Eq (s a)) => Ord (Sized s a) Source 
(Sequence s, Read (s a)) => Read (Sized s a) Source 
(Sequence s, Show (s a)) => Show (Sized s a) Source 
(Sequence s, Arbitrary (s a)) => Arbitrary (Sized s a) Source 
(Sequence s, CoArbitrary (s a)) => CoArbitrary (Sized s a) Source 
Sequence s => Monoid (Sized s a) Source 

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