chickadee » srfi-1 » unfold

unfold p f g seed #!optional tail-genprocedure

unfold is best described by its basic recursion:

(unfold P F G SEED) = 
    (if (P SEED) (TAIL-GEN SEED)
        (cons (F SEED)
              (unfold P F G (G SEED))))
Determines when to stop unfolding.
Maps each seed value to the corresponding list element.
Maps each seed value to next seed value.
The "state" value for the unfold.
Creates the tail of the list; defaults to (lambda (x) '())

In other words, we use G to generate a sequence of seed values

SEED, G(SEED), G^2(SEED), G^3(SEED), ...

These seed values are mapped to list elements by F, producing the elements of the result list in a left-to-right order. P says when to stop.

unfold is the fundamental recursive list constructor, just as fold-right is the fundamental recursive list consumer. 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 ... 10^2
(unfold (lambda (x) (> x 10))
        (lambda (x) (* x x))
	(lambda (x) (+ x 1))
(unfold null-list? car cdr lis) ; Copy a proper list.
;; 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 lis 
;; Append HEAD onto TAIL:
(unfold null-list? car cdr head 
              (lambda (x) tail))

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


(fold-right KONS KNIL (unfold KNULL? KAR KDR X)) = X


(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."