首页 > 代码库 > 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 使用连续处理树