# Programming with Sequences

A sequence is a series of objects. At any point, you may ask whether a sequence is empty, and if it is not empty you may retrieve the next object. Many datastructures can represent their items as a sequence. For example, a sequence for representing the items in an array could begin with the item at index `0`. Subsequent items in the sequence would correspond to subsequent items in the array. When it reaches the end of the array then the sequence is empty.

While sequences are not a core language feature, they do play a fundamental part in the design of Stanza's core library. In this chapter we'll see how to fully exploit their power, and by doing so, avoid having to repeatedly reimplement many common programming patterns ourselves.

## Fundamental Operations

A sequence is represented by the `Seq` type in Stanza. Let's first create a sequence containing all the strings in a tuple.

``val xs = to-seq(["Timon" "and" "Pumbaa" "are" "good" "friends."])``

This creates the sequence `xs`, which has type `Seq<String>` indicating that it is a sequence of strings.

Fundamentally, a sequence is defined by three operations.

1. You may ask whether a sequence is empty.
2. You may take a peek at the next item in the sequence.
3. You may take out the next item in the sequence.

Here is how to ask whether our `xs` sequence is empty.

``if empty?(xs) :   println("xs is empty.")else :   println("xs is not empty.")``

which prints out

``xs is not empty.``

because we haven't taken anything out of the sequence yet.

If the sequence is not empty, then you can take a peek at the next item in the sequence like this.

``val x0 = peek(xs)println("The next item is %_." % [x0])``

which prints out

``The next item is Timon.``

Peeking at an empty sequence is a fatal error.

Peeking at a sequence does not change the state of a sequence. If you peek again at the same sequence, it returns the same thing.

``val x1 = peek(xs)println("The next item is still %_." % [x1])``

which prints out

``The next item is still Timon.``

Once you've determined that the sequence is not empty, you may take out the next item in the sequence.

``val y0 = next(xs)println("Took out item %_ from xs." % [y0])``

which prints out

``Took out item Timon from xs.``

Calling `next` on a sequence does change the state of a sequence. If you call `next` again on the same sequence, it will return the following item in the sequence.

``val y1 = next(xs)println("Now took out item %_ from xs." % [y1])``

which prints out

``Now took out item and from xs.``

Here is the standard pattern for printing out all the items in a sequence.

``while not empty?(xs) :   println("Next item is %_" % [next(xs)])``

which prints out

``Next item is TimonNext item is andNext item is PumbaaNext item is areNext item is goodNext item is friends.``

## Writing a Sequence Function

Let's now write a function that takes a sequence argument. `cum-sum` takes a sequence of integers, `xs`, and returns a vector containing the cumulative sum of all the numbers in `xs`.

``defn cum-sum (xs:Seq<Int>) :   val ys = Vector<Int>()   var accum = 0   while not empty?(xs) :            accum = accum + next(xs)      add(ys, accum)   ys``

Let's try it out on some numbers.

``defn main () :   val xs = [1, 1, 3, 1, 5, 6, 2, 3, 8]   println(cum-sum(to-seq(xs)))main()``

Compiling and running the above prints out

``[1 2 5 6 11 17 19 22 30]``

### Seqable

Notice that in the call to `cum-sum` we have to explicitly convert our tuple into a `Seq` object using `to-seq`. Otherwise Stanza would issue a type error. For convenience, however, it would be better to move the call to `to-seq` inside the body of `cum-sum` and have `cum-sum` accept any object that supports `to-seq`

This brings us to the type `Seqable`. Values of type `Seqable` support only a single operation: calling `to-seq` on a `Seqable` object returns a `Seq``Seqable` also accepts a type parameter that indicates the type of element it contains. Thus calling `to-seq` on a `Seqable<Int>` returns a `Seq<Int>`.

Let's change our `cum-sum` function to accept an object of type `Seqable<Int>`.

``defn cum-sum (xs:Seqable<Int>) :   val xs-seq = to-seq(xs)   val ys = Vector<Int>()   var accum = 0   while not empty?(xs-seq) :            accum = accum + next(xs-seq)      add(ys, accum)   ys``

Now our `cum-sum` function is general enough to be called with any `Seqable` object. This includes ranges, tuples, arrays, vectors, lists (which we will cover later), and even other sequences. Let's try it out.

``defn main () :   val xs = [1, 1, 3, 1, 5, 6, 2, 3, 8]   val ys = to-array<Int>([1, 1, 3, 1, 5, 6, 2, 3, 8])   val zs = to-vector<Int>([1, 1, 3, 1, 5, 6, 2, 3, 8])   val ws = to-list([1, 1, 3, 1, 5, 6, 2, 3, 8])   println(cum-sum(xs))   println(cum-sum(ys))   println(cum-sum(zs))   println(cum-sum(ws))main()``

