Portability | GHC, Hugs (MPTC and FD) |
---|---|
Stability | stable |
Maintainer | robdockins AT fastmail DOT fm |
The sequence abstraction is usually viewed as a hierarchy of ADTs including lists, queues, deques, catenable lists, etc. However, such a hierarchy is based on efficiency rather than functionality. For example, a list supports all the operations that a deque supports, even though some of the operations may be inefficient. Hence, in Edison, all sequence data structures are defined as instances of the single Sequence class:
class (Functor s, MonadPlus s) => Sequence s
All sequences are also instances of Functor
, Monad
, and MonadPlus
.
In addition, all sequences are expected to be instances of Eq
, Show
,
and Read
, although this is not enforced.
We follow the naming convention that every module implementing sequences
defines a type constructor named Seq
.
For each method the "default" complexity is listed. Individual implementations may differ for some methods. The documentation for each implementation will list those methods for which the running time differs from these.
A description of each Sequence function appears below. In most cases psudeocode is also provided. Obviously, the psudeocode is illustrative only.
Sequences are represented in psudecode between angle brackets:
<x0,x1,x2...,xn-1>
Such that x0
is at the left (front) of the sequence and
xn-1
is at the right (rear) of the sequence.
- map :: Sequence s => (a -> b) -> s a -> s b
- singleton :: Sequence s => a -> s a
- concatMap :: Sequence s => (a -> s b) -> s a -> s b
- empty :: Sequence s => s a
- append :: Sequence s => s a -> s a -> s a
- class (Functor s, MonadPlus s) => Sequence s where
- lcons :: a -> s a -> s a
- rcons :: a -> s a -> s a
- fromList :: [a] -> s a
- copy :: Int -> a -> s a
- lview :: Monad m => s a -> m (a, s a)
- lhead :: s a -> a
- lheadM :: Monad m => s a -> m a
- ltail :: s a -> s a
- ltailM :: Monad m => s a -> m (s a)
- rview :: Monad m => s a -> m (a, s a)
- rhead :: s a -> a
- rheadM :: Monad m => s a -> m a
- rtail :: s a -> s a
- rtailM :: Monad m => s a -> m (s a)
- null :: s a -> Bool
- size :: s a -> Int
- toList :: s a -> [a]
- concat :: s (s a) -> s a
- reverse :: s a -> s a
- reverseOnto :: s a -> s a -> s a
- fold :: (a -> b -> b) -> b -> s a -> b
- fold' :: (a -> b -> b) -> b -> s a -> b
- fold1 :: (a -> a -> a) -> s a -> a
- fold1' :: (a -> a -> a) -> s a -> a
- foldr :: (a -> b -> b) -> b -> s a -> b
- foldr' :: (a -> b -> b) -> b -> s a -> b
- foldl :: (b -> a -> b) -> b -> s a -> b
- foldl' :: (b -> a -> b) -> b -> s a -> b
- foldr1 :: (a -> a -> a) -> s a -> a
- foldr1' :: (a -> a -> a) -> s a -> a
- foldl1 :: (a -> a -> a) -> s a -> a
- foldl1' :: (a -> a -> a) -> s a -> a
- reducer :: (a -> a -> a) -> a -> s a -> a
- reducer' :: (a -> a -> a) -> a -> s a -> a
- reducel :: (a -> a -> a) -> a -> s a -> a
- reducel' :: (a -> a -> a) -> a -> s a -> a
- reduce1 :: (a -> a -> a) -> s a -> a
- reduce1' :: (a -> a -> a) -> s a -> a
- take :: Int -> s a -> s a
- drop :: Int -> s a -> s a
- splitAt :: Int -> s a -> (s a, s a)
- subseq :: Int -> Int -> s a -> s a
- filter :: (a -> Bool) -> s a -> s a
- partition :: (a -> Bool) -> s a -> (s a, s a)
- takeWhile :: (a -> Bool) -> s a -> s a
- dropWhile :: (a -> Bool) -> s a -> s a
- splitWhile :: (a -> Bool) -> s a -> (s a, s a)
- inBounds :: Int -> s a -> Bool
- lookup :: Int -> s a -> a
- lookupM :: Monad m => Int -> s a -> m a
- lookupWithDefault :: a -> Int -> s a -> a
- update :: Int -> a -> s a -> s a
- adjust :: (a -> a) -> Int -> s a -> s a
- mapWithIndex :: (Int -> a -> b) -> s a -> s b
- foldrWithIndex :: (Int -> a -> b -> b) -> b -> s a -> b
- foldrWithIndex' :: (Int -> a -> b -> b) -> b -> s a -> b
- foldlWithIndex :: (b -> Int -> a -> b) -> b -> s a -> b
- foldlWithIndex' :: (b -> Int -> a -> b) -> b -> s a -> b
- zip :: s a -> s b -> s (a, b)
- zip3 :: s a -> s b -> s c -> s (a, b, c)
- zipWith :: (a -> b -> c) -> s a -> s b -> s c
- zipWith3 :: (a -> b -> c -> d) -> s a -> s b -> s c -> s d
- unzip :: s (a, b) -> (s a, s b)
- unzip3 :: s (a, b, c) -> (s a, s b, s c)
- unzipWith :: (a -> b) -> (a -> c) -> s a -> (s b, s c)
- unzipWith3 :: (a -> b) -> (a -> c) -> (a -> d) -> s a -> (s b, s c, s d)
- strict :: s a -> s a
- strictWith :: (a -> b) -> s a -> s a
- structuralInvariant :: s a -> Bool
- instanceName :: s a -> String
Superclass aliases
Functor aliases
map :: Sequence s => (a -> b) -> s a -> s bSource
Return the result of applying a function to
every element of a sequence. Identical
to fmap
from Functor
.
map f <x0,...,xn-1> = <f x0,...,f xn-1>
Axioms:
map f empty = empty
map f (lcons x xs) = lcons (f x) (map f xs)
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of f
Monad aliases
singleton :: Sequence s => a -> s aSource
Create a singleton sequence. Identical to return
from Monad
.
singleton x = <x>
Axioms:
singleton x = lcons x empty = rcons x empty
This function is always unambiguous.
Default running time: O( 1 )
concatMap :: Sequence s => (a -> s b) -> s a -> s bSource
Apply a sequence-producing function to every element
of a sequence and flatten the result. concatMap
is the bind (>>=)
operation of from Monad
with the
arguments in the reverse order.
concatMap f xs = concat (map f xs)
Axioms:
concatMap f xs = concat (map f xs)
This function is always unambiguous.
Default running time: O( t * n + m )
where n
is the length of the input sequence, m
is the
length of the output sequence, and t
is the running time of f
MonadPlus aliases
empty :: Sequence s => s aSource
The empty sequence. Identical to mzero
from MonadPlus
.
empty = <>
This function is always unambiguous.
Default running time: O( 1 )
append :: Sequence s => s a -> s a -> s aSource
Append two sequence, with the first argument on the left
and the second argument on the right. Identical to mplus
from MonadPlus
.
append <x0,...,xn-1> <y0,...,ym-1> = <x0,...,xn-1,y0,...,ym-1>
Axioms:
append xs ys = foldr lcons ys xs
This function is always unambiguous.
Default running time: O( n1 )
The Sequence class
class (Functor s, MonadPlus s) => Sequence s whereSource
The Sequence
class defines an interface for datatypes which
implement sequences. A description for each function is
given below.
lcons :: a -> s a -> s aSource
Add a new element to the front/left of a sequence
lcons x <x0,...,xn-1> = <x,x0,...,xn-1>
Axioms:
lcons x xs = append (singleton x) xs
This function is always unambiguous.
Default running time: O( 1 )
rcons :: a -> s a -> s aSource
Add a new element to the right/rear of a sequence
rcons x <x0,...,xn-1> = <x0,...,xn-1,x>
Axioms:
rcons x xs = append xs (singleton x)
This function is always unambiguous.
Default running time: O( n )
Convert a list into a sequence
fromList [x0,...,xn-1] = <x0,...,xn-1>
Axioms:
fromList xs = foldr lcons empty xs
This function is always unambiguous.
Default running time: O( n )
Create a sequence containing n
copies of the given element.
Return empty
if n<0
.
copy n x = <x,...,x>
Axioms:
n > 0 ==> copy n x = cons x (copy (n-1) x)
n <= 0 ==> copy n x = empty
This function is always unambiguous.
Default running time: O( n )
lview :: Monad m => s a -> m (a, s a)Source
Separate a sequence into its first (leftmost) element and the
remaining sequence. Calls fail
if the sequence is empty.
Axioms:
lview empty = fail
lview (lcons x xs) = return (x,xs)
This function is always unambiguous.
Default running time: O( 1 )
Return the first element of a sequence. Signals an error if the sequence is empty.
Axioms:
lhead empty = undefined
lhead (lcons x xs) = x
This function is always unambiguous.
Default running time: O( 1 )
lheadM :: Monad m => s a -> m aSource
Returns the first element of a sequence.
Calls fail
if the sequence is empty.
Axioms:
lheadM empty = fail
lheadM (lcons x xs) = return x
This function is always unambiguous.
Default running time: O( 1 )
Delete the first element of the sequence. Signals error if sequence is empty.
Axioms:
ltail empty = undefined
ltail (lcons x xs) = xs
This function is always unambiguous.
Default running time: O( 1 )
ltailM :: Monad m => s a -> m (s a)Source
Delete the first element of the sequence.
Calls fail
if the sequence is empty.
Axioms:
ltailM empty = fail
ltailM (lcons x xs) = return xs
This function is always unambiguous.
Default running time: O( 1 )
rview :: Monad m => s a -> m (a, s a)Source
Separate a sequence into its last (rightmost) element and the
remaining sequence. Calls fail
if the sequence is empty.
Axioms:
rview empty = fail
rview (rcons x xs) = return (x,xs)
This function is always unambiguous.
Default running time: O( n )
Return the last (rightmost) element of the sequence. Signals error if sequence is empty.
Axioms:
rhead empty = undefined
rhead (rcons x xs) = x
This function is always unambiguous.
Default running time: O( n )
rheadM :: Monad m => s a -> m aSource
Returns the last element of the sequence.
Calls fail
if the sequence is empty.
Axioms:
rheadM empty = fail
rheadM (rcons x xs) = return x
This function is always unambiguous.
Default running time: O( n )
Delete the last (rightmost) element of the sequence. Signals an error if the sequence is empty.
Axioms:
rtail empty = undefined
rtail (rcons x xs) = xs
This function is always unambiguous.
Default running time: O( n )
rtailM :: Monad m => s a -> m (s a)Source
Delete the last (rightmost) element of the sequence.
Calls fail
of the sequence is empty
Axioms:
rtailM empty = fail
rtailM (rcons x xs) = return xs
This function is always unambiguous.
Default running time: O( n )
Returns True
if the sequence is empty and False
otherwise.
null <x0,...,xn-1> = (n==0)
Axioms:
null xs = (size xs == 0)
This function is always unambiguous.
Default running time: O( 1 )
Returns the length of a sequence.
size <x0,...,xn-1> = n
Axioms:
size empty = 0
size (lcons x xs) = 1 + size xs
This function is always unambiguous.
Default running time: O( n )
Convert a sequence to a list.
toList <x0,...,xn-1> = [x0,...,xn-1]
Axioms:
toList empty = []
toList (lcons x xs) = x : toList xs
This function is always unambiguous.
Default running time: O( n )
concat :: s (s a) -> s aSource
Flatten a sequence of sequences into a simple sequence.
concat xss = foldr append empty xss
Axioms:
concat xss = foldr append empty xss
This function is always unambiguous.
Default running time: O( n + m )
where n
is the length of the input sequence and m
is
length of the output sequence.
Reverse the order of a sequence
reverse <x0,...,xn-1> = <xn-1,...,x0>
Axioms:
reverse empty = empty
reverse (lcons x xs) = rcons x (reverse xs)
This function is always unambiguous.
Default running time: O( n )
reverseOnto :: s a -> s a -> s aSource
Reverse a sequence onto the front of another sequence.
reverseOnto <x0,...,xn-1> <y0,...,ym-1> = <xn-1,...,x0,y0,...,ym-1>
Axioms:
reverseOnto xs ys = append (reverse xs) ys
This function is always unambiguous.
Default running time: O( n1 )
fold :: (a -> b -> b) -> b -> s a -> bSource
Combine all the elements of a sequence into a single value,
given a combining function and an initial value. The order
in which the elements are applied to the combining function
is unspecified. fold
is one of the few ambiguous sequence
functions.
Axioms:
fold f c empty = c
f is fold-commutative ==> fold f = foldr f = foldl f
fold f
is unambiguous iff f
is fold-commutative.
Default running type: O( t * n )
where t
is the running tome of f
.
fold' :: (a -> b -> b) -> b -> s a -> bSource
A strict variant of fold
. fold'
is one of the few ambiguous
sequence functions.
Axioms:
forall a. f a _|_ = _|_ ==> fold f x xs = fold' f x xs
fold f
is unambiguous iff f
is fold-commutative.
Default running type: O( t * n )
where t
is the running tome of f
.
fold1 :: (a -> a -> a) -> s a -> aSource
Combine all the elements of a non-empty sequence into a single value, given a combining function. Signals an error if the sequence is empty.
Axioms:
f is fold-commutative ==> fold1 f = foldr1 f = foldl1 f
fold1 f
is unambiguous iff f
is fold-commutative.
Default running type: O( t * n )
where t
is the running tome of f
.
fold1' :: (a -> a -> a) -> s a -> aSource
A strict variant of fold1
.
Axioms:
forall a. f a _|_ = _|_ ==> fold1' f xs = fold1 f xs
fold1' f
is unambiguous iff f
is fold-commutative.
Default running time: O( t * n )
where t
is the running time of f
foldr :: (a -> b -> b) -> b -> s a -> bSource
Combine all the elements of a sequence into a single value, given a combining function and an initial value. The function is applied with right nesting.
foldr (%) c <x0,...,xn-1> = x0 % (x1 % ( ... % (xn-1 % c)))
Axioms:
foldr f c empty = c
foldr f c (lcons x xs) = f x (foldr f c xs)
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of f
foldr' :: (a -> b -> b) -> b -> s a -> bSource
Strict variant of foldr
.
Axioms:
forall a. f a _|_ = _|_ ==> foldr f x xs = foldr' f x xs
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of f
foldl :: (b -> a -> b) -> b -> s a -> bSource
Combine all the elements of a sequence into a single value, given a combining function and an initial value. The function is applied with left nesting.
foldl (%) c <x0,...,xn-1> = (((c % x0) % x1) % ... ) % xn-1
Axioms:
foldl f c empty = c
foldl f c (lcons x xs) = foldl f (f c x) xs
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of f
foldl' :: (b -> a -> b) -> b -> s a -> bSource
Strict variant of foldl
.
Axioms:
- forall a. f _|_ a = _|_ ==> foldl f z xs = foldl' f z xs
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of f
foldr1 :: (a -> a -> a) -> s a -> aSource
Combine all the elements of a non-empty sequence into a single value, given a combining function. The function is applied with right nesting. Signals an error if the sequence is empty.
foldr1 (+) <x0,...,xn-1> | n==0 = error "ModuleName.foldr1: empty sequence" | n>0 = x0 + (x1 + ... + xn-1)
Axioms:
foldr1 f empty = undefined
foldr1 f (rcons x xs) = foldr f x xs
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of f
foldr1' :: (a -> a -> a) -> s a -> aSource
Strict variant of foldr1
.
Axioms:
- forall a. f a _|_ = _|_ ==> foldr1 f xs = foldr1' f xs
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of f
foldl1 :: (a -> a -> a) -> s a -> aSource
Combine all the elements of a non-empty sequence into a single value, given a combining function. The function is applied with left nesting. Signals an error if the sequence is empty.
foldl1 (+) <x0,...,xn-1> | n==0 = error "ModuleName.foldl1: empty sequence" | n>0 = (x0 + x1) + ... + xn-1
Axioms:
foldl1 f empty = undefined
foldl1 f (lcons x xs) = foldl f x xs
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of f
foldl1' :: (a -> a -> a) -> s a -> aSource
Strict variant of foldl1
.
Axioms:
- forall a. f _|_ a = _|_ ==> foldl1 f xs = foldl1' f xs
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of f
reducer :: (a -> a -> a) -> a -> s a -> aSource
See reduce1
for additional notes.
reducer f x xs = reduce1 f (cons x xs)
Axioms:
-
reducer f c xs = foldr f c xs
for associativef
reducer f
is unambiguous iff f
is an associative function.
Default running time: O( t * n )
where t
is the running time of f
reducer' :: (a -> a -> a) -> a -> s a -> aSource
Strict variant of reducer
.
See reduce1
for additional notes.
Axioms:
forall a. f a _|_ = _|_ && forall a. f _|_ a = _|_ ==> reducer f x xs = reducer' f x xs
reducer' f
is unambiguous iff f
is an associative function.
Default running time: O( t * n )
where t
is the running time of f
reducel :: (a -> a -> a) -> a -> s a -> aSource
See reduce1
for additional notes.
reducel f x xs = reduce1 f (rcons x xs)
Axioms:
-
reducel f c xs = foldl f c xs
for associativef
reducel f
is unambiguous iff f
is an associative function.
Default running time: O( t * n )
where t
is the running time of f
reducel' :: (a -> a -> a) -> a -> s a -> aSource
Strict variant of reducel
.
See reduce1
for additional notes.
Axioms:
forall a. f a _|_ = _|_ && forall a. f _|_ a = _|_ ==> reducel f x xs = reducel' f x xs
reducel' f
is unambiguous iff f
is an associative function.
Default running time: O( t * n )
where t
is the running time of f
reduce1 :: (a -> a -> a) -> s a -> aSource
A reduce is similar to a fold, but combines elements in a balanced fashion. The combining function should usually be associative. If the combining function is associative, the various reduce functions yield the same results as the corresponding folds.
What is meant by "in a balanced fashion"? We mean that
reduce1 (%) <x0,x1,...,xn-1>
equals some complete parenthesization of
x0 % x1 % ... % xn-1
such that the nesting depth of parentheses
is O( log n )
. The precise shape of this parenthesization is
unspecified.
reduce1 f <x> = x reduce1 f <x0,...,xn-1> = f (reduce1 f <x0,...,xi>) (reduce1 f <xi+1,...,xn-1>)
for some i
such that 0 <= i && i < n-1
Although the exact value of i is unspecified it tends toward n/2
so that the depth of calls to f
is at most logarithmic.
Note that reduce
* are some of the only sequence operations for which
different implementations are permitted to yield different answers. Also
note that a single implementation may choose different parenthisizations
for different sequences, even if they are the same length. This will
typically happen when the sequences were constructed differently.
The canonical applications of the reduce functions are algorithms like merge sort where:
mergesort xs = reducer merge empty (map singleton xs)
Axioms:
reduce1 f empty = undefined
-
reduce1 f xs = foldr1 f xs = foldl1 f xs
for associativef
reduce1 f
is unambiguous iff f
is an associative function.
Default running time: O( t * n )
where t
is the running time of f
reduce1' :: (a -> a -> a) -> s a -> aSource
Strict variant of reduce1
.
Axioms:
forall a. f a _|_ = _|_ && forall a. f _|_ a = _|_ ==> reduce1 f xs = reduce1' f xs
reduce1' f
is unambiguous iff f
is an associative function.
Default running time: O( t * n )
where t
is the running time of f
take :: Int -> s a -> s aSource
Extract a prefix of length i
from the sequence. Return
empty
if i
is negative, or the entire sequence if i
is too large.
take i xs = fst (splitAt i xs)
Axioms:
i < 0 ==> take i xs = empty
i > size xs ==> take i xs = xs
size xs == i ==> take i (append xs ys) = xs
This function is always unambiguous.
Default running time: O( i )
drop :: Int -> s a -> s aSource
Delete a prefix of length i
from a sequence. Return
the entire sequence if i
is negative, or empty
if
i
is too large.
drop i xs = snd (splitAt i xs)
Axioms:
i < 0 ==> drop i xs = xs
i > size xs ==> drop i xs = empty
size xs == i ==> drop i (append xs ys) = ys
This function is always unambiguous.
Default running time: O( i )
splitAt :: Int -> s a -> (s a, s a)Source
Split a sequence into a prefix of length i
and the remaining sequence. Behaves the same
as the corresponding calls to take
and drop
if i
is negative or too large.
splitAt i xs | i < 0 = (<> , <x0,...,xn-1>) | i < n = (<x0,...,xi-1>, <xi,...,xn-1>) | i >= n = (<x0,...,xn-1>, <> )
Axioms:
splitAt i xs = (take i xs,drop i xs)
This function is always unambiguous.
Default running time: O( i )
subseq :: Int -> Int -> s a -> s aSource
Extract a subsequence from a sequence. The integer
arguments are "start index" and "length" NOT
"start index" and "end index". Behaves the same
as the corresponding calls to take
and drop
if the
start index or length are negative or too large.
subseq i len xs = take len (drop i xs)
Axioms:
subseq i len xs = take len (drop i xs)
This function is always unambiguous.
Default running time: O( i + len )
filter :: (a -> Bool) -> s a -> s aSource
Extract the elements of a sequence that satisfy the given predicate, retaining the relative ordering of elements from the original sequence.
filter p xs = foldr pcons empty xs where pcons x xs = if p x then cons x xs else xs
Axioms:
filter p empty = empty
filter p (lcons x xs) = if p x then lcons x (filter p xs) else filter p xs
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of p
partition :: (a -> Bool) -> s a -> (s a, s a)Source
Separate the elements of a sequence into those that satisfy the given predicate and those that do not, retaining the relative ordering of elements from the original sequence.
partition p xs = (filter p xs, filter (not . p) xs)
Axioms:
partition p xs = (filter p xs, filter (not . p) xs)
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of p
takeWhile :: (a -> Bool) -> s a -> s aSource
Extract the maximal prefix of elements satisfying the given predicate.
takeWhile p xs = fst (splitWhile p xs)
Axioms:
takeWhile p empty = empty
takeWhile p (lcons x xs) = if p x then lcons x (takeWhile p xs) else empty
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of p
dropWhile :: (a -> Bool) -> s a -> s aSource
Delete the maximal prefix of elements satisfying the given predicate.
dropWhile p xs = snd (splitWhile p xs)
Axioms:
dropWhile p empty = empty
dropWhile p (lcons x xs) = if p x then dropWhile p xs else lcons x xs
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of p
splitWhile :: (a -> Bool) -> s a -> (s a, s a)Source
Split a sequence into the maximal prefix of elements satisfying the given predicate, and the remaining sequence.
splitWhile p <x0,...,xn-1> = (<x0,...,xi-1>, <xi,...,xn-1>) where i = min j such that p xj (or n if no such j)
Axioms:
splitWhile p xs = (takeWhile p xs,dropWhile p xs)
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of p
inBounds :: Int -> s a -> BoolSource
Test whether an index is valid for the given sequence. All indexes are 0 based.
inBounds i <x0,...,xn-1> = (0 <= i && i < n)
Axioms:
inBounds i xs = (0 <= i && i < size xs)
This function is always unambiguous.
Default running time: O( i )
lookup :: Int -> s a -> aSource
Return the element at the given index. All indexes are 0 based. Signals error if the index out of bounds.
lookup i xs@<x0,...,xn-1> | inBounds i xs = xi | otherwise = error "ModuleName.lookup: index out of bounds"
Axioms:
not (inBounds i xs) ==> lookup i xs = undefined
size xs == i ==> lookup i (append xs (lcons x ys)) = x
This function is always unambiguous.
Default running time: O( i )
lookupM :: Monad m => Int -> s a -> m aSource
Return the element at the given index. All indexes are 0 based.
Calls fail
if the index is out of bounds.
lookupM i xs@<x0,...,xn-1> | inBounds i xs = Just xi | otherwise = Nothing
Axioms:
not (inBounds i xs) ==> lookupM i xs = fail
size xs == i ==> lookupM i (append xs (lcons x ys)) = return x
This function is always unambiguous.
Default running time: O( i )
lookupWithDefault :: a -> Int -> s a -> aSource
Return the element at the given index, or the default argument if the index is out of bounds. All indexes are 0 based.
lookupWithDefault d i xs@<x0,...,xn-1> | inBounds i xs = xi | otherwise = d
Axioms:
not (inBounds i xs) ==> lookupWithDefault d i xs = d
size xs == i ==> lookupWithDefault d i (append xs (lcons x ys)) = x
This function is always unambiguous.
Default running time: O( i )
update :: Int -> a -> s a -> s aSource
Replace the element at the given index, or return the original sequence if the index is out of bounds. All indexes are 0 based.
update i y xs@<x0,...,xn-1> | inBounds i xs = <x0,...xi-1,y,xi+1,...,xn-1> | otherwise = xs
Axioms:
not (inBounds i xs) ==> update i y xs = xs
size xs == i ==> update i y (append xs (lcons x ys)) = append xs (lcons y ys)
This function is always unambiguous.
Default running time: O( i )
adjust :: (a -> a) -> Int -> s a -> s aSource
Apply a function to the element at the given index, or return the original sequence if the index is out of bounds. All indexes are 0 based.
adjust f i xs@<x0,...,xn-1> | inBounds i xs = <x0,...xi-1,f xi,xi+1,...,xn-1> | otherwise = xs
Axioms:
not (inBounds i xs) ==> adjust f i xs = xs
size xs == i ==> adjust f i (append xs (lcons x ys)) = append xs (cons (f x) ys)
This function is always unambiguous.
Default running time: O( i + t )
where t
is the running time of f
mapWithIndex :: (Int -> a -> b) -> s a -> s bSource
Like map
, but include the index with each element.
All indexes are 0 based.
mapWithIndex f <x0,...,xn-1> = <f 0 x0,...,f (n-1) xn-1>
Axioms:
mapWithIndex f empty = empty
mapWithIndex f (rcons x xs) = rcons (f (size xs) x) (mapWithIndex f xs)
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of f
foldrWithIndex :: (Int -> a -> b -> b) -> b -> s a -> bSource
Like foldr
, but include the index with each element.
All indexes are 0 based.
foldrWithIndex f c <x0,...,xn-1> = f 0 x0 (f 1 x1 (... (f (n-1) xn-1 c)))
Axioms:
foldrWithIndex f c empty = c
foldrWithIndex f c (rcons x xs) = foldrWithIndex f (f (size xs) x c) xs
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of f
foldrWithIndex' :: (Int -> a -> b -> b) -> b -> s a -> bSource
Strict variant of foldrWithIndex
.
Axioms:
forall i a. f i a _|_ = _|_ ==> foldrWithIndex f x xs = foldrWithIndex' f x xs
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of f
foldlWithIndex :: (b -> Int -> a -> b) -> b -> s a -> bSource
Like foldl
, but include the index with each element.
All indexes are 0 based.
foldlWithIndex f c <x0,...,xn-1> = f (...(f (f c 0 x0) 1 x1)...) (n-1) xn-1)
Axioms:
foldlWithIndex f c empty = c
foldlWithIndex f c (rcons x xs) = f (foldlWithIndex f c xs) (size xs) x
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of f
foldlWithIndex' :: (b -> Int -> a -> b) -> b -> s a -> bSource
Strict variant of foldlWithIndex
.
Axioms:
forall i a. f _|_ i a = _|_ ==> foldlWithIndex f x xs = foldlWithIndex' f x xs
This function is always unambiguous.
Default running time: O( t * n )
where t
is the running time of f
zip :: s a -> s b -> s (a, b)Source
Combine two sequences into a sequence of pairs. If the sequences are different lengths, the excess elements of the longer sequence is discarded.
zip <x0,...,xn-1> <y0,...,ym-1> = <(x0,y0),...,(xj-1,yj-1)> where j = min {n,m}
Axioms:
zip xs ys = zipWith (,) xs ys
This function is always unambiguous.
Default running time: O( min( n1, n2 ) )
zip3 :: s a -> s b -> s c -> s (a, b, c)Source
Like zip
, but combines three sequences into triples.
zip3 <x0,...,xn-1> <y0,...,ym-1> <z0,...,zk-1> = <(x0,y0,z0),...,(xj-1,yj-1,zj-1)> where j = min {n,m,k}
Axioms:
zip3 xs ys zs = zipWith3 (,,) xs ys zs
This function is always unambiguous.
Default running time: O( min( n1, n2, n3 ) )
zipWith :: (a -> b -> c) -> s a -> s b -> s cSource
Combine two sequences into a single sequence by mapping a combining function across corresponding elements. If the sequences are of different lengths, the excess elements of the longer sequence are discarded.
zipWith f xs ys = map (uncurry f) (zip xs ys)
Axioms:
zipWith f (lcons x xs) (lcons y ys) = lcons (f x y) (zipWith f xs ys)
(null xs || null ys) ==> zipWith xs ys = empty
This function is always unambiguous.
Default running time: O( t * min( n1, n2 ) )
where t
is the running time of f
zipWith3 :: (a -> b -> c -> d) -> s a -> s b -> s c -> s dSource
Like zipWith
but for a three-place function and three
sequences.
zipWith3 f xs ys zs = map (uncurry f) (zip3 xs ys zs)
Axioms:
zipWith3 (lcons x xs) (lcons y ys) (lcons z zs) = lcons (f x y z) (zipWith3 f xs ys zs)
This function is always unambiguous.
Default running time: O( t * min( n1, n2, n3 ) )
where t
is the running time of f
unzip :: s (a, b) -> (s a, s b)Source
Transpose a sequence of pairs into a pair of sequences.
unzip xs = (map fst xs, map snd xs)
Axioms:
unzip xys = unzipWith fst snd xys
This function is always unambiguous.
Default running time: O( n )
unzip3 :: s (a, b, c) -> (s a, s b, s c)Source
Transpose a sequence of triples into a triple of sequences
unzip3 xs = (map fst3 xs, map snd3 xs, map thd3 xs) where fst3 (x,y,z) = x snd3 (x,y,z) = y thd3 (x,y,z) = z
Axioms:
unzip3 xyzs = unzipWith3 fst3 snd3 thd3 xyzs
This function is always unambiguous.
Default running time: O( n )
unzipWith :: (a -> b) -> (a -> c) -> s a -> (s b, s c)Source
Map two functions across every element of a sequence, yielding a pair of sequences
unzipWith f g xs = (map f xs, map g xs)
Axioms:
unzipWith f g xs = (map f xs, map g xs)
This function is always unambiguous.
Default running time: O( t * n )
where t
is the maximum running time
of f
and g
unzipWith3 :: (a -> b) -> (a -> c) -> (a -> d) -> s a -> (s b, s c, s d)Source
Map three functions across every element of a sequence, yielding a triple of sequences.
unzipWith3 f g h xs = (map f xs, map g xs, map h xs)
Axioms:
unzipWith3 f g h xs = (map f xs,map g xs,map h xs)
This function is always unambiguous.
Default running time: O( t * n )
where t
is the maximum running time
of f
, g
, and h
Semanticly, this function is a partial identity function. If the
datastructure is infinite in size or contains exceptions or non-termination
in the structure itself, then strict
will result in bottom. Operationally,
this function walks the datastructure forcing any closures. Elements contained
in the sequence are not forced.
Axioms:
-
strict xs = xs
ORstrict xs = _|_
This function is always unambiguous.
Default running time: O( n )
strictWith :: (a -> b) -> s a -> s aSource
Similar to strict
, this function walks the datastructure forcing closures.
However, strictWith
will additionally apply the given function to the
sequence elements, force the result using seq
, and then ignore it.
This function can be used to perform various levels of forcing on the
sequence elements. In particular:
strictWith id xs
will force the spine of the datastructure and reduce each element to WHNF.
Axioms:
- forall
f :: a -> b
,strictWith f xs = xs
ORstrictWith f xs = _|_
This function is always unambiguous.
Default running time: unbounded (forcing element closures can take arbitrairly long)
structuralInvariant :: s a -> BoolSource
A method to facilitate unit testing. Returns True
if the structural
invariants of the implementation hold for the given sequence. If
this function returns False
, it represents a bug in the implementation.
instanceName :: s a -> StringSource
The name of the module implementing s.
Sequence [] |