Tail Recursion mit Fortführung

Question

Wie würden Sie den folgenden ML-Code in eine Tail rekursive Funktion konvertieren? Ich habe es angeschaut und versucht, es für ein paar Stunden herauszufinden, und ich kann nicht sehen, wie.

datatype Tree = NULL | NODE of Tree*Tree | VAL of int; 
fun dup(NULL) = NULL 
| dup(VAL(y)) = NODE(VAL(y),VAL(y)) 
| dup(NODE(y1,y2)) = NODE(dup(y1), dup(y2)); 

Answer 1

Transforming zu Continuation-Übertragungsstil ist (relativ) einfach hier - die Rekursion der schwierige Fall ist.

Das Umschreiben der rechten Seite erleichtert manchmal das Erkennen eines Musters.

| dup (NODE (y1, y2)) = let val left = dup y1 
          val right = dup y2 
         in 
          NODE (left, right) 

Wir brauchen sowohl left und right und kombinieren sie danach greifen.
Der Unterschied in CPS besteht darin, dass wir eine Funktion weitergeben, die diese Werte empfängt, anstatt sie direkt zu empfangen, und dann lassen wir die Fortsetzung, die uns gegeben wurde, mit dem Ergebnis umgehen.

Benennen der Fortsetzung "Rückkehr", kann es wie folgt aussehen:

fun dup_cont NULL return = return NULL (* Trivial *) 
    (* duplicate the value and return it *) 
    | dup_cont (VAL y) return = return (NODE (VAL y, VAL y)) 
    (* recurse, grab the result. 
     recurse again, grab result. 
     combine the two results and return *) 
    | dup_cont (NODE (y1, y2)) return = 
     dup_cont y1 (fn left => dup_cont y2 (fn right => return (NODE (left, right))))