lambda - 使用延续在F#中处理树

我试图理解延续的工作方式，我有一个例子，我在本书中遇到了这个例子，Tomas Petricek和Jon Skeet合着的《 Real World Functional Programming》。但这确实使我不寒而栗，所以我必须寻求一些详细的帮助。

type IntTree =
    | Leaf of int
    | Node of IntTree * IntTree

let rec sumTreeCont tree cont =
  match tree with
  | Leaf(n) -> cont(n)
  | Node(left, right) ->
      sumTreeCont left (fun leftSum ->
        sumTreeCont right (fun rightSum ->
          cont(leftSum + rightSum)))

好的，这就是我能够弄清楚自己的事情了……在第二个分支中，我们首先处理节点的左侧并传递一个lambda。这个lambda将实例化一个闭包类，其中包含两个字段right: IntTree和cont: (int -> 'a)，这两个字段将由基本案例调用。但是然后，似乎“内部lambda”捕获了leftSum，但我不太了解它们如何组合在一起，我不得不承认，当我试图弄清楚这一点时，我会有些头晕。

最佳答案

我认为Christian的答案是一个很好的答案-延续传递样式实际上只是对原始源代码所做的(不是这样)简单的机械转换。当您逐步执行此操作时，可能会更容易看到它:

1)从原始代码开始(在这里，我将代码更改为每行仅执行一次操作):

let rec sumTree tree =
   match tree with
   | Leaf(n) -> n
   | Node(left, right) ->
       let leftSum = sumTree left
       let rightSum = sumTree right
       leftSum + rightSum

2)添加延续参数并调用它而不是返回结果(这仍然不是尾递归的)。为了进行这种类型检查，我在两个子调用中都添加了fun x -> x延续，以便它们只返回总和作为结果:

let rec sumTree tree cont =
   match tree with
   | Leaf(n) -> cont n
   | Node(left, right) ->
       let leftSum = sumTree left (fun x -> x)
       let rightSum = sumTree right (fun x -> x)
       cont (leftSum + rightSum)

3)现在，让我们更改第一个递归调用以使用延续传递样式-将 body 的其余部分提升到延续中:

let rec sumTree tree cont =
   match tree with
   | Leaf(n) -> cont n
   | Node(left, right) ->
       sumTree left (fun leftSum ->
         let rightSum = sumTree right (fun x -> x)
         cont (leftSum + rightSum) )

4)对第二个递归调用重复相同的操作:

let rec sumTree tree cont =
   match tree with
   | Leaf(n) -> cont n
   | Node(left, right) ->
       sumTree left (fun leftSum ->
         sumTree right (fun rightSum ->
           cont (leftSum + rightSum) ))

关于lambda - 使用延续在F#中处理树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27712576/