which prints out

``[1 2 5 6 11 17 19 22 30][1 2 5 6 11 17 19 22 30][1 2 5 6 11 17 19 22 30][1 2 5 6 11 17 19 22 30]``

This is the mechanism that allows the core library functions (such as `do`) to operate on all sorts of collections. `do` just accepts a `Seqable` argument.

And since `do` accepts a `Seqable` argument, we can actually rewrite our `cum-sum` function more elegantly using `do`

``defn cum-sum (xs:Seqable<Int>) :   val ys = Vector<Int>()   var accum = 0   for x in xs do :      accum = accum + x      add(ys, accum)   ys``

## Lazy Sequences

Our `cum-sum` function takes a sequence as its argument and returns a vector. This works just fine if we want all of the cumulative sums, but what if we want only the first four? Then we're spending a lot of time computing results that we don't need.

To overcome this, we can rewrite `cum-sum` to return a `Seq<Int>` instead of a `Vector<Int>` where the elements in the returned sequence is computed on-demand

``defn cum-sum (xs:Seqable<Int>) :   var accum = 0   val xs-seq = to-seq(xs)   new Seq<Int> :      defmethod empty? (this) :         empty?(xs-seq)      defmethod peek (this) :         accum + peek(xs-seq)      defmethod next (this) :         accum = peek(this)         next(xs-seq)         accum``

Now `cum-sum` returns a lazy sequence where items are computed as they're needed. To demonstrate this, let's call `cum-sum` on an infinite range of numbers, and print out the first 10 elements.

``defn main () :   val xs = 1 to false by 3   val ys = cum-sum(xs)   for i in 0 to 10 do :      println("Item %_ is %_." % [i, next(ys)])main()``

Compiling and running the above gives us

``Item 0 is 1.Item 1 is 5.Item 2 is 12.Item 3 is 22.Item 4 is 35.Item 5 is 51.Item 6 is 70.Item 7 is 92.Item 8 is 117.Item 9 is 145.``

Thus `ys` is an infinite sequence of integers containing the cumulative sum of another infinite sequence of integers.

### seq

Creating a sequence by calling a function repeatedly on the items from another sequence is a common operation, so it is included in Stanza's core library as the `seq` operating function. The `cum-sum` function can be rewritten using `seq` like this.

``defn cum-sum (xs:Seqable<Int>) :   var accum = 0   for x in xs seq :      accum = accum + x      accum``

## Using The Sequence Library

Now that we've been introduced to sequences, we can unveil the full power of Stanza's core library. As mentioned in an earlier chapter, Stanza encourages users to architect their programs by defining a small set of fundamental operations on each type, and then augment that with a large library of derived operations for those types. Stanza's sequence library is structured in such a way.

The set of fundamental operations for a `Seq` is very small, comprised of just `empty?``peek`, and `next`. But Stanza includes a large library of useful functions for manipulating sequences. These functions are roughly categorized into three groups: sequence creators, sequence operators, and sequence reducers. Independently of this categorization, a large number of these functions are also operating functions and can be used with the for construct.

### Sequence Creators

Sequence creators are functions that take non-`Seq` arguments and create and return `Seq` objects. In typical programming, most sequences you manipulate will have been created with a sequence creator.

### to-seq

The most commonly used sequence creator is the `to-seq` function, which works on any `Seqable` object. You've already seen usages of it for converting tuples, arrays, vectors, and ranges to sequences.

### repeatedly

`repeatedly` takes an argument function, `f`, and creates an infinite sequence from the results of calling `f` repeatedly. Here is an example of using it to create a sequence containing all the positive powers of 2.

``var x = 1Lval xs = repeatedly \$ fn () :   val cur-x = x   x = x * 2L   cur-x``

Let's print out the first 10 elements.

``do(println{next(xs)}, 0 to 10)``

which prints out

``1248163264128256512``

### repeat-while

`repeat-while` takes an argument function, `f`, and creates an infinite sequence by calling `f` repeatedly. `f` must return a `Maybe` object. The returned sequence contains all the wrapped objects in all the `One` objects returned by `f` and ends the first time `f` returns a `None` object.

Here is an example of using it to create a sequence containing all the positive powers of 2 that are less than 2000.

``var x = 1Lvar xs = repeat-while \$ fn () :   val cur-x = x   if cur-x < 2000L :      x = x * 2L      One(cur-x)   else :      None()``

