210lab12 < Teaching

Instructions for students & labbies: Students use DrScheme, following the design recipe, on the exercises at their own pace, while labbies wander among the students, answering questions, bringing the more important ones to the lab's attention.

Accumulators on Trees

We've seen some examples of using accumulators with lists. While we've formally introduced the idea this week, a few examples have popped up earlier without any fanfare. What about with other data types? Is there anything additional to see and learn? Yes!

Skim section 32.1 from the book. There are two important points to take away from this section:

When there are multiple recursive calls, threading the accumulator from one recursive call into the other recursive call is very useful. (See Figure 92.)
There are multiple ways to use accumulators. One general technique is for the accumulator to be a partial result. When you are done with all of your input (i.e., the base case), you return the accumulator, since that is your result. (E.g., Figure 92.) Another general technique is for the accumulator to build up information that helps the computation. (E.g., 93.)

Accumulator exercise


Develop an accumulator based function that multiplies all the numbers in a tree. This will use the accumulator threading mentioned above. We'll use the following binary tree type. ; A binary tree of numbers (btn) is one of ; - a number, or ; - (make-node n l r), ; where n is a number, and l and r are btns. (define-struct node (n l r)) In addition, we want to take advantage of our mathematical knowledge that anything multiplied by zero is zero. Your function should quit recurring through the tree and return zero if you ever multiply by zero.

Vector Basics

We frequently want a data structure to store a collection of data. Today we'll introduce one more solution, vectors, for this problem. It's useful to contrast vectors with structures and lists.

Data structure	# of items	Accessing data
Structures	Any particular data structure type contains a fixed number of items. E.g., a "posn" contains two items, and `make-posn` takes two items.	You can access any of the structure's items directly, by name. E.g., for a "posn", use `posn-x` and `posn-y`.
Lists	Lists can contain an arbitrary number of items. Given a list, we can easily make a larger one with `cons`, or a shorter one with `rest`.	Accessing the `i`^th item requires about `i` steps.
Vectors	Vectors can contain an arbitrary number of items. But, given a vector, we cannot directly make a larger or shorter one. When creating a particular vector, we give it a specific size that cannot be changed.	You can access any of the vector's items directly, by position number, or index.

Note: Some languages use the terms arrays instead of vectors.

To use vectors in DrScheme, change to the Advanced Language Level.

Vector examples/exercises


We'll introduce how to use vectors by examples. Try these in DrScheme and see what each line returns. (define colors (vector 'teal 'ecru 'lilac 'maroon 'red)) colors ⇒ ??? (vector-length colors) ⇒ ??? (vector-ref colors 3) ⇒ ??? (vector-ref colors 0) ⇒ ??? (vector-ref colors 5) ⇒ ??? After these examples, be sure that you understand how vectors are indexed. Define a couple vectors of your own. Suggestions: a vector containing the names of the 8 known planets; a vector containing one posn, the origin. We can also define a vector containing no elements. Following your previous examples, how can you do this? Try it. Define a function that takes any vector of positive length and returns its last element. Try it on your examples.

You've summed up lists in many ways. It's a conceptually simple computation that has been useful for illustrating structural recursion on lists, using abstract functions like foldr and

foldl, and will soon be used to illustrate accumulators. Now, let's sum up vectors.

A vector can be of arbitrary size, but they aren't defined recursively, so how can we write such a function? The indices are natural numbers, which are defined recursively, so let's recur on the index! For example,

      ; vec-sum-help : vector-of-numbers natural -> number
      ; Returns the sum of the first num-elts elements in vector v.
      (define (vec-sum-help v num-elts)
         (cond
            [(zero? n)     0]
            [(positive? n) (+ (vector-ref v (sub1 num-elts))
                              (vec-sum-help v (sub1 num-elts)))]))

      ; vec-sum : vector-of-numbers -> number
      ; Returns the sum of the elements in vector v.
      (define (vec-sum v)
         (vec-sum-help v (vector-length v)))

Vector exercises
In the previous example, it may be a little surprising that we use `(vector-ref v (sub1 num-elts))`, rather than `(vector-ref v num-elts)`. Do you understand why? If not, step through an example use. One of the most common mistakes with vectors is to use an index that's one less or greater than intended. Write a function to return whether any vector element is equal to 5. In many programming languages, it is more traditional to look at the indices in ascending order instead of descending, as above. Write a function that sums up the vector elements in ascending index order, instead. (What is the base case?)

Vector examples/exercises
From the previous examples, `vector` is analogous to `make-s`, for a structure type s, and to `list`. There are alternative ways to define vectors. Try the following in DrScheme and see what each line returns. (define numbers (build-vector 10 (lambda (i) i))) numbers ⇒ ??? (define twos (make-vector 7 2)) twos ⇒ ??? Use `build-vector` to construct a list of 10 elements: 0, 1, 4, 9, 16, … Write a function that takes a natural number `n` and creates a vector of that length of 2×1, 2×2, …, 2×`n`. Write a function that takes a vector of numbers, and returns a new vector of the same length who elements are double of the original. Generalize your previous example to `map-vector : (X->Y) vector-of-X -> vector-of-Y`, analogous of mapping on a list. If you have time… Similarly, write the equivalent of `filter` on a list, except on vectors: `filter-vector : (X->boolean) vector-of-X -> vector-of-X` . Note that the resulting vector is generally shorter than the original.

In math, we often generalize one-dimensional vectors to two- (or more) dimensional matrices. Scheme, like many languages, do not have two-dimensional vectors/matrices. Instead, we can use vectors of vectors. For example,

      (define matrix (vector (vector 1 2 3)
                             (vector 4 5 6)
                             (vector 7 8 9)))

      (define v-of-v (vector (vector 1 2)
                             (vector 3)
                             (vector 4 5 6 7)
                             (vector 8 9)))

As you can see, the inner vectors need not be of the same length in general.

Vector-of-vector exercises
Write a function that, given natural number `n`, creates a `n`×`n` matrix (i.e., vector of vectors) with each element being 1. If you have time… Write a function that, given natural number `n`, creates a `n`×`n` "identity" matrix, i.e., with 1's on the diagonal (where the row index equals the column index) and 0's everywhere else. Write a function that takes a vector-of-vectors-of-numbers and returns the sum of all its numbers. Hint: Use `vec-sum`. If you have time… Write a function that take a vector-of-vectors and returns whether it is a matrix, i.e., whether all its vectors are of the same length.

Accumulators on Trees; Vectors

Accumulators on Trees

Vector Basics

Access Permissions