chickadee » srfi-1 » unfold-right

unfold-right p f g seed #!optional tailprocedure

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


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


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