Vectors

A vector is a new basic type in Scheme: like a list, but not. Vectors are good if you know exactly how many elements you need ahead of time, and are going to be accessing things by number. They're also more efficient for getting and setting elements in the middle of the sequence. But it's really hard to add or delete elements—you have to make a new vector to do it!

Vector programs are all based on mutation. If you want to do a functional vector procedure, you make a new "result" vector and mutate that. Often (but not always) a vector program will also use a helper procedure that takes a single argument, an index, which is just a number you use to say where you are in the vector.

Check out the comparison of vectors and lists, which also shows the common vector procedures.

Here's some practice with vectors:

• Write vector->list, which takes a vector and returns a list of the same elements. (This is actually in STk, but you should be able to redo it here.)

  (show answer)

  The most straightforward way to do this is to remember that we can build the list recursively using cons just like any other list-based procedure. Even though we have to keep track of where we are in the vector!

  (define (vector->list vec)
    (define (helper i)
      (if (= i (vector-length vec))
          vec
          (cons (vector-ref vec i) (helper (+ i 1))) ))
    (helper 0) )

  You can also do this going from the end of the vector back to the beginning; this approach works well for building the list iteratively.

  (define (vector->list vec)
    (define (helper i so-far)
      (if (< i 0)
          so-far
          (helper (- i 1) (cons (vector-ref vec i) so-far)) ))
    (helper (- (vector-length vec) 1)) )

  Either way, remember that the elements of a vector start at 0, not at 1!

  (hide answer)

• Write list->vector, which takes a list and returns a vector of the same elements. (This is also in STk already.)

  (show answer)

  This time, the key point was to realize you have to make the vector before you put anything in it. You could do this very simply, without trying to be efficient:

  (define (list->vector lst)
    (let ((result (make-vector (length lst))))
      (define (helper i)
        (if (= i (vector-length result))
            result
            (begin (vector-set! result i (list-ref lst i))
                   (helper (+ i 1)) )))
      (helper 0) ))

  Or you could keep track of where you were in the list, rather than doing list-ref over and over again.

  (define (list->vector lst)
    (let ((result (make-vector (length lst))))
      (define (helper lst i)
        (if (null? lst)
            result
            (begin (vector-set! result i (car lst))
                   (helper (cdr lst) (+ i 1)) )))
      (helper lst 0) ))

  Notice that either way, by defining the helper inside the let, we didn't have to pass result into the helper as an argument. I think this makes things cleaner, but it's a matter of style.

  (hide answer)

• Write vector-copy!. This is a very useful helper procedure for copying part of one vector into part of another vector. (The return value doesn't matter.) It comes up fairly often in vector problems.

  Hint: rather than use an index like you did for vector->list, use length to keep track of how much work you have left.

  > (define a (vector 1 2 3 4 5 6 7 8 9 10))
  > (define b '#(a b c d e f g h i j k))
  > (vector-copy! a 2 b 5 3)
  > a
  #(1 2 f g h 6 7 8 9 10)
  > b
  #(a b c d e f g h i j k)
  
  (define (vector-copy! dst dst-start src src-start length)

  (show answer)

  This one actually has a very straightforward recursive answer!

  (define (vector-copy! dst dst-start src src-start length)
    (if (= length 0)
        'okay
        (begin (vector-set! dst dst-start (vector-ref src src-start))
               (vector-copy! dst (+ 1 dst-start)
                             src (+ 1 src-start)
                             (- 1 length) ))))

  This solution copies the "current" item from the source to the destination, moves the source and destination indexes forward, and says "now we have one less thing to copy". There are other solutions, such as this one:

  (define (vector-copy! dst dst-start src src-start length)
    (if (= length 0)
        'okay
        (begin (vector-set! dst (+ dst-start length -1)
                            (vector-ref src (+ src-start length -1)) )
               (vector-copy! dst dst-start
                             src src-start
                             (- 1 length) ))))

  This one copies back-to-front. It never has to change src-start or dst-start, and only subtracts one from the length each time. The one tricky bit is that "off by one" in the indexes: if our length is 1 and the start index is 0, we want to copy index 0, not index 1. So we have to subtract 1. (This is a good way to check yourself, by seeing what'll happen at the beginning and end of the vector.)

  We could have easily implemented this with a helper procedure, with a single offset argument that tracked where we were and also took the -1 into account. There are many ways to implement vector-copy!.

  (hide answer)

Back to Jordy's home page | Course home page