Chapter 5 Sequences

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 and Show, although this is not enforced (in fact, is not enforceable in any reasonable way).

We follow the naming convention that every module implementing sequences defines a type constructor named Seq.

Figure 5.1 summarizes all the methods on sequences. We next describe each of these methods in more detail.

Sequence Methods

Constructors:

empty, single, cons, snoc, append, fromList, copy, tabulate

Destructors:

lview, lhead, ltail, rview, rhead, rtail

Observers:

null, size, toList

Concat and reverse:

concat, reverse, reverseOnto

Maps and folds:

map, concatMap, foldr, foldl, foldr1, foldl1, reducer, reducel, reduce1

Subsequences:

take, drop, splitAt, subseq

Predicate-based operations:

filter, partition, takeWhile, dropWhile, splitWhile

Index-based operations:

inBounds, lookup, lookupM, lookupWithDefault, update, adjust,
mapWithIndex, foldrWithIndex, foldlWithIndex

Zips and unzips:

zip, zip3, zipWith, zipWith3, unzip, unzip3, unzipWith, unzipWith3

Figure 5.1: Summary of methods for the Sequence class.

5.1 Constructors

empty :: seq a

The empty sequence.

single :: a ® seq a

Create a singleton sequence.

Axioms:

single x º cons x empty º snoc empty x

Default running time: O(1)

cons :: a ® seq a ® seq a

Add a new element to the front/left of a sequence.

Axioms:

cons x xs º append (single x) xs

Default running time: O(1)

snoc :: seq a ® a ® seq a

Add a new element to the rear/right of a sequence.

Axioms:

snoc xs x º append xs (single x)

Default running time: O(n)

append :: seq a ® seq a ® seq a

Append two sequences, with the first argument on the left and the second argument on the right.

Axioms:

append xs ys º foldr cons ys xs

Default running time: O(n₁)

fromList :: [a] ® seq a

Convert a list to a sequence.

Axioms:

fromList xs º foldr cons empty xs

Default running time: O(n)

copy :: Int ® a ® seq a

Create a sequence containing n copies of the given element. Return empty if n<0.

Axioms:

n > 0-- copy n x º cons x (copy (n-1) x)

n <= 0 -- copy n x º empty

Default running time: O(n)

tabulate :: Int ® (Int ® a) ® seq a

Create a sequence containing the results of applying the given function to the integers 0... n-1. Return empty if n<0.

Axioms:

n > 0-- tabulate n f º map f (fromList [0..n-1])

n <= 0 -- tabulate n f º empty

Default running time: O(nt), where t is the running time of f

5.2 Destructors

lview :: seq a ® Maybe2 a (seq a)

Separate a sequence into its first element and the remaining sequence. Return Nothing2 if the sequence is empty.

Axioms:

lview empty º Nothing2

lview (cons x xs) º Just2 x xs

Default running time: O(1)

lhead :: seq a ® a

Return the first element of the sequence. Signal an error if the sequence is empty.

Axioms:

lhead empty º error

lhead (cons x xs) º x

Default running time: O(1)

ltail :: seq a ® seq a

Delete the first element of the sequence. Return empty if the sequence is already empty.

Axioms:

ltail empty º empty

ltail (cons x xs) º xs

Default running time: O(1)

rview :: seq a ® Maybe2 (seq a) a

Separate a sequence into its last element and the remaining sequence. Return Nothing2 if the sequence is empty.

Axioms:

rview empty º Nothing2

rview (snoc xs x) º Just2 xs x

Default running time: O(n)

rhead :: seq a ® a

Return the first element of the sequence. Signal an error if the sequence is empty.

Axioms:

rhead empty º error

rhead (snoc xs x) º x

Default running time: O(n)

rtail :: seq a ® seq a

Delete the first element of the sequence. Return empty if the sequence is already empty.

Axioms:

rtail empty º empty

rtail (snoc xs x) º xs

Default running time: O(n)

5.3 Observers

null :: seq a ® Bool

Return True if the sequence is empty and False otherwise.

Axioms:

null xs º (size xs == 0)

Default running time: O(1)

size :: seq a ® Int

Return the length of the sequence.

Axioms:

size empty º 0

size (cons x xs) º 1 + size xs

Default running time: O(n)

toList :: seq a ® [a]

Convert a sequence to a list.

Axioms:

toList empty º []

toList (cons x xs) º x : toList xs

Default running time: O(n)

5.4 Concat and reverse

concat :: seq (seq a) ® seq a

Flatten a sequence of sequences into a simple sequence.

Axioms:

concat xss º foldr append empty xss

