Vector basics, "For" Loops, "Until" Loops
A list can contain as many items as you like, but you can only access the first element directly. In contrast, we'll introduce a new structure, vectors, where you can access (say) the 17th element directly, but the structure contains exactly a pre-determined fixed number of items.
Here as some self-explanatory examples of how to use vectors. Type them into DrScheme and see what happens. (define colors (vector 'teal 'ecru 'lilac 'maroon 'red)) (vector-ref colors 3) (vector-ref colors 0) (vector-ref colors 5) ; ERROR -- indices must be in [0,5). (vector-length colors) (vector-set! colors 3 'macaroni) (vector-ref colors 3) |
In addition to creating vectors via vector
,
there is also a function build-vector
,
which creates a vector where the ith location
is initialized to a function of i.
What should the following return? (build-vector 5 sqr) (build-vector 5 (lambda (i) (* 2 i))) |
In comments, we'll often write "v[i]", as a shorthand for "(vector-ref v i)".
Vectors are another abstraction for collections of data. Like a structure, each element of a vector is named, in this case with a number. I.e., they are named 0, 1, 2, 3, … in order. Vectors can be of any length when created, although you cannot change the length of a particular vector.
When msn.net was first set up, people could sign up for accounts. When they got their one-millionth customer, their code broke -- the site was down for three days, and a million customers couldn't log on to the net. Presumably they'd used vectors, when a list would be more appropriate. (They wanted the constant-time random-access of a vector, but didn't know the number of elements in advance. At the very least, their code for adding a new customer should have had refused the millionth customer, rather than crashing the system for everybody! |
Remember that vector elements are indexed starting with 0, not 1! That means you should never use code like
(vector-ref vec (vector-length vec))because there is no such element in the vector. While there is a historical reason for 0-indexing, today the primary motivation is tradition. Almost all programming languages follow this tradition.
Note that we can have empty vectors, just like empty lists:
(vector)This is a vector with zero elements. (Fairly useless, isn't it?)
We won't worry about all of the following, but for your reference, here is a summary of the most common built-in vector functions:
(vector v0
…
vn-1)
creates a vector of length n of the given elements.
(build-vector n f)
creates a vector of length n of elements
(f 0)
…
(f (sub1 n))
(make-vector n v)
creates a vector of length n,
of n instances of v.
It is essentially a special case of build-vector
.
(vector-length vec)
returns the length of the given vector.
(vector-ref vec n)
returns the nth
element of the vector (counting from zero).
(vector-set! vec n v)
changes the nth element of the vector
to be the given element (counting from zero).
|
In that last exercise, there are really two different things:
(vector-set! v i (sqr (vector-ref v i)))
We'll loop through each of these values.
When using loops, it is more common to count upwards, so we'll do that.
So, the latter part is looping from 0 to n-1.
(Note that if n=0, that means doing nothing.)
Note that this is an abstraction similar to foldr
for natural numbers:
it allows us to seperate the code for an individual task
from the iterative process of calling that task on 0, 1, 2, …)
|
|
To think about:
What if we frequently wanted to do something
with every other number in a range?
Should we modify the task (i.e., body!
),
or modify the control logic in charge
of applying body!
to the right values?
Both ways work; the latter is better, since it separates the
individual task from the looping.
Do we need to use mutation, to make use of a "for" loop? No, we actually have been doing stuff all along which didn't. Consider the following examples:
(triangle-number 3) = 1 + 2 + 3 = 6 (countdown 3) = (list 3 2 1 'blastoff) (define (triangle-number n) (loop-for-acc 1 (add1 n) 0 ; The initial sum-so-far (accumulator). (lambda (i so-far) (+ i so-far)))) ; A body which creates new accum. (define (countdown n) (loop-for-acc 0 n '(blastoff) ; Initial accumulator value. (lambda (i so-far) (cons (add1 i) so-far))))
Write a version of (define (loop-for-acc strt stop init body ) …) |
Let's see another example of how recursion and looping are related. Some of the corresponding syntactic pieces are highlighted in color.
We start with a simple structurally recursive program:
(define (sum-list alon) (cond [(empty? alon) 0] [(cons? alon) (+ (first alon) (sum-list (rest alon)))]))
We can then obtain the accumulator version:
(define (sum-list alon) (local [(define (sum-list-acc the-lon accum) (cond [(empty? the-lon) accum] [(cons? the-lon) (sum-list-acc (rest the-lon) (+ (first the-lon) accum))]))] (sum-list-acc alon 0)))As you've seen, sometimes this step is difficult. Remember that this version adds up the numbers in the oppositive order. Thus, part of the reason it was relatively easy to obtain this version is that addition is associative.
We can rewrite this to avoid passing arguments in the helper function and, instead, change only local variables. This step is similar to the assembly-language code that a compiler would produce. This is a straightforward syntactic translation:
(define (sum-list alon) (local [(define accum 0) (define the-lon alon) (define (sum-list!) (cond [(empty? the-lon) accum] [(cons? the-lon) (begin (set! accum (+ (first the-lon) accum)) (set! the-lon (rest the-lon)) (sum-list!))]))] (sum-list!)))
Does the order of the two |
Lastly, we can rewrite this using one of Scheme's several looping constructs. (Make sure you're using DrScheme's "Pretty Big" language level.) This is another straightforward syntactic translation:
(define (sum-list alon) (local [(define accum 0)] (begin (loop-until alon empty? rest (lambda (the-lon) (set! accum (+ (first the-lon) accum)))) accum)))
loop-until
takes four arguments:
a starting value to loop on, a test for what value(s) to stop on,
a function to get the next loop value from the current one,
and a function to evaluate on each loop iteration.
What must the contract for |
Most programming languages have a construct similar to this, except with a test for what value(s) to continue looping (i.e., the opposite of what's used here). Then, it is typically called a "while" loop.
This process is insufficient for all programs, but it shows that recursion and iteration are closely related. They are both useful tools.
Which version of sum-list
is best?
set!
.
|