SML/NJ 中的树尾递归

Question

我有一个定义树的函数：

datatype 'a tree = leaf of 'a |
                node of 'a tree * 'a tree;
fun cat(leaf(s)) = s
  | cat(node(t1,t2)) = cat(t1) ^ " " ^ cat(t2);

cat 函数用于将字符串输入连接到字符串树。我知道它不是尾递归，因为定义使用函数本身进行递归。现在我在想有没有办法以尾递归的方式制作它？提前感谢任何帮助。

Answer 1

这将是尾递归版本

fun cat'(leaf(s), acc) = s^acc
  | cat'(node(t1, node(t2, acc))

您也可以将其作为延续传递样式函数

fun cat'' (leaf(s)) k = k(s)
  | cat'' (node(t1, t2)) k = cat''(t1) (fn res => k(res ^ cat''(t2)))

希望这有帮助！！ :D