Default running time: O(n + m), where n is the length of the input sequence and m is the length of the output sequence (usually n < m, but if the input sequence contains many empties, then n may be larger)

reverse :: seq a ® seq a

Reverse the order of a sequence.

Axioms:

reverse empty º empty

reverse (cons x xs) º snoc (reverse xs) x

Default running time: O(n)

reverseOnto :: seq a ® seq a ® seq a

Reverse a sequence onto the front of another sequence.

Axioms:

reverseOnto xs ys º append (reverse xs) ys

Default running time: O(n₁)

5.5 Maps and folds

map :: (a ® b) ® seq a ® seq b

Return the result of applying a function to every element of a sequence.

Axioms:

map f empty º empty

map f (cons x xs) º cons (f x) (map f xs)

Default running time: O(nt), where t is the running time of f

concatMap :: (a ® seq b) ® seq a ® seq b

Apply a sequence-producing function to every element of a sequence and flatten the result. Note that concatMap is the ``bind'' operation of the sequence monad (but with the arguments in the opposite order).

Axioms:

concatMap f xs º concat (map f xs)

Default running time: O(nt + 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

foldr :: (a ® b ® b) ® b ® seq a ® b

Combine all the elements of a sequence into a single value, given a right-associative combining function and an initial value. Note that

foldr (Å) e [x₀,x₁,...,x_n-1] º x₀ Å (x₁ Å ··· Å (x_n-1 Å e))

Axioms:

foldr f c empty º c

foldr f c (cons x xs) = f x (foldr f c xs)

Default running time: O(nt), where t is the running time of f

foldl :: (b ® a ® b) ® b ® seq a ® b

Combine all the elements of a sequence into a single value, given a left-associative combining function and an initial value. Note that

foldl (Å) e [x₀,x₁,...,x_n-1] º ((e Å x₀) Å x₁) Å ··· Å x_n-1

Axioms:

foldl f c empty º c

foldl f c (cons x xs) = foldl f (f c x) xs

Default running time: O(nt), where t is the running time of f

foldr1 :: (a ® a ® a) ® seq a ® seq a

Combine all the elements of a non-empty sequence into a single value, given a right-associative combining function. Signal an error if the sequence is empty.

Axioms:

foldr1 f empty º error

foldr1 f (snoc xs x) º foldr f x xs

Default running time: O(nt), where t is the running time of f

foldl1 :: (a ® a ® a) ® seq a ® seq a

Combine all the elements of a non-empty sequence into a single value, given a left-associative combining function. Signal an error if the sequence is empty.

Axioms:

foldl1 f empty º error

foldl1 f (cons x xs) º foldl f x xs

Default running time: O(nt), where t is the running time of f

reducer :: (a ® a ® a) ® a ® seq a ®seq a reducel :: (a® a ® a) ® a ® seq a ®seq a reduce1 :: (a® a ® a) ® seq a ® seq a

Like the various folds, but combine the elements in a balanced fashion rather than linearly from right-to-left or left-to-right. Usually, the combining function is associative, in which case the various reduces yield the same answers as the corresponding folds (albeit perhaps more efficiently). reduce1 signals an error if the sequence is empty.

What do I mean by ``in a balanced fashion''? I mean that reduce1 (Å) [x₀,...,x_n-1] equals some complete parenthesization of x₀ Å ··· Å x_n-1, such that the nesting depth of parentheses is O(log n). The precise shape of this parenthesization is unspecified. For example, the following are all typical answers for reduce1 (Å) [a,b,c,d,e,f]:

(a Å b) Å ((c Å d) Å (e Å f))

((a Å b) Å (c Å d)) Å (e Å f)

(a Å (b Å c)) Å (d Å (e Å f))

((a Å b) Å c) Å ((d Å e) Å f)

Note that these are the only sequence operations for which different implementations are permitted to yield different answers.¹ Also note that a single implementation may choose different parenthesizations for different sequences, even if they are the same length. This will typically happen when the lists were constructed differently (e.g., one using cons and the other using snoc).

The canonical applications of the reduce functions are algorithms like mergesort, where

    mergesort :: (Ord a,Sequence s) => s a -> s a
    mergesort xs = reducer merge empty (map single xs)

Axioms:

reduce1 (Å) empty º error

" x,y,z. x Å (y Å z) º (x Å y) Å z --

reduce1 (Å) xs º foldr1 (Å) xsº foldl1 (Å) xs

reducer (Å) c xs º foldr (Å) c xs

reducel (Å) c xs º foldl (Å) c xs

Default running time: O(nt), where t is the running time of f

5.6 Subsequences

take :: Int ® seq a ® seq a

Extract a prefix of length i from a sequence. Return empty if i is negative, or the entire sequence if i is too large.

Axioms:

i < 0 -- take i xs º empty

i > size xs -- take i xs º xs

size xs == i -- take i (append xs ys) º xs

Default running time: O(i)

drop :: Int ® seq a ® seq a

Delete a prefix of length i from a sequence. Return the entire sequence if i is negative, or empty if i is too large.

Axioms:

i < 0 -- drop i xs º xs

i > size xs -- drop i xs º empty

size xs == i -- drop i (append xs ys) º ys

Default running time: O(i)

splitAt :: Int ® seq a ® (seq a, seq a)

Split a sequence into a prefix of length i and the remaining sequence. Behaves the same as the corresponding calls to take and drop is i is negative or too large.

Axioms:

splitAt i xs º (take i xs, drop i xs)

Default running time: O(i)

subseq :: Int ® Int ® seq a ® seq a

Extract a subsequence from a sequence. The integer arguments are ``start index'' and ``length'' rather than ``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.

Axioms:

subseq i len xs º take len (drop i xs)

Default running time: O(i + len)

5.7 Predicate-based operations

filter :: (a ® Bool) ® seq a ® seq a

Extract the elements of a sequence that satisfy the given predicate, retaining the relative ordering of elements from the original sequence.

Axioms:

filter p empty º empty

filter p (cons x xs) º if p x then cons x (filter p xs) else filter p xs

Default running time: O(nt), where t is the running time of p

partition :: (a ® Bool) ® seq a ® (seq a, seq a)

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.

Axioms:

partition p xs º (filter p xs, filter (not . p) xs)

Default running time: O(nt), where t is the running time of p

takeWhile :: (a ® Bool) ® seq a ® seq a

Extract the maximal prefix of elements satisfying the given predicate.

Axioms:

takeWhile p empty º empty

takeWhile p (cons x xs) º if p x then cons x (takeWhile p xs) else empty

Default running time: O(nt), where t is the running time of p

dropWhile :: (a ® Bool) ® seq a ® seq a

Delete the maximal prefix of elements satisfying the given predicate.

Axioms:

dropWhile p empty º empty

dropWhile p (cons x xs) º if p x then dropWhile p xs else cons x xs

Default running time: O(nt), where t is the running time of p

splitWhile :: (a ® Bool) ® seq a ® seq a

Split a sequence into the maximal prefix of elements satisfying the given predicate, and the remaining sequence.

Axioms:

splitWhile p xs º (takeWhile p xs, dropWhile p xs)

Default running time: O(nt), where t is the running time of p

5.8 Index-based operations

The following operations all assume zero-based indexing.

inBounds :: seq a ® Int ® Bool

Test whether an index is valid for the given sequence.

Axioms:

inBounds xs i º (0 <= i && i < size xs)

Default running time: O(i)

lookup :: seq a ® Int ® a

Return the element at the given index. Signal an error if the index is out of bounds.

Axioms:

not (inBounds xs i) -- lookup xs i º error

size xs == i -- lookup (append xs (cons x ys)) i º x

Default running time: O(i)

lookupM :: seq a ® Int ® Maybe a

Return Just of the element at the given index, or Nothing if the index is out of bounds.

Axioms:

not (inBounds xs i) -- lookupM xs i º Nothing

size xs == i -- lookupM (append xs (cons x ys)) i º Just x

Default running time: O(i)

lookupWithDefault :: a ® seq a ® Int ® a

Return the element at the given index, or the default argument if the index is out of bounds.

Axioms:

not (inBounds xs i) -- lookupWithDefault d xs i º d

size xs == i -- lookupWithDefault d (append xs (cons x ys)) i º x

Default running time: O(i)

update :: Int ® a ® seq a ® seq a

Replace the element at the given index, or return the original sequence if the index is out of bounds.

Axioms:

not (inBounds xs i) -- update i y xs º xs

size xs == i -- update i y (append xs (cons x ys)) º append xs (cons y ys)

Default running time: O(i)

adjust :: (a ® a) ® Int ® seq a ® seq a

Apply a function to the element at the given index, or return the original sequence if the index is out of bounds.

Axioms:

not (inBounds xs i) -- adjust f i xs º xs

size xs == i -- adjust f i (append xs (cons x ys)) º append xs (cons (f x) ys)

Default running time: O(i + t), where t is the running time of f

mapWithIndex :: (Int ® a ® b) ® seq a ® seq b

Like map, but include the index with each element.

Axioms:

mapWithIndex f empty º empty

mapWithIndex f (snoc xs x) º snoc (mapWithIndex f xs) (f (size xs) x)

Default running time: O(nt), where t is the running time of f

foldrWithIndex :: (Int ® a ® b ® b) ® b ® seq a ® b

Like foldr, but include the index with each element.

Axioms:

foldrWithIndex f c empty º c

foldrWithIndex f c (snoc xs x) º foldrWithIndex f (f (size xs) x c) xs

Default running time: O(nt), where t is the running time of f

foldlWithIndex :: (b ® Int ® a ® b) ® b ® seq a ® b

Like foldl, but include the index with each element.

Axioms:

foldlWithIndex f c empty º c

foldlWithIndex f c (snoc xs x) º f (foldlWithIndex f c xs) (size xs) x

Default running time: O(nt), where t is the running time of f

5.9 Zips and unzips

zip :: seq a ® seq b ®seq (a,b) zip3 :: seq a® seq b ® seq c ® seq (a,b,c)

Combine two (or three) sequences into a sequence of pairs (or triples). If the sequences are of different lengths, the excess elements of the longer sequence (or sequences) are discarded.

Axioms:

zip xs ys º zipWith (l x y ® (x,y)) xs ys

zip3 xs ys zs º zipWith3 (l x y z ® (x,y,z)) xs ys zs

Default running time: O(min {n₁,n₂}), O(min {n₁,n₂,n₃})

zipWith :: (a ® b ® c) ® seq a ® seq b ®seq c zipWith3 :: (a® b ® c ® d) ® seq a ® seq b ® seq c ® seq d

Combine two (or three) 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 (or sequences) are discarded.

Axioms:

zipWith f (cons x xs) (cons y ys) º cons (f x y) (zipWith f xs ys)

(null xs Ú null ys) -- zipWith f xs ys º empty

zipWith3 f (cons x xs) (cons y ys) (cons z zs) º cons (f x y z) (zipWith3 f xs ys zs)

(null xs Ú null ys Ú null zs) -- zipWith3 f xs ys zs º empty

Default running time: O(t · min {n₁,n₂}), O(t · min {n₁,n₂,n₃}), where t is the running time of f

unzip :: seq (a,b) ®(seq a, seq b) unzip3 :: seq (a,b,c)® (seq a, seq b, seq c)

Transpose a sequence of pairs (or triples) into a pair (or triple) of sequences.

Axioms:

unzip xys º (map fst xys, map snd xys)

unzip3 xyzs º (map fst3 xyzs, map snd3 xyzs, map thd3 xyzs)

Default running time: O(n)

unzipWith :: (a ® b) ® (a ® c) ® seq a ®(seq b, seq c) unzipWith3 :: (a® b) ® (a ® c) ® (a ® d) ® seq a ® (seq b, seq c, seq d)

Map two (or three) functions across every element of a sequence, yielding a pair (or triple) of sequences.

Axioms:

unzipWith f g xs º (map f xs, map g xs)

unzipWith3 f g h xs º (map f xs, map g xs, map h xs)

Default running time: O(nt), where t is the maximum running time of f, g, and h

5.10 Implementations

The following implementations are available or planned. I list with each implementation the major operations whose running times differ from the default (either better or worse).

Available:

ListSeq: Ordinary lists.
SimpleQueue: Burton, IPL'82.
O(1) snoc.
O(1) lview/ltail if single-threaded, O(n) otherwise.
BankersQueue: Okasaki, JFP'95.
O(1) snoc.
MyersStack: Myers, IPL'93.
O(log n) lookup.
RandList: Okasaki, FPCA'95.
O(log n) lookup, update.
BinaryRandList: Okasaki, PFDS (Chapter 10.1.2).
O(log n) lookup, update.
JoinList:
O(1) snoc/append.
O(n) lview/ltail/rview/rtail, but O(1) in practice.

Planned:

StrictList: Strict lists.
BootstrappedQueue: Okasaki, PFDS.
O(1) snoc.
SimpleDeque: Hoogerwoord, JFP'92.
O(1) snoc.
O(1) lview/ltail/rview/rtail if single-threaded, O(n) otherwise.
CatenableList: Okasaki, FOCS'95.
O(1) snoc, append.
CatenableDeque: Okasaki, ICFP'97.
O(1) snoc, rview/rhead/rtail, append.
BraunSeq: Hoogerwoord, MPC'92.
O(log n) cons/lview/ltail.
O(log² n) snoc/rview/rhead/rtail.
O(log i) lookup, update.

1: For all the other sequence operations, implementations may differ only in efficiency and strictness/order of evaluation.