lcons :: a -> s a -> s a | Source |
|
Add a new element to the front/left of a sequence
lcons x <x0,...,xn-1> = <x,x0,...,xn-1>
Axioms:
This function is always unambiguous.
Default running time: O( 1 )
|
|
rcons :: a -> s a -> s a | Source |
|
Add a new element to the right/rear of a sequence
rcons x <x0,...,xn-1> = <x0,...,xn-1,x>
Axioms:
This function is always unambiguous.
Default running time: O( n )
|
|
|
Convert a list into a sequence
fromList [x0,...,xn-1] = <x0,...,xn-1>
Axioms:
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:
This function is always unambiguous.
Default running time: O( n )
|
|
|
Separate a sequence into its first (leftmost) element and the
remaining sequence. Calls fail if the sequence is empty.
Axioms:
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 )
|
|
|
Returns the first element of a sequence.
Calls fail if the sequence is empty.
Axioms:
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 )
|
|
|
Delete the first element of the sequence.
Calls fail if the sequence is empty.
Axioms:
This function is always unambiguous.
Default running time: O( 1 )
|
|
|
Separate a sequence into its last (rightmost) element and the
remaining sequence. Calls fail if the sequence is empty.
Axioms:
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 )
|
|
|
Returns the last element of the sequence.
Calls fail if the sequence is empty.
Axioms:
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 )
|
|
|
Delete the last (rightmost) element of the sequence.
Calls fail of the sequence is empty
Axioms:
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:
This function is always unambiguous.
Default running time: O( 1 )
|
|
|
Returns the length of a sequence.
size <x0,...,xn-1> = n
Axioms:
This function is always unambiguous.
Default running time: O( n )
|
|
|
Convert a sequence to a list.
toList <x0,...,xn-1> = [x0,...,xn-1]
Axioms:
This function is always unambiguous.
Default running time: O( n )
|
|
concat :: s (s a) -> s a | Source |
|
Flatten a sequence of sequences into a simple sequence.
concat xss = foldr append empty xss
Axioms:
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:
This function is always unambiguous.
Default running time: O( n )
|
|
reverseOnto :: s a -> s a -> s a | Source |
|
Reverse a sequence onto the front of another sequence.
reverseOnto <x0,...,xn-1> <y0,...,ym-1> = <xn-1,...,x0,y0,...,ym-1>
Axioms:
This function is always unambiguous.
Default running time: O( n1 )
|
|
fold :: (a -> b -> b) -> b -> s a -> b | Source |
|
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 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 -> b | Source |
|
A strict variant of fold. fold' is one of the few ambiguous
sequence functions.
Axioms:
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 -> a | Source |
|
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:
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 -> a | Source |
|
A strict variant of fold1.
Axioms:
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 -> b | Source |
|
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:
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 -> b | Source |
|
Strict variant of foldr.
Axioms:
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 -> b | Source |
|
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:
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 -> b | Source |
|
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 -> a | Source |
|
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:
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 -> a | Source |
|
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 -> a | Source |
|
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:
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 -> a | Source |
|
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 -> a | Source |
|
See reduce1 for additional notes.
reducer f x xs = reduce1 f (cons x xs)
Axioms:
- reducer f c xs = foldr f c xs for associative f
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 -> a | Source |
|
Strict variant of reducer.
See reduce1 for additional notes.
Axioms:
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 -> a | Source |
|
See reduce1 for additional notes.
reducel f x xs = reduce1 f (rcons x xs)
Axioms:
- reducel f c xs = foldl f c xs for associative f
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 -> a | Source |
|
Strict variant of reducel.
See reduce1 for additional notes.
Axioms:
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 -> a | Source |
|
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 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 -> a | Source |
|
Strict variant of reduce1.
Axioms:
reduce1' f is unambiguous iff f is an associative function.
Default running time: O( t * n )
where t is the running time of f
|
|
|
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 )
|
|
|
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:
This function is always unambiguous.
Default running time: O( i )
|
|
|
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:
This function is always unambiguous.
Default running time: O( i )
|
|
|
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:
This function is always unambiguous.
Default running time: O( i + len )
|
|
|
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:
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:
This function is always unambiguous.
Default running time: O( t * n )
where t is the running time of p
|
|
|
Extract the maximal prefix of elements satisfying the
given predicate.
takeWhile p xs = fst (splitWhile p xs)
Axioms:
This function is always unambiguous.
Default running time: O( t * n )
where t is the running time of p
|
|
|
Delete the maximal prefix of elements satisfying the
given predicate.
dropWhile p xs = snd (splitWhile p xs)
Axioms:
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:
This function is always unambiguous.
Default running time: O( t * n )
where t is the running time of p
|
|
|
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:
This function is always unambiguous.
Default running time: O( i )
|
|
|
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:
This function is always unambiguous.
Default running time: O( i )
|
|
|
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:
This function is always unambiguous.
Default running time: O( i )
|
|
lookupWithDefault :: a -> Int -> s a -> a | Source |
|
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:
This function is always unambiguous.
Default running time: O( i )
|
|
|
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:
This function is always unambiguous.
Default running time: O( i )
|
|
adjust :: (a -> a) -> Int -> s a -> s a | Source |
|
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:
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 b | Source |
|
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:
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 -> b | Source |
|
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:
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 -> b | Source |
|
Strict variant of foldrWithIndex.
Axioms:
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 -> b | Source |
|
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:
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 -> b | Source |
|
Strict variant of foldlWithIndex.
Axioms:
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:
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:
This function is always unambiguous.
Default running time: O( min( n1, n2, n3 ) )
|
|
zipWith :: (a -> b -> c) -> s a -> s b -> s c | Source |
|
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:
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 d | Source |
|
Like zipWith but for a three-place function and three
sequences.
zipWith3 f xs ys zs = map (uncurry f) (zip3 xs ys zs)
Axioms:
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:
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:
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:
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:
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 OR strict xs = _|_
This function is always unambiguous.
Default running time: O( n )
|
|
strictWith :: (a -> b) -> s a -> s a | Source |
|
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 OR strictWith f xs = _|_
This function is always unambiguous.
Default running time: unbounded (forcing element closures can take arbitrairly long)
|
|
|
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.
|
|
|
The name of the module implementing s.
|