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