在树上的尾递归

Question

我有一个数据结构,

datatype 'a tree = Leaf | Branch of 'a tree * 'a * 'a tree

我想编写一个以某种顺序遍历此树的函数.无论它做什么都没关系,所以它可能是一个treefold : ('a * 'b -> 'b) -> 'b -> 'a tree -> 'b.我可以像这样编写这个函数:

fun treefold f acc1 Leaf = acc1
  | treefold f acc1 (Branch (left, a, right)) =
    let val acc2 = treefold acc1 left
        val acc3 = f (a, acc2)
        val acc4 = treefold acc3 right
    in acc4 end

但是因为在最后一种情况下我不可避免地有两个分支,所以这不是尾递归函数.

是否有可能创建一个,因为允许扩展类型签名,并且成本是多少？我也想知道它是否值得尝试; 也就是说,它在实践中是否提供任何速度优势？

Answer 1

您可以使用延续传递样式实现尾递归树折:

fun treefold1 f Leaf acc k = k acc
  | treefold1 f (Branch (left, a, right)) acc k =
    treefold1 f left acc (fn x => treefold1 f right (f(a, x)) k)

fun treefold f t b = treefold1 f t b (fn x => x)

例如:

fun sumtree t = treefold op+ t 0

val t1 = Branch (Branch(Leaf, 1, Leaf), 2, Branch (Leaf, 3, Leaf))

val n = sumtree t1

结果如预期的那样n = 6.