带延续的尾递归

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 的不同之处在于我们传递了一个接收这些值的函数而不是直接接收它们，然后我们让给我们的延续处理结果。

将延续 "return" 命名为：

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

带延续的尾递归

Tail Recursion with continuation

recursion

tail-recursion

ml