Hello Chung-chieh!

This is a nice algorithm, but I’m not sure I understand why you claim
that it avoids traversing the tree twice. Let’s look at an example.
Assume t is the following tree.

(Branch (Branch (Leaf 1, Leaf 2), Leaf 3))

then ( repmin t ) reduces in a couple of steps to

  let make =                                                                                                        
    .! .< fun future ->                                                                                             
       (Branch (Branch (Leaf future, Leaf future), Leaf future)) >.                                                 
  in                                                                                                                
    make 1

which reduces to (modulo some simplification):

let make future = (Branch (Branch (Leaf future, Leaf future), Leaf future))                                       
    in make 1

Now to execute (make 1) you will have to traverse the tree

(Branch (Branch (Leaf future, Leaf future), Leaf future)).

If that’s the case the difference between the obvious
non-meta-programming algorithm for implementing the specification and
your proposed algorithm is not in the number of tree traversals, but
in how many of these traversals have to be programmed explicitly.

Martin