24.7.3 Unfolding vectors

Function: vector-unfold stop? seed->item make-seed first-seed

Function: vector-unfold stop? seed->item make-seed first-seed base-vector

Function: vector-unfold stop? seed->item make-seed first-seed base-vector make-final

This is a fundamental constructor for vectors. Arguments description follows.

make-seed

A map function used to generate a series of “seed” values from the initial seed:

first-seed
(make-seed first-seed)            ⇒ seed2
(make-seed seed2)                 ⇒ seed3
(make-seed seed3)                 ⇒ seed4
...

stop?

A predicate function telling when to stop generating items: When it returns true when applied to one of the seed values.

seed->item

Map function mapping each seed value to the corresponding item in the result vector. These items are assembled into the vector in a left–to–right order.

base

An optional vector which is used as initial/leftmost portion of the constructed vector. Defaults to the empty vector.

make-final

Optional function applied to the terminal seed value (on which stop? returns true) to produce the final/rightmost portion of the constructed vector. Defaults to (lambda (x) '#()).

More precisely, the following (simple, inefficient) definitions hold:

;; iterative
(define (vector-unfold stop? seed->item make-seed
                       first-seed base-vector make-final)
  (let loop ((seed    first-seed)
             (result  base-vector))
    (if (stop? seed)
        (vector-append result (make-final seed))
      (loop (make-seed seed)
            (vector-append result
                           (vector (seed->item seed)))))))

;; recursive
(define (vector-unfold stop? seed->item make-seed
                       first-seed base-vector make-final)
  (vector-append
     base-vector
     (let loop ((seed first-seed))
       (if (stop? seed)
           (make-final seed)
         (vector-append (vector (seed->item seed))
                        (loop (make-seed seed)))))))

This function is a fairly powerful vector constructor; we can use it to convert a list to a vector, read a port into a vector, reverse a vector, copy a vector, and so forth. Examples:

(port->vector p) = (vector-unfold eof-object? values
                                  (lambda (x) (read-item p))
                                  (read-item p))

(list->vector lis) = (vector-unfold null? car cdr lis)

(vector-tabulate f size) = (vector-unfold (lambda (i)
                                            (= i size))
                                          f add1 0)

to map proc over a list lis, producing a vector:

(vector-unfold null? (compose proc car) cdr lis)

Interested functional programmers may enjoy noting that vector-fold-right and vector-unfold are in some sense inverses. That is, given operations knull?, kar, kdr, combine, and knil satisfying:

(combine (kar x) (kdr x)) ⇒ x
(knull? knil) ⇒ #t

then:

(vector-fold-right combine knil
                   (vector-unfold knull? kar kdr x))
⇒ x

and:

(vector-unfold knull? kar kdr
               (vector-fold-right combine knil s))
⇒ s

The final vector constructed does not share storage with either base-vector or the value produced by make-final.

Function: vector-unfold-right stop? seed->item make-seed first-seed

Function: vector-unfold-right stop? seed->item make-seed first-seed base-vector

Function: vector-unfold-right stop? seed->item make-seed first-seed base-vector make-final

This is a fundamental constructor for vectors. The arguments are like the ones of vector-unfold. The difference from vector-unfold is that this function builds the vector from right to left; more precisely, the following (simple, inefficient) definitions hold:

;; iterative
(define (vector-unfold-right
           stop? seed->item make-seed
           first-seed base-vector make-final)
  (let lp ((seed    first-seed)
           (result  base))
    (if (stop? seed)
        (vector-append (make-final seed) result)
      (loop (make-seed seed)
            (vector-append (vector (seed->item seed))
                           result)))))

;; recursive
(define (vector-unfold-right
           stop? seed->item make-seed
           first-seed base-vector make-final)
  (vector-append
     (let loop ((seed first-seed))
       (if (stop? seed)
           (make-final seed)
         (vector-append (loop (make-seed seed))
                        (vector (seed->item seed)))))
     base))

Interested functional programmers may enjoy noting that vector-fold and vector-unfold-right are in some sense inverses. That is, given operations knull?, kar, kdr, kons, and knil satisfying:

(kons (kar x) (kdr x)) ⇒ x
(knull? knil) ⇒ #t

then:

(vector-fold kons knil
             (vector-unfold-right knull? kar kdr x))
⇒ x

and:

(vector-unfold-right knull? kar kdr
                     (vector-fold kons knil s))
⇒ s

The final vector constructed does not share storage with either base-vector or the value produced by make-final.