chickadee » srfi-116 » iunfold

iunfold p f g seed #!optional tail-genprocedure

iunfold is best described by its basic recursion:

(iunfold p f g seed) =
    (if (p seed) (tail-gen seed)
        (ipair (f seed)
              (iunfold p f g (g seed))))
Determines when to stop unfolding.
Maps each seed value to the corresponding ilist element.
Maps each seed value to next seed value.
The "state" value for the unfold.
Creates the tail of the ilist; defaults to (lambda (x) '())

In other words, we use g to generate a sequence of seed values seed, (g seed), (g2 seed), (g3 seed), ... These seed values are mapped to ilist elements by f, producing the elements of the result ilist in a left-to-right order. P says when to stop (i.e. when it returns true the procedure ends).

iunfold is the fundamental recursive ilist constructor, just as ifold-right is the fundamental recursive ilist consumer. While iunfold may seem a bit abstract to novice functional programmers, it can be used in a number of ways:

;; Ilist of squares: 1^2 ... 10^2
(iunfold (lambda (x) (> x 10))
        (lambda (x) (* x x))
    (lambda (x) (+ x 1))

(iunfold null-ilist? icar icdr lis) ; Copy a proper ilist.

;; Read current input port into an ilist of values.
(iunfold eof-object? values (lambda (x) (read)) (read))

;; Copy a possibly non-proper ilist:
(iunfold not-ipair? icar icdr lis

;; Append HEAD onto TAIL:
(iunfold null-ilist? icar icdr head
              (lambda (x) tail))

Interested functional programmers may enjoy noting that ifold-right and iunfold 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


(ifold-right kons knil (iunfold knull? kar kdr x)) ;=> x ;AND
(iunfold knull? kar kdr (ifold-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."