Copyright	Copyright (c) 1998-1999 2008 Chris Okasaki
License	MIT; see COPYRIGHT file for terms and conditions
Maintainer	robdockins AT fastmail DOT fm
Stability	stable
Portability	GHC, Hugs (MPTC and FD)
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Edison.Seq.SizedSeq

Contents

Sized Sequence Type
Sequence Operations
Unit testing
Documentation
Other supported operations

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

data Sized s a
empty :: Sequence s => Sized s a
singleton :: Sequence s => a -> Sized s a
lcons :: Sequence s => a -> Sized s a -> Sized s a
rcons :: Sequence s => a -> Sized s a -> Sized s a
append :: Sequence s => Sized s a -> Sized s a -> Sized s a
lview :: (Sequence s, MonadFail m) => Sized s a -> m (a, Sized s a)
lhead :: Sequence s => Sized s a -> a
ltail :: Sequence s => Sized s a -> Sized s a
rview :: (Sequence s, MonadFail m) => Sized s a -> m (a, Sized s a)
rhead :: Sequence s => Sized s a -> a
rtail :: Sequence s => Sized s a -> Sized s a
lheadM :: (Sequence s, MonadFail m) => Sized s a -> m a
ltailM :: (Sequence s, MonadFail m) => Sized s a -> m (Sized s a)
rheadM :: (Sequence s, MonadFail m) => Sized s a -> m a
rtailM :: (Sequence s, MonadFail m) => Sized s a -> m (Sized s a)
null :: Sequence s => Sized s a -> Bool
size :: Sequence s => Sized s a -> Int
concat :: Sequence s => Sized s (Sized s a) -> Sized s a
reverse :: Sequence s => Sized s a -> Sized s a
reverseOnto :: Sequence s => Sized s a -> Sized s a -> Sized s a
fromList :: Sequence s => [a] -> Sized s a
toList :: Sequence s => Sized s a -> [a]
map :: Sequence s => (a -> b) -> Sized s a -> Sized s b
concatMap :: Sequence s => (a -> Sized s b) -> Sized s a -> Sized s b
fold :: Sequence s => (a -> b -> b) -> b -> Sized s a -> b
fold' :: Sequence s => (a -> b -> b) -> b -> Sized s a -> b
fold1 :: Sequence s => (a -> a -> a) -> Sized s a -> a
fold1' :: Sequence s => (a -> a -> a) -> Sized s a -> a
foldr :: Sequence s => (a -> b -> b) -> b -> Sized s a -> b
foldr' :: Sequence s => (a -> b -> b) -> b -> Sized s a -> b
foldl :: Sequence s => (b -> a -> b) -> b -> Sized s a -> b
foldl' :: Sequence s => (b -> a -> b) -> b -> Sized s a -> b
foldr1 :: Sequence s => (a -> a -> a) -> Sized s a -> a
foldr1' :: Sequence s => (a -> a -> a) -> Sized s a -> a
foldl1 :: Sequence s => (a -> a -> a) -> Sized s a -> a
foldl1' :: Sequence s => (a -> a -> a) -> Sized s a -> a
reducer :: Sequence s => (a -> a -> a) -> a -> Sized s a -> a
reducer' :: Sequence s => (a -> a -> a) -> a -> Sized s a -> a
reducel :: Sequence s => (a -> a -> a) -> a -> Sized s a -> a
reducel' :: Sequence s => (a -> a -> a) -> a -> Sized s a -> a
reduce1 :: Sequence s => (a -> a -> a) -> Sized s a -> a
reduce1' :: Sequence s => (a -> a -> a) -> Sized s a -> a
copy :: Sequence s => Int -> a -> Sized s a
inBounds :: Sequence s => Int -> Sized s a -> Bool
lookup :: Sequence s => Int -> Sized s a -> a
lookupM :: (Sequence s, MonadFail m) => Int -> Sized s a -> m a
lookupWithDefault :: Sequence s => a -> Int -> Sized s a -> a
update :: Sequence s => Int -> a -> Sized s a -> Sized s a
adjust :: Sequence s => (a -> a) -> Int -> Sized s a -> Sized s a
mapWithIndex :: Sequence s => (Int -> a -> b) -> Sized s a -> Sized s b
foldrWithIndex :: Sequence s => (Int -> a -> b -> b) -> b -> Sized s a -> b
foldlWithIndex :: Sequence s => (b -> Int -> a -> b) -> b -> Sized s a -> b
foldrWithIndex' :: Sequence s => (Int -> a -> b -> b) -> b -> Sized s a -> b
foldlWithIndex' :: Sequence s => (b -> Int -> a -> b) -> b -> Sized s a -> b
take :: Sequence s => Int -> Sized s a -> Sized s a
drop :: Sequence s => Int -> Sized s a -> Sized s a
splitAt :: Sequence s => Int -> Sized s a -> (Sized s a, Sized s a)
subseq :: Sequence s => Int -> Int -> Sized s a -> Sized s a
filter :: Sequence s => (a -> Bool) -> Sized s a -> Sized s a
partition :: Sequence s => (a -> Bool) -> Sized s a -> (Sized s a, Sized s a)
takeWhile :: Sequence s => (a -> Bool) -> Sized s a -> Sized s a
dropWhile :: Sequence s => (a -> Bool) -> Sized s a -> Sized s a
splitWhile :: Sequence s => (a -> Bool) -> Sized s a -> (Sized s a, Sized s a)
zip :: Sequence s => Sized s a -> Sized s b -> Sized s (a, b)
zip3 :: Sequence s => Sized s a -> Sized s b -> Sized s c -> Sized s (a, b, c)
zipWith :: Sequence s => (a -> b -> c) -> Sized s a -> Sized s b -> Sized s c
zipWith3 :: Sequence s => (a -> b -> c -> d) -> Sized s a -> Sized s b -> Sized s c -> Sized s d
unzip :: Sequence s => Sized s (a, b) -> (Sized s a, Sized s b)
unzip3 :: Sequence s => Sized s (a, b, c) -> (Sized s a, Sized s b, Sized s c)
unzipWith :: Sequence s => (a -> b) -> (a -> c) -> Sized s a -> (Sized s b, Sized s c)
unzipWith3 :: Sequence s => (a -> b) -> (a -> c) -> (a -> d) -> Sized s a -> (Sized s b, Sized s c, Sized s d)
strict :: Sequence s => Sized s a -> Sized s a
strictWith :: Sequence s => (a -> b) -> Sized s a -> Sized s a
structuralInvariant :: Sequence s => Sized s a -> Bool
moduleName :: String
instanceName :: Sequence s => Sized s a -> String
fromSeq :: Sequence s => s a -> Sized s a
toSeq :: Sequence s => Sized s a -> s a

