chickadee » srfi-1 » unfold

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))))

P

Determines when to stop unfolding.

F

Maps each seed value to the corresponding list element.

G

Maps each seed value to next seed value.

SEED

The "state" value for the unfold.

TAIL-GEN

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))
	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 
              values)
 
;; 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

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