chickadee » srfi-13 » string-unfold

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 left-to-right order.
• BASE is the optional initial/leftmost 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/rightmost portion of the constructed string. It defaults to (lambda (x) "").

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

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

string-unfold is a fairly powerful string constructor -- you can use it to convert a list to a string, read a port into a string, reverse a string, copy a string, and so forth. Examples:

(port->string p) = (string-unfold eof-object? values
                                  (lambda (x) (read-char p))
                                  (read-char p))
 
(list->string lis) = (string-unfold null? car cdr lis)
 
(string-tabulate f size) = (string-unfold (lambda (i) (= i size)) f add1 0)

To map F over a list LIS, producing a string:

(string-unfold null? (compose f car) cdr lis)

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

and

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

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

This combinator sometimes is called an "anamorphism."

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