Sized Sequence Type

data Sized s a Source #

Instances

Instances details

Sequence s => Sequence (Sized s) Source #
Instance details Defined in Data.Edison.Seq.SizedSeq 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 :: MonadFail m => Sized s a -> m (a, Sized s a) # lhead :: Sized s a -> a # lheadM :: MonadFail m => Sized s a -> m a # ltail :: Sized s a -> Sized s a # ltailM :: MonadFail m => Sized s a -> m (Sized s a) # rview :: MonadFail m => Sized s a -> m (a, Sized s a) # rhead :: Sized s a -> a # rheadM :: MonadFail m => Sized s a -> m a # rtail :: Sized s a -> Sized s a # rtailM :: MonadFail 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 :: MonadFail 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 #
Instance details Defined in Data.Edison.Seq.SizedSeq 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 => Applicative (Sized s) Source #
Instance details Defined in Data.Edison.Seq.SizedSeq 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 => Functor (Sized s) Source #
Instance details Defined in Data.Edison.Seq.SizedSeq Methods fmap :: (a -> b) -> Sized s a -> Sized s b # (<$) :: a -> Sized s b -> Sized s a #
Sequence s => Monad (Sized s) Source #
Instance details Defined in Data.Edison.Seq.SizedSeq 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 #
Sequence s => MonadPlus (Sized s) Source #
Instance details Defined in Data.Edison.Seq.SizedSeq Methods mzero :: Sized s a # mplus :: Sized s a -> Sized s a -> Sized s a #
(Sequence s, Arbitrary (s a)) => Arbitrary (Sized s a) Source #
Instance details Defined in Data.Edison.Seq.SizedSeq Methods arbitrary :: Gen (Sized s a) # shrink :: Sized s a -> [Sized s a] #
(Sequence s, CoArbitrary (s a)) => CoArbitrary (Sized s a) Source #
Instance details Defined in Data.Edison.Seq.SizedSeq Methods coarbitrary :: Sized s a -> Gen b -> Gen b #
Sequence s => Monoid (Sized s a) Source #
Instance details Defined in Data.Edison.Seq.SizedSeq Methods mempty :: Sized s a # mappend :: Sized s a -> Sized s a -> Sized s a # mconcat :: [Sized s a] -> Sized s a #
Sequence s => Semigroup (Sized s a) Source #
Instance details Defined in Data.Edison.Seq.SizedSeq 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, Read (s a)) => Read (Sized s a) Source #
Instance details Defined in Data.Edison.Seq.SizedSeq Methods readsPrec :: Int -> ReadS (Sized s a) # readList :: ReadS [Sized s a] # readPrec :: ReadPrec (Sized s a) # readListPrec :: ReadPrec [Sized s a] #
(Sequence s, Show (s a)) => Show (Sized s a) Source #
Instance details Defined in Data.Edison.Seq.SizedSeq Methods showsPrec :: Int -> Sized s a -> ShowS # show :: Sized s a -> String # showList :: [Sized s a] -> ShowS #
Eq (s a) => Eq (Sized s a) Source #
Instance details Defined in Data.Edison.Seq.SizedSeq 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 #
Instance details Defined in Data.Edison.Seq.SizedSeq 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 Operations

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

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, MonadFail 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, MonadFail 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, MonadFail m) => Sized s a -> m a Source #

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

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

rtailM :: (Sequence s, MonadFail 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, MonadFail 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

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

Documentation

moduleName :: String Source #

instanceName :: Sequence s => Sized s a -> String Source #

Other supported operations

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

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