尾递归在树上

我有一个数据结构，尾递归在树上

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

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

是否有可能创建一个，即允许类型签名被允许扩展以及花费多少？我也怀疑它是否值得尝试;也就是说，它在实践中是否会带来速度上的好处？

来源

2013-09-28 Simon Shine

看到这个：http://stackoverflow.com/questions/9323036/tail-递归函数查找树的深度 – david

可以使用延续传递风格实现尾递归treefold：

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。

来源

2013-09-29 13:45:28 seanmcl

像@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

来源

2013-10-06 19:43:23 kfl

谢谢，肯。我最主要的问题是因为我变得急躁潜伏在其他人问SML问题，并认为我会问一个人们可能想回答的问题。 :)（H＆R的新F＃书中似乎增加了有关延续的新章节。） –

尾递归在树上

回答

相关问题