作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我有一个数据结构,
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
但是因为我在最后一种情况下不可避免地有两个分支,所以这不是尾递归函数。
如果允许扩展类型签名,是否可以创建一个,代价是什么?我也想知道它是否值得尝试;也就是说,它在实践中会带来任何速度优势吗?
最佳答案
您可以使用连续传递样式实现尾递归树折叠:
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。
关于functional-programming - 树上的尾递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19070577/
我是一名优秀的程序员,十分优秀!