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	None
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

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 #
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 #
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

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, 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

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 #