Class 27: Vectors

Held Thursday, March 8, 2001

Summary

Today we consider vectors, which serve as alternates to lists. Vectors differ from lists in three primary ways: vectors have fixed size, vectors are indexed, and vectors are mutable.

Notes

• I've scanned the surveys (and will probably do another scan this weekend).
  • As you might expect, there were opposite answers on a lot of questions.
  • For example, about 1/4 of you want more lecture and about 1/4 of you want less lecture.
  • There does seem to be some inverse correlation between your opinion of the complexity of the course and your desire for lecture.
  • To that, I respond that You can't learn to ride a bike by watching someone else.
• Are there questions on homework 4?
  • Lists should certainly be surrounded by parentheses.
  • Almost everything else is up for grabs as long as it's readable and you clearly document what you're doing.
  • Please don't use hacks involving write and display.
• Are there any questions on lab writeup 2?
• Don't forget, cool convo talk today; cool CS talk this afternoon.
• Yup, tomorrow's reading is delayed. It's been a bad week.

Overview

• Problems with lists
• A solution: Vectors
• Common vector procedures
• Lab

List Deficiencies

• Now that we've worked with lists for a while, we've identified some things that make lists inappropriate for some situations.
  • List are expensive to use; to find the length of a list or to access an element late in the list, you need to cdr down the list.
  • Lists are fixed; you can't easily change an element of a list.
• At the same time, there are some advantages to lists:
  • Lists are dynamic; it is easy to grow and shrink a list.
  • Lists are inherently recursive; the type is defined recursively.
  • Lists are simple; you can build almost every list operation through just a few basic operations (car, cdr, null, and null?).

An Alternative: Vectors

• The designers of Scheme decided that it would be useful to include another compound data type that handled some of the deficiencies of lists.
  • However, that meant we had to give up some of the advantages of lists.
• Vectors are compound data types that
  • Have fixed size: One you create a vector, you cannot easily add elements to the vector.
  • Permit indexed access: You can quickly access any element in a vector.
  • Support mutation: You can change any element of a vector.
• Through the rest of the term, we'll often ask ourselves whether we're better off using a vector or a list for a particular problem.
• We've seen that lists are implemented through cons cells. How are vectors implemented? There's basically just a big cons-cell-like thing that has as many boxes as there are elements in the vector (plus a notation as to the vector's length).

Common Vector Methods

• (vector val1 ... valn): a lot like list
• (make-vector size element): make a vector of a particular length containing lots of copies of the same value.
• (vector? value): determine if a value is a vector
• (vector-length vector): get the length of a vector
• (vector-ref vector pos): get an element from a vector.
• (vector-set! vector pos newval): change part of a vector. Note the use of an exclamation point to indicate that this changes its argument.
• (list->vector list): Guess
• (vector->list vector): Guess
• (vector-fill! vector value): Fill an existing vector with a particular value.

Lab

• Do the lab.
• Be ready to reflect.