23.8.7 Unfolding

Function: unfold stop? map-to-elm seed-step first-seed

Function: unfold stop? map-to-elm seed-step first-seed tail-gen

Syntax: unfold/stx stop? map-to-elm seed-step first-seed

Syntax: unfold/stx stop? map-to-elm seed-step first-seed tail-gen

Generate a list from a starting value; return the result. It is is the fundamental recursive list constructor, just as fold-right is the fundamental recursive list consumer. It is best described by its basic recursion:

(unfold stop? map-to-elm seed-step seed tail-gen) =
    (if (stop? seed)
        (tail-gen seed)
      (cons (map-to-elm seed)
            (unfold stop? map-to-elm
                    seed-step (seed-step seed)
                    tail-gen)))

The arguments are:

stop?

Determines when to stop: it is applied to the current seed value, and if the return value is #t: unfolding stops. If it evaluates to #t at the first invocation: the return value of unfold is the return value of tail-gen.

map-to-elm

Maps each seed value to the corresponding list element. It is applied to the current seed value and must return the value to append to the result list.

seed-step

Maps each seed value to next seed value.

first-seed

The “state” value for the unfold. It is the first seed value.

tail-gen

Applied to the seed value that caused stop? to return #t, must return the tail of the result list. Defaults to (lambda (x) '()).

While unfold may seem a bit abstract to novice functional programmers, it can be used in a number of ways:

;; List of squares: 1^2 ... 5^2
(unfold (lambda (x) (> x 5))
        (lambda (x) (* x x))
        (lambda (x) (+ x 1))
        1)
⇒ (1 4 9 16 25)

;; Copy a proper list.
(unfold null-list? car cdr '(1 2 3 4 5))
⇒ (1 2 3 4 5)

;; Read current input port into a list of values.
(unfold eof-object? values (lambda (x) (read)) (read))

;; Copy a possibly non-proper list:
(unfold not-pair? car cdr '(1 2 3 4 . 5) values)
⇒ (1 2 3 4 . 5)

;; Append HEAD onto TAIL:
(unfold null-list? car cdr '(1 2 3) (lambda (x) '(4 5 6)))
⇒ (1 2 3 4 5 6)

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

(kons (kar x) (kdr x)) = x and (knull? knil) = #t

then:

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

and:

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

This combinator sometimes is called an “anamorphism”; when an explicit tail-gen procedure is supplied, it is called an “apomorphism”.

Function: unfold-right stop? map-to-elm seed-step first-seed

Function: unfold-right stop? map-to-elm seed-step first-seed tail

Syntax: unfold-right/stx stop? map-to-elm seed-step first-seed

Syntax: unfold-right/stx stop? map-to-elm seed-step first-seed tail

Generate a list from a starting value; return the result. It is the fundamental iterative list constructor, just as fold is the fundamental iterative list consumer. Construct a list with the following loop:

(let loop ((seed seed)
           (ell  tail))
  (if (stop? seed)
      ell
    (loop (seed-step seed)
          (cons (map-to-elm seed) ell))))

Arguments are:

stop?

Determine when to stop unfolding.

map-to-elm

Map each seed value to the corresponding list element.

seed-step

Map each seed value to next seed value.

first-seed

The “state” value for the unfold.

tail

List terminator; defaults to '().

While unfold-right may seem a bit abstract to novice functional programmers, it can be used in a number of ways:

;; List of squares: 1^2 ... 10^2
(unfold-right zero?
              (lambda (x) (* x x))
              (lambda (x) (- x 1))
              5)
⇒ (1 4 9 16 25)

;; Reverse a proper list.
(unfold-right null-list? car cdr '(1 2 3 4 5))
⇒ (5 4 3 2 1)

;; Read current input port into a list of values.
(unfold-right eof-object? values (lambda (x) (read)) (read))

;; Equivalent to: (append-reverse rev-head tail)
(unfold-right null-list? car cdr '(3 2 1) '(4 5 6))
⇒ (1 2 3 4 5 6)

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

(kons (kar x) (kdr x)) = x and (knull? knil) = #t

then:

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

and:

(unfold-right knull? kar kdr (fold kons knil x)) = x.

This combinator presumably has some pretentious mathematical name; interested readers are invited to communicate it to the author.