Let's print out all the items in `xs`.

``do(println, xs)``

which prints out

``12481632641282565121024``

### Sequence Operators

Sequence operators are functions that take `Seq` (or `Seqable`) arguments and create and return `Seq` objects. The lazy `cum-sum` function that we implemented is an example of a sequence operator.

### cat

One of the simplest sequence operators is the `cat` function which simply concatenates two sequences together to form a longer sequence.

Here is an example.

``val xs = ["Patrick", "Luca", "Emmy"]val ys = ["Sunny", "Whiskey", "Rummy"]val zs = cat(xs, ys)do(println, zs)``

which prints out

``PatrickLucaEmmySunnyWhiskeyRummy``

### join

`join` is another simple sequence operator that takes a sequence, `xs`, and a joiner item, `x`, and creates a lazy sequence by inserting `x` in between each item in `xs`.

Here is an example.

``val xs = ["Patrick", "Luca", "Emmy"]val zs = join(xs, "and")do(println, zs)``

which prints out

``PatrickandLucaandEmmy``

### take-n

The `take-n` function takes an integer, `n`, and a sequence, `xs`, and returns a lazy sequence consisting of the first `n` elements in `xs`. It is a fatal error to call `take-n` on a sequence with less than `n` items.

Here is an example of using `take-n` to print out the first 10 items in an infinite range.

``val xs = 0 to false by 13do(println, take-n(10, xs))``

which prints out

``013263952657891104117``

### filter

The `filter` function takes a predicate function, `f`, and a sequence, `xs`, and returns a lazy sequence consisting only of the items in `xs` for which calling `f` on them returns `true``filter` is also an operating function.

Here is an example of using `filter` to print out only the positive items in a sequence.

``val xs = [1, 3, -2, -7, 3, -8, 9, 10, -3]val ys = filter({_ > 0}, xs)do(println, ys)   ``

which prints out

``133910``

### seq

The `seq` function is the most commonly used sequence operator. It takes a function, `f`, and a sequence, `xs`, and returns a lazy sequence comprised of the results of calling `f` on each item in the sequence.

Here is an example of printing out the length of each string in a sequence.

``val xs = ["Patrick", "Luca", "Emmy", "Sunny", "Whiskey", "Rummy"]val ys = seq(length, xs)do(println, ys)``

which prints out

``744575``

### Sequence Reducers

Sequence reducers are functions that take `Seq` (or `Seqable`) arguments and return non-`Seq` objects.

We have already been introduced to and have been using a number of these, such as `do``find``first``index-when``all?``none?`, and `any?`. We'll take this opportunity to say that they each accept any `Seqable` object as their argument.

We'll show you a handful more useful reducers here, but you are encouraged to read the reference documentation for a listing of all of them.

### contains?

`contains?` takes a sequence, `xs`, and an item, `y`, and returns `true` if `xs` contains `y`. Otherwise it returns `false`.

``val xs = ["Patrick", "Luca", "Emmy"]println(contains?(xs, "Emmy"))println(contains?(xs, "Emily"))``

prints out

``truefalse``

### index-of

`index-of` takes a sequence, `xs`, and an item, `y`, and returns the index of the first occurrence of `y` in `xs`. If `y` never appears in `xs`, then `false` is returned.

``val xs = ["Patrick", "Luca", "Emmy"]println(index-of(xs, "Emmy"))println(index-of(xs, "Emily"))``

prints out

``2false``

### unique

`unique` takes a sequence, `xs`, and returns a list containing all the items in `xs` but with duplicates removed.

``val xs = ["Patrick", "Luca", "Luca", "Emmy", "Patrick", "Emmy"]println(unique(xs))``

prints out

``("Patrick" "Luca" "Emmy")``

### to-array

`to-array` creates a new array containing all the items in its given sequence. It takes a single type argument to indicate the element type of the array. We will discuss type arguments when we introduce parametric polymorphism.

Here is an example.

``val xs = ["Patrick", "Luca", "Emmy"]println(to-array<String>(xs))``

prints out

``["Patrick" "Luca" "Emmy"]``

### to-vector

`to-vector` creates a new vector containing all the items in its given sequence. Like `to-array`, it also takes a single type argument to indicate the element type of the vector.

Here is an example.

``val xs = ["Patrick", "Luca", "Emmy"]println(to-vector<String>(xs))``

### to-list

