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

Question

我着迷the approach used in this blog post使用 CPS 遍历玫瑰树 a.k.a.multiway tree a.k.a n-ary tree。

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

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

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

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

所以我的问题是:是否有另一种方法可以在玫瑰树上实现 CPS，我可以设法更好地理解它？有没有一种方法可以重构上面的代码，使其更容易理解(消除相互递归？)

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

Answer 1

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

• 从您的类型中删除 Leaf 案例，因为它是多余的。叶子只是一个带有空子列表的 Node。
• 将通用 CPS 逻辑与玫瑰树专用逻辑分开。
• 使用延续 monad 来简化 CPS 代码。

首先，让我们定义 continuation monad :

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 函数，它将“不完整”计算列表组合成一个单独的不完整计算(其中不完整计算是任何需要延续的函数' -> 'u 类型，并使用它来生成 'u 类型的值。

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

我认为这当然更清楚，但它可能看起来像魔术。理解的关键让! 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 .