树上的尾递归 [英] Tail-recursion on trees
问题描述
我有一个数据结构,
datatype 'a tree = Leaf | Branch of 'a tree * 'a * 'a tree
我想写一个函数,以某种顺序遍历这棵树.它做什么并不重要,所以它可能是一个 treefold : ('a * 'b -> 'b) ->'b ->'一棵树 ->'b
.我可以这样写这个函数:
and I want to write a function that traverses this tree in some order. It doesn't matter what it does, so it could be a treefold : ('a * 'b -> 'b) -> 'b -> 'a tree -> 'b
. I can write this function like this:
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
但是因为在最后一种情况下我不可避免地有两个分支,所以这不是尾递归函数.
But because I inevitably have two branches in the last case, this is not a tail-recursive function.
是否有可能创建一个,即允许扩展类型签名,并且成本是多少?我也想知道它是否值得尝试;也就是说,它在实践中是否会带来任何速度优势?
Is it possible to create one that is, given the type signature is allowed to be expanded, and at what cost? I also wonder if it's even worth trying; that is, does it give any speed benefits in practice?
推荐答案
您可以使用 continuation-passing 样式实现尾递归树状折叠:
You can achieve a tail-recursive treefold using continuation-passing style:
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.
results in n = 6 as expected.
这篇关于树上的尾递归的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!