In a sense, the binding of a new variable n introduces an implicit box that will get filled in at some point. So because we have letrec binding semantics, we can use the same box as both an output and an input to the replaceMin function. But the box can only be filled once; if, in the process of computing the value to be placed in the box, we end up having to use the value in the box, we end up with a dependency cycle and then loop. This program works because the box gets set at the end of the computation, and doesn't get used until after that point.minTree t = t'

where (n, t') = replaceMin t n

replaceMin (Leaf n) m = (n, Leaf m)

replaceMin (Node t1 t2) m = (n, Node t1' t2')

where (n1, t1') = replaceMin t1 m

(n2, t2') = replaceMin t2 m

n = min n1 n2

We can explicitly encode the order of the computation using continuations. I'll use Scheme now just to show there's no hidden reliance on laziness anymore.

Now you can see exactly when we set the value of the box--after the computation finishes--and that we don't do anything with the returned "min-computations" except embed them in larger min-computations until after the traversal, when we run the final computation.(define (min-tree t n)

(let ([m (box #f)])

(match-let ([(n . t*) (replace/min t m)])

(set-box! m (n identity))

t*)))

(define (replace/min t m)

(match t

[($ Leaf n)

(cons (lambda (k) (k n)) (make-Leaf m))]

[($ Node t1 t2)

(match-let ([(k1 . t1*) (replace/min t1 m)]

[(k2 . t2*) (replace/min t2 m)])

(cons (lambda (k)

(k1 (lambda (n1)

(k2 (lambda (n2)

(k (min n1 n2)))))))

(make-Node t1* t2*)))]))

## No comments:

Post a Comment