计算树中的节点

Question

与f#战斗 - 战斗在树的领域 - 特别是计算节点的数量.这是真正令人感兴趣的,因为我想最终在F#中编写的程序涉及多路树,不幸的是它开始有点麻烦 - 我希望你能提供帮助!

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

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

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

• loop t id id是单位类型 - 我不知道这是如何隐含的

基本上不理解这个,或者它在树中流动的顺序(调试和步骤通过不证明有用)如果有更简单的例子,预读推荐等,那么请指导我们.

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

干杯

TD

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是使用local loop函数定义的.这个函数很有趣,因为它是使用continuation传递样式定义的.在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只返回其参数而不进行修改.

您可能还会发现二进制树的折叠描述很有用.