树的尾递归

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 f acc1 left
        val acc3 = f (a, acc2)
        val acc4 = treefold f acc3 right
    in acc4 end

但由于在最后一种情况下我不可避免地有两个分支，因此这不是一个尾递归函数。

如果允许扩展类型签名，是否可能创建一个尾递归函数？成本是多少？我也想知道是否值得尝试；也就是说，在实践中它是否带来任何速度优势？

- sshine

---

请查看此链接：https://dev59.com/p2ox5IYBdhLWcg3wQSKp - Dave L.

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，如预期。

- seanmcl

Answer 2

如@seanmcl所述,将函数转化为尾递归的系统方法是使用 continuation-passing 样式。

之后，您可能需要实现您的延续并使用更具体的数据类型，例如列表:

fun treefoldL f init tree =
    let fun loop Leaf acc [] = acc
          | loop Leaf acc ((x, right) :: stack) =
            loop right (f(x,acc)) stack
          | loop (Branch (left, x, right)) acc stack =
            loop left acc ((x, right) :: stack)
    in  loop tree init [] end

- kfl

---

谢谢你，Ken。我主要是因为等待其他人提问SML问题而变得不耐烦，所以想问一个人们可能喜欢回答的问题。 :) （看起来H＆R的新F#书中添加了有关continuations的新章节。） - sshine