`to-list` creates a new list containing all the items in its given sequence. Note that unlike `to-array` and `to-vector``to-list` does not take a type argument. We will cover lists in more detail when we talk about programming with immutable datastructures. For now, you can treat them just as another type of collection. And we will explain why `to-list` does not require a type argument in the chapter on parametric polymorphism.

Here is an example.

``val xs = ["Patrick", "Luca", "Emmy"]println(to-list(xs))``

which prints out

``("Patrick" "Luca" "Emmy")``

### reduce

`reduce` takes a binary operator, `f`, an initial item, `x0`, and a sequence, `xs`. If `xs` is empty then `reduce` returns `x0`. If `xs` contains one item, then `reduce` returns the result of calling `f` on `x0` and the item in `xs`. If `xs` contains two items, then `reduce` returns the result of calling `f` on `x0` and the first item in `xs`, and then calling `f` again on that result and the second item in `xs`. If `xs` contains three items, then `reduce` returns the result of calling `f` on `x0` and the first item in `xs`, then calling `f` again on that result and the second item in `xs`, and then calling `f` again on that result and the third item in `xs`. Et cetera.

Here is an example of using the `bit-or` operator to compute the bitwise or of every integer in a tuple.

``val xs = [1, 5, 18, 92, 1, 3]val y = reduce(bit-or, 0, xs)println(y)``

which prints out

``95``

## Collection versus Seqable

Consider the following definition of `print-odd-then-even`, a function that first prints all the odd integers in a sequence, and then prints all the even integers in the sequence.

``defn print-odd-then-even (xs:Seqable<Int>) :   val odd = filter({_ % 2 != 0}, xs)   val even = filter({_ % 2 == 0}, xs)   print("Odd integers: ")   println-all(join(odd, ", "))   print("Even integers: ")   println-all(join(even, ", "))``

Because we declared `print-odd-then-even` to accept an argument of type `Seqable`, we are able to call it on a variety of different types of collections. Let's try a few.

``defn main () :   val xs = [1, 2, 3, 4, 5, 6, 7, 8]   val ys = to-array<Int>([1, 2, 3, 4, 5, 6, 7, 8])   val zs = to-vector<Int>([1, 2, 3, 4, 5, 6, 7, 8])   val ws = 1 through 8      println("On tuples")   print-odd-then-even(xs)   println("On arrays")   print-odd-then-even(ys)   println("On vectors")   print-odd-then-even(zs)   println("On ranges")   print-odd-then-even(ws)main()   ``

It prints out

``On tuplesOdd integers: 1, 3, 5, 7Even integers: 2, 4, 6, 8On arraysOdd integers: 1, 3, 5, 7Even integers: 2, 4, 6, 8On vectorsOdd integers: 1, 3, 5, 7Even integers: 2, 4, 6, 8On rangesOdd integers: 1, 3, 5, 7Even integers: 2, 4, 6, 8``

demonstrating that it does the same thing regardless of the type of collection.

But now let's try calling it on a `Seq`. All `Seq` objects are also trivially instances of `Seqable`. Calling `to-seq` on a `Seq` object simply returns itself.

``defn main2 () :   val xs = to-seq(1 through 8)   println("On seqs")   print-odd-then-even(xs)main2()``

This print outs

``On seqsOdd integers: 1, 3, 5, 7Even integers: ``

What is happening? How come the even integers didn't get printed out?

The problem lies in the two calls to `filter`.

``val odd = filter({_ % 2 != 0}, xs)val even = filter({_ % 2 == 0}, xs)``

`filter` creates a lazy sequence, so iterating over the result of `filter` also requires iterating over the sequence it was constructed from. Thus printing out `odd` also requires iterating over `xs`, in which case, after printing out all the odd integers, we will have iterated through `xs` once completely and it will now be empty. At this point, `even` is also empty, as the sequence it was constructed from is now empty.

The fundamental problem is that `Seq` is a subtype of `Seqable`. Calling `to-seq` twice on a `Seq` object does not return two independent sequences. For these purposes, Stanza provides a subtype of `Seqable` called `Collection`. Identical to `Seqable``to-seq` is the only fundamental operation supported by `Collection`. The crucial difference is that `Seq` is not a subtype of `Collection`. This means that each call to `to-seq` on a `Collection` returns an independent sequence.

Let's rewrite our `print-odd-then-even` function with the appropriate type annotation.

``defn print-odd-then-even (xs:Collection<Int>) :   val odd = filter({_ % 2 != 0}, xs)   val even = filter({_ % 2 == 0}, xs)   print("Odd integers: ")   println-all(join(odd, ", "))   print("Even integers: ")   println-all(join(even, ", "))``

