首页 > 代码库 > 10.3.2.1 使用连续处理树

10.3.2.1 使用连续处理树

10.3.2.1 使用连续处理树

 

要把我们以前实现的 sumTree 函数,转变成使用连续的版本,首先,要给这个函数添加一个额外的参数(连续);其次,还需要改变函数返回结果的方式,不是简单地返回值,而是把它作为参数值,给连续进行调用。 清单 10.18 是代码的最终版本。

 

清单 10.18 使用连续,计算树中元素的和 (F# Interactive)

> let rec sumTreeCont tree cont = 

     match tree with 

     | Leaf(num) -> cont(num) 

     | Node(left, right) –> 

       sumTreeCont left (fun leftSum ->   [1]

         sumTreeCont right (fun rightSum –>    [2]

           cont(leftSum + rightSum)));;     [3]

val sumTreeCont : IntTree -> (int ->‘a) –> ‘a

 

修改叶子的分支很容易,因为它以前就是从叶子返回值。第二种情况就重要得多,我们使用的模式相似于前面的 C# 示例。我们调用函数计算左子树元素的的和[1](这是尾递归),并把 lambda 函数作为它的第二个参数值。在 lambda 函数的内部,我们对右子树做类似的事情[2](也是尾递归调用)。一旦我们有两个子树的和,就把它作为参数,调用最初得到的连续,(这还是尾递归调用)。

对于我们刚刚写的这个函数,还有一件重要的事情,就是它的类型签名。通常,我们不需要显式写出任何类型,F# 会为我们推断出类型。这个函数把树作为第一个参数,连续作为第二参数。现在,连续的类型为 int –>‘a,函数的整体结果是 ‘a;换句话说,整个函数的返回类型与连续的返回类型相同。

前面我们提到过,在代码中,所有递归调用现在都是尾递归,所以,我们可以在不平衡树上尝试这个函数,在以前的版本中是失败的:

 

> sumTreeCont imbalancedTree (fun r –> 

     printfn "Result is: %d" r);; 

Result is: 8736 

val it : unit = ()

 

> sumTreeCont imbalancedTree (fun a-> a);;   <-- 从连续中返回和

val it : int = 8736

 

可以看到,现在的代码可以运行非常大的树,而没有任何麻烦。第一个示例,我们直接在连续中打印出结果,连续不返回任何值,所以,表达式的整体结果是 unit;在第二种情况下,我们给它一个恒等函数(返回值就是参数值的函数)作为连续。恒等函数在 F# 库中已经有了,所以,我们可以写 id。 连续返回类型是 int,从调用 sumTreeCont 返回的值就是树中所有元素的和。

10.3.2.1 使用连续处理树