在树上进行尾递归 [英] Tail-recursion on trees

问题描述

我有一个数据结构，

  datatype'a tree = Leaf | 'a tree *'a *'a tree的分支
  

我想写一个遍历函数这棵树以某种顺序。它并不重要，它可以是 treefold：（'a *'b - >'b） - > 'b - > '树 - > B 。我可以这样写这个函数：

  fun treefold f acc1 Leaf = acc1 
 | treefold f acc1（Branch（left，a，right））= 
 let val acc2 = treefold acc1 left $ b $ val val acc3 = f（a，acc2）
 val acc4 = treefold acc3 right $ b acc4中的$ b结尾
  

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

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

解决方案

您可以使用延续传递样式来实现尾递归树形折叠：

  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）
 
 funf treefold ftb = treefold1 ftb（fn x => x）
  

例如：

  fun sumtree t = treefold op + t 0 
 
 val t1 =分支（分支（Leaf，1，Leaf）， 2，Branch（Leaf，3，Leaf））
 
 val n = sumtree t1 
  

如预期的那样导致n = 6。

I have a data structure,

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

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

解决方案

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)

For example:

fun sumtree t = treefold op+ t 0

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

val n = sumtree t1

results in n = 6 as expected.

这篇关于在树上进行尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！