1.16.2.7 Folding loops

Syntax: fold-ec x0 ?qualifier ... expression f2

Syntax: fold3-ec x0 ?qualifier ... expression f1 f2

Reduce the sequence x[1], x[2], …, x[n-1] of values obtained by evaluating expression once for each binding as specified by the ?qualifier syntaxes. The arguments x0, f2 and f1, all syntactically equivalent to expression, specify the reduction process.

(define (f2 expr knil)
  (+ knil (* expr expr)))

(fold-ec 0              ;knil
         (:range k 1 5) ;qualifier, k from 1 to 4
  k                     ;expression
  f2)
⇒ 30 ;(+ 0 (* 1 1) (* 2 2) (* 3 3) (* 4 4))

The reduction process for fold-ec is defined as follows. A reduction variable x is initialized to the value of x0, and for each k \in {1, ..., n-1} the command:

(set! x[k+1] (f2 x[k] x[k-1]))

is evaluated. Finally, x[n] is returned as the value of the comprehension.

The reduction process for fold3-ec is different:

1. If and only if the sequence is empty: x0 is evaluated and returned as the value of the comprehension.
2. If the sequence in non–empty: A reduction variable x is initialized to the value of (f1 x[1]), and for each k \in {2, ..., n-1} the command:

   (set! x[k+1] (f2 x[k] x[k-1]))
   

   is evaluated; finally, x[n] is returned as the value of the comprehension.

Example:

(define (f2 expr knil)
  (+ knil (* expr expr)))

(define (f1 x)
  x)

(fold3-ec 1234                  ;never used
          (:range k 2 5)        ;k from 2 to 4
  k                             ;expression
  f1
  f2)
⇒ 27 ;(+ (f1 2) (* 3 3) (* 4 4))

(fold3-ec 1234
          (:range k 2 2)        ;loop zero times
  k
  f1
  f2)
⇒ 1234

As the order of the arguments suggests, x0 is evaluated outside the scope of the qualifiers, whereas the reduction expressions involving f1 and f2 are inside the scope of the qualifiers (so they may depend on any variable introduced by the qualifiers). Note that f2 is evaluated repeatedly, with any side–effect or overhead this might have.

The main purpose of these comprehensions is implementing other comprehensions as special cases. They are generalizations of the procedures fold-left and reduce. Note that fold3-ec is defined such that x0 is only evaluated in case the sequence is empty. This allows raising an error for the empty sequence.