使用连续传递样式简化多路树遍历

Question

我着迷于the approach used in this blog post使用CPS遍历玫瑰树a.k.a多路树a.k.an叉树。

这是我的代码，删除了类型注释并更改了名称，这是我在尝试理解该技术时所做的：

type 'a Tree = Node of 'a * 'a Tree list | Leaf of 'a

let rec reduce recCalls cont =
    match recCalls with
    | [] -> [] |> cont 
    | findMaxCall :: pendingCalls ->
        findMaxCall (fun maxAtNode ->
                    reduce pendingCalls (fun maxVals -> maxAtNode :: maxVals |> cont))
        
let findMaxOf (roseTree : int Tree) =
    let rec findMax tr cont =
        match tr with
        | Leaf i -> i |> cont
        | Node (i, chld) ->
            let recCalls = chld |> List.map findMax 
            reduce recCalls (fun maxVals -> List.max (i :: maxVals) |> cont)
    findMax roseTree id 
    
// test it
let FindMaxOfRoseTree =
    let t = Node (1, [ Leaf 2; Leaf 3 ])
    let maxOf = findMaxOf t //will be 3
    maxOf

我的问题是，我发现这种方法很难遵循。相互递归（假设这是正确的术语）对我的傻瓜大脑来说真的很聪明，但我在试图理解它是如何工作的时候迷路了，即使是在使用简单的例子和手动写下步骤等时也是如此。

我需要对 Rose 树使用 CPS，我将进行需要 CPS 的遍历，因为就像这个例子一样，基于我的树节点的计算结果需要首先计算节点。无论如何，我喜欢CPS，我想提高对它的理解。

所以我的问题是：有没有一种在玫瑰树上实施 CPS 的替代方法，我可以设法更好地理解？有没有办法重构上面的代码，让它更容易理解（消除相互递归？）

如果有上述方法的名称，或者一些resources/books我可以阅读以更好地理解它，也欢迎提供提示。

Answer 1

CPS 肯定会令人困惑，但您可以做一些事情来简化此代码：

从您的类型中删除 Leaf 大小写，因为它是多余的。叶子只是一个 Node 和一个空的子列表。
将通用 CPS 逻辑与玫瑰树专用逻辑分开。
使用 continuation monad 来简化 CPS 代码。

首先，让我们定义 :

type ContinuationMonad() =
    member __.Bind(m, f) = fun c -> m (fun a -> f a c)
    member __.Return(x) = fun k -> k x

let cont = ContinuationMonad()

使用这个构建器，我们可以定义一个通用的 CPS reduce 函数，它将“不完整”计算的列表组合成一个单独的不完整计算（其中不完整计算是任何需要连续的函数输入 't -> 'u 并使用它来生成类型 'u).

的值

let rec reduce fs =
    cont {
        match fs with
        | [] -> return []
        | head :: tail ->
            let! result = head
            let! results = reduce tail
            return result :: results
    }

我认为这当然更清楚，但它可能看起来像魔术。理解此构建器的 let! x = f 的关键是 x 是传递给 f 的隐含延续的值。这使我们能够摆脱大量的 lambda 和嵌套的括号。

现在我们准备好处理玫瑰树了。这是简化的类型定义：

type 'a Tree = Node of 'a * 'a Tree list

let leaf a = Node (a, [])

现在查找树中的最大值如下所示：

let rec findMax (Node (i, chld)) =
    cont {
        let! maxVals = chld |> List.map findMax |> reduce
        return List.max (i :: maxVals)
    }

注意这里没有相互递归。 reduce 和 findMax 都是自递归的，但是 reduce 没有调用 findMax 并且对玫瑰树一无所知。

您可以像这样测试重构后的代码：

let t = Node (1, [ leaf 2; leaf 3 ])
findMax t (printfn "%A")   // will be 3

为了方便起见，我创建了a gist containing all the code。

Answer 2

brianberns 接受的答案确实提供了一种在玫瑰树上实现 cps 的替代方法。

我还要添加来自 Tomas Petricek 的 this alternative solution。它显示了我们如何通过将树的类型从单个节点更改为内部循环中的节点列表来消除额外的函数调用。

我应该使用术语多路树（我会在一分钟内更改）但至少这个问题现在记录了三种不同的方法。希望它能帮助其他人。

使用连续传递样式简化多路树遍历

Simplify multiway tree traversal with continuation passing style

functional-programming

f#

continuation-passing