Given a tree whose leaves are labeled by numbers, let us replace every label by the minimum label without traversing the tree twice.
type tree = Leaf of int | Branch of tree * tree;;
let repmin (t:tree) : tree =
let present = ref max_int in
let make = .!.<fun future -> .~(
let rec process = function
| Leaf x ->
present := min x !present;
.<Leaf future>.
| Branch (t1,t2) ->
.<Branch (.~(process t1), .~(process t2))>.
in process t)>. in
make !present;;
repmin (Branch (Branch (Leaf 1, Leaf 2), Leaf 3));;
(* Branch (Branch (Leaf 1, Leaf 1), Leaf 1) *)
Julia L. Lawall, 2001. Implementing circularity using partial evaluation. In Proceedings of PADO 2001: 2nd symposium on programs as data objects, ed. Olivier Danvy and Andrzej Filinski, 84–102. Lecture Notes in Computer Science 2053. (slides)