recursion - 计算树中的节点

Question

与 f# 打架 - 打架是在树的领域 - 特别是计算节点数。这是真正有趣的，因为我最终想用 F# 编写的程序涉及多路树，不幸的是它的开始有点麻烦 - 我希望你能提供帮助!

99 f# 系列的第 61 题，要求计算二叉树的叶子数。解决方案(下面给出)计算节点，但我的问题是不理解

• 双重递归如何工作循环左(有趣的 lacc -> 循环右..)

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

  <

• loop t id id 是类型 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

Answer 1

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

定义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 函数定义的。这个函数很有趣，因为它是使用 continuation passing style 定义的。 .在 CPS 中，每个函数都有一个额外的“延续”函数，该函数传递计算结果并负责决定接下来会发生什么。请注意，loop 是尾递归的，因此避免了 foldTreeNaive 的溢出问题。

loop 函数的类型是:

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

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

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

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

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

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

loop 函数随后由 foldTree 函数在以下行中调用:

loop t id

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

您可能还会找到 this description of fold for binary trees有用。