NAVIGATION

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.

You may ask whether a sequence is empty.
You may take a peek at the next item in the sequence.
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 Timon
Next item is and
Next item is Pumbaa
Next item is are
Next item is good
Next 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 = 1L
val 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

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 = 1L
var 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

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

Patrick
Luca
Emmy
Sunny
Whiskey
Rummy

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

Patrick
and
Luca
and
Emmy

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 13
do(println, take-n(10, xs))

which prints out

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

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

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

true
false

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

2
false

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

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 tuples
Odd integers: 1, 3, 5, 7
Even integers: 2, 4, 6, 8
On arrays
Odd integers: 1, 3, 5, 7
Even integers: 2, 4, 6, 8
On vectors
Odd integers: 1, 3, 5, 7
Even integers: 2, 4, 6, 8
On ranges
Odd integers: 1, 3, 5, 7
Even 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 seqs
Odd integers: 1, 3, 5, 7
Even 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> -> False
with 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 Stack
defmulti push (s:Stack, x:String) -> False
defmulti pop (s:Stack) -> String
defmulti empty? (s:Stack) -> True|False

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(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 arguments
of 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 s
Stack containing [Timon Timon and Pumbaa Pumbaa]

2. Index of Pumbaa
3

3. Does it contain any capitalized strings?
true

4. Are all strings capitalized?
false

5. What are the capitalized strings?
Timon, Timon, Pumbaa, Pumbaa

6. 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.