2

与 f# 战斗 - 战斗在树的领域 - 专门计算节点的数量。这是真正有趣的，因为我想最终在 F# 中编码的程序涉及多路树，不幸的是它的开始有点麻烦 - 我希望你能提供帮助！

99 f# 系列的第 61 题，要求计算二叉树的叶子。解决方案（如下所示）计算节点，但我的问题是不理解

  • 双递归的工作原理向左循环（有趣的 lacc -> 向右循环..）

  • 什么cont (branchF x lacc racc)是，我的印象是 cont 是“abc”函数，但这只需要两个参数......

  • loop t idid 的类型是 unit - 我不明白这是如何暗示的

基本上不理解这一点，或者它在树中流动的顺序（调试和单步执行没有帮助）如果有更简单的示例、预读建议等，请指导我。

非常感谢您的帮助，有问题的解决方案代码如下：

干杯

时间

type 'a Tree = Empty | Branch of 'a * 'a Tree * 'a Tree

let foldTree branchF emptyV t =
    let rec loop t cont =
        match t with
        | Empty ->
            cont emptyV
        | Branch (x, left, right) ->
            loop left  (fun lacc -> 
                loop right (fun racc ->
                    cont (branchF x lacc racc)))
    loop t id

let counLeaves tree =
    foldTree (fun abc lc rc ->
        if lc + rc = 0 then 1
        else 1 + lc + rc) 0 tree

let Tree1 = Branch ('x', Branch ('x', Empty, Empty),Branch ('x', Empty, Branch ('x', Empty, Branch ('x', Empty, Empty))))


let result = counLeaves Tree1
4

1 回答 1

7

顾名思义，foldTree定义了自定义Tree类型之上的折叠函数。

定义 a 的一种天真的方法foldTree可能是：

let rec foldTreeNaive accFun init = function
    | Empty -> init
    | Branch (x, left, right) ->
        let lacc = foldTreeNaive accFun init left
        let racc = foldTreeNaive accFun init right
        accFun x lacc racc

这个函数的问题是，如果被折叠的树很深，它可能会进行非常深的递归调用，因为在调用累加器函数之前，节点的递归调用必须完成。例如以下导致堆栈溢出异常：

let unbalanced = [1..100000] |> List.fold (fun t i -> Branch(i, t, Empty)) Empty
let nodeCount = foldTreeNaive (fun _ lc rc -> lc + rc + 1) 0 unbalanced

避免这种堆栈溢出的常用方法是使函数尾部递归，但是在这种情况下这似乎是不可能的，因为要进行两次递归调用，而不是折叠列表时所需的一次。

foldTree是使用局部loop函数定义的。这个函数很有趣，因为它是使用延续传递样式定义的。在 CPS 中，每个函数都有一个附加的“延续”函数，该函数传递计算结果并负责决定接下来会发生什么。请注意，它loop是尾递归的，因此避免了foldTreeNaive.

函数的类型loop是：

Tree<'a> -> ('b -> 'c) -> 'c

其中'a是树中节点的类型，'b是累加器类型，'c是延续函数的结果。

在叶节点的情况下，将传递给函数的空累加器值传递给延续foldTree。

在这种情况下折叠非空树时Branch，折叠的结果取决于左右子树的结果。这是递归完成的，首先折叠左子树，然后折叠右子树。对于左子树上的递归调用，loop必须建立一个新的延续来接收结果，这是

(fun lacc -> 
    loop right (fun racc ->
        cont (branchF x lacc racc))

功能。这个延续所做的是对右子树进行递归调用，传递另一个延续来接收折叠的结果。当调用该延续时，左子树和右子树的结果在lacc和中可用racc。此时，可以使用当前节点的值和左右子树的结果调用节点的累积函数。然后将此函数的结果传递给传递给的原始延续loop。

然后该loop函数由该行中的函数调用foldTree：

loop t id

这里，id是接收树根节点折叠结果的延续。由于这是所需的值，因此id只需返回其参数而不进行修改。

您可能还会发现这种对二叉树折叠的描述很有用。

于 2013-02-27T09:34:51.387 回答