chickadee » srfi-1 » unfold-right

unfold-right constructs a list with the following loop:

(let lp ((seed seed) (lis tail))
  (if (p seed) lis
      (lp (g seed)
          (cons (f seed) lis))))

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

list terminator; defaults to '().

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 right-to-left order. P says when to stop.

unfold-right is the fundamental iterative list constructor, just as fold is the fundamental iterative list consumer. While unfold-right 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-right zero? 
              (lambda (x) (* x x))
              (lambda (x) (- x 1))
              10)
	
;; Reverse a proper list.
(unfold-right null-list? car cdr lis)
 
;; Read current input port into a list of values.
(unfold-right eof-object? values (lambda (x) (read)) (read))
 
;; (append-reverse rev-head tail)
(unfold-right null-list? car cdr rev-head tail)

Interested functional programmers may enjoy noting that fold and unfold-right 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 KONS KNIL (unfold-right KNULL? KAR KDR X)) = X

and

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

This combinator presumably has some pretentious mathematical name; interested readers are invited to communicate it to the author.