尾遞歸連續

Question

如何將下面的ML代碼轉換爲尾遞歸函數？我盯着它，試圖弄清楚幾個小時，我看不出如何。

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

轉化來延續傳遞風格（相對）簡單的在這裏 - 遞歸是棘手的情況。

重寫右側有時會更容易看到圖案。

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

我們需要抓住這兩個left和right並隨後將它們結合起來。
CPS的不同之處在於我們傳遞的是一個接收這些值的函數，而不是直接接收這些值，然後讓我們繼續處理結果。

命名延續 「迴歸」，它可以是這樣的：

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))))