chickadee » srfi-116 » iunfold

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

p

Determines when to stop unfolding.

f

Maps each seed value to the corresponding ilist element.

g

Maps each seed value to next seed value.

seed

The "state" value for the unfold.

tail-gen

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

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

then

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