This page tells monad savvy readers how to do monads in Scheme. It thus presumes concepts that I lack. It does, however, propose a nice challenge for the purely functional style of code. Scheme supports this style but also supports side-effects.

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:
• the new tree,
• a sort S procedure for the unused stream.
Here goes:
```(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.
Richard Uhtenwoldt’s example