You may verify that calling `print-odd-then-even` with all the collections in `main` still behaves as before. The important point is that attempting to compile `main2` now gives this error.

``Cannot call function print-odd-then-even of type Collection<Int> -> Falsewith arguments of type (Seq<Int>).``

With the appropriate type annotation, Stanza now prevents us from calling `print-odd-then-even` incorrectly.

As a rule of thumb, you should always write your functions to accept `Collection` objects by default. If you are sure that you iterate through the sequence only once, then you may change it to accept `Seqable` objects in order to be able to pass it a `Seq`.

## Revisiting Stack

Let us now revisit our `Stack` type from chapter 4. Here is a (slightly cleaned up) listing of its definitions.

``deftype Stackdefmulti push (s:Stack, x:String) -> Falsedefmulti pop (s:Stack) -> Stringdefmulti empty? (s:Stack) -> True|Falsedefn Stack (capacity:Int) -> Stack :   val items = Array<String>(capacity)   var size = 0   new Stack :      defmethod push (this, x:String) :         if size == capacity : fatal("Stack is full!")         items[size] = x         size = size + 1      defmethod pop (this) :         if size == 0 : fatal("Stack is empty!")         size = size - 1         items[size]      defmethod empty? (this) :         size == 0      defmethod print (o:OutputStream, this) :         print(o, "Stack containing [")         print-all(o, join(take-n(size, items), " "))         print(o, "]")``

It's quite a basic definition, allowing us to push and pop items but not much else. We cannot find the index of a specific item, or determine whether it contains any capitalized strings, or get a listing of all of its unique elements. We cannot even iterate through it. The following

``val s = Stack(10)push(s, "Timon")push(s, "and")push(s, "Pumbaa")for x in s do :   println(x)``

gives us this error if we try to compile it.

``No appropriate function do for argumentsof type (? -> False, Stack). Possibilities are:   do: <?T> . (T -> ?, Seqable<?T>) -> False   do: <?T, ?S> . ((T, S) -> ?,                   Seqable<?T>,                   Seqable<?S>) -> False   do: <?T, ?S, ?U> . ((T, S, U) -> ?, Seqable<?T>,                       Seqable<?S>,                       Seqable<?U>) -> False``

It says that there are multiple definitions of `do` but all of them require a `Seqable` argument, and `Stack` is not a `Seqable`.

We shall extend the functionality of `Stack` by declaring it as a subtype of `Collection`

``deftype Stack <: Collection<String>``

The mandatory minimal implementation of `Collection` is `to-seq`, so we need to now provide a method for it. Here is now our extended `Stack` construction function.

``defn Stack (capacity:Int) -> Stack :   val items = Array<String>(capacity)   var size = 0   new Stack :      defmethod push (this, x:String) :         if size == capacity : fatal("Stack is full!")         items[size] = x         size = size + 1      defmethod pop (this) :         if size == 0 : fatal("Stack is empty!")         size = size - 1         items[size]      defmethod empty? (this) :         size == 0      defmethod print (o:OutputStream, this) :         print(o, "Stack containing [")         print-all(o, join(this, " "))         print(o, "]")      defmethod to-seq (this) :         take-n(size, items)``

Our implementation of `to-seq` simply calls `take-n` to retrieve the first `size` elements from the backing array `items`.

Now let's try exercising the power of our new extended `Stack` type.

``defn main () :   val s = Stack(10)   for x in ["Timon", "Timon", "and", "Pumbaa", "Pumbaa"] do :      push(s, x)   println("1. Contents of s")   println(s)   println("\n2. Index of Pumbaa")   println(index-of(s, "Pumbaa"))   println("\n3. Does it contain any capitalized strings?")   println(any?(upper-case?{_[0]}, s))   println("\n4. Are all strings capitalized?")   println(all?(upper-case?{_[0]}, s))   println("\n5. What are the capitalized strings?")   val cap-s = filter(upper-case?{_[0]}, s)   println-all(join(cap-s, ", "))   println("\n6. What are its unique elements?")   println(unique(s))main()``

Compiling and running the above prints out

``1. Contents of sStack containing [Timon Timon and Pumbaa Pumbaa]2. Index of Pumbaa33. Does it contain any capitalized strings?true4. Are all strings capitalized?false5. What are the capitalized strings?Timon, Timon, Pumbaa, Pumbaa6. What are its unique elements?("Timon" "and" "Pumbaa")``

This example shows us the full advantage of structuring your programs to contain a large library of derived operations. With a two line change to our definition of the `Stack` object, we've provided it the full capabilities of Stanza's sequence library.