I adapt the challenge here as follows.
Suppose we have a sort S of scheme procedure that takes no arguments and returns a pair of a character and a procedure of sort S.
A sort S procedure thus produces a character stream sequentially:
(car (s)), (car ((cdr (s)))), (car ((cdr ((cdr (s)))))), ...
For example st0 below is such a procedure yielding “pusillanimous pusillanimous ...”:
(define (st0) (let* ((st "pusillanimous ") (l (- (string-length st) 1))) (let s ((n 0)) (cons (string-ref st n) (lambda () (s (if (= n l) 0 (+ n 1))))))))We are to build a depth n binary tree with the letters of the stream as leaves. A binary tree of depth n and 3 as leaves can be built with
(define n 4) (let bt ((k n)) (if (zero? k) 3 (cons (bt (- k 1))(bt (- k 1)))))That was easy but for the real problem we must specify in our code which branch of a sub tree is to have the early stream characters. Our recursive procedure takes a sort S procedure and returns a pair of values:
(let bt ((k n)(stx st0)) (if (zero? k) (stx) (let* ((lst (bt (- k 1) stx))(rst (bt (- k 1) (cdr lst)))) (cons (cons (car lst) (car rst)) (cdr rst)))))which yields:
(((((#\p . #\u) #\s . #\i) (#\l . #\l) #\a . #\n) ((#\i . #\m) #\o . #\u) (#\s . #\space) #\p . #\u) . #Perhaps we should lop off the remaining procedure but I won't. I think this is in the monad spirit, but not yet in the monad style. It hands around the stream generator awkwardly. It is easier in Ocaml, but still awkward. I find code such as this easier to write than to read.)