chickadee » srfi-13 » string-unfold-right

This is a fundamental constructor for strings.

• G is used to generate a series of "seed" values from the initial seed: SEED, (G SEED), (G^2 SEED), (G^3 SEED), ...
• P tells us when to stop -- when it returns true when applied to one of these seed values.
• F maps each seed value to the corresponding character in the result string. These chars are assembled into the string in a right-to-left order.
• BASE is the optional initial/rightmost portion of the constructed string; it defaults to the empty string "".
• MAKE-FINAL is applied to the terminal seed value (on which P returns true) to produce the final/leftmost portion of the constructed string. It defaults to (lambda (x) "").

More precisely, the following (simple, inefficient) definitions hold:

;;; Iterative
(define (string-unfold-right p f g seed base make-final)
  (let lp ((seed seed) (ans base))
    (if (p seed) 
        (string-append (make-final seed) ans)
        (lp (g seed) (string-append (string (f seed)) ans)))))
 
;;; Recursive
(define (string-unfold-right p f g seed base make-final)
  (string-append (let recur ((seed seed))
                   (if (p seed) (make-final seed)
                       (string-append (recur (g seed))
                                      (string (f seed)))))
                 base))

Interested functional programmers may enjoy noting that string-fold and string-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

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

and

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

The final string constructed does not share storage with either BASE or the value produced by MAKE-FINAL.

Note: implementations should take care that runtime stack limits do not cause overflow when constructing large (e.g., megabyte) strings with string-unfold-right.