f# - 如何在 F# 中组合状态和延续单子(monad)

Question

我正在尝试使用任务并行库对树求和，其中子任务仅在树被遍历到一定深度之前生成，否则它使用连续传递样式对剩余的子节点求和，以避免堆栈溢出。

但是，代码看起来很丑 - 使用 state monad 来携带当前深度会很好，但 state monad 不是尾递归的。或者，我将如何修改延续单子(monad)以携带状态？或者创建状态和延续单子(monad)的组合？

let sumTreeParallelDepthCont tree cont = 
  let rec sumRec tree depth cont =
    let newDepth = depth - 1
    match tree with
    | Leaf(num) -> cont num
    | Branch(left, right) ->
      if depth <= 0 then
        sumTreeContMonad left (fun leftM ->
          sumTreeContMonad right (fun rightM ->
            cont (leftM + rightM )))
      else 
        let leftTask = Task.Factory.StartNew(fun () -> 
              let leftResult = ref 0
              sumRec left newDepth (fun leftM -> 
                leftResult := leftM)
              !leftResult
              )
        let rightTask = Task.Factory.StartNew(fun () -> 
              let rightResult = ref 0
              sumRec right newDepth (fun rightM ->
                rightResult := rightM)
              !rightResult
              )
        cont (leftTask.Result + rightTask.Result)
  sumRec tree 4 cont // 4 levels deep

我在这篇博文中有更多详细信息:http://taumuon-jabuka.blogspot.co.uk/2012/06/more-playing-with-monads.html

Answer 1

我认为首先了解您的要求很重要。

• 算法的顺序版本不需要保留depth (因为它总是处理树的其余部分)。但是，它需要使用延续，因为树可能很大。

• 另一方面，并​​行版本需要保留 depth (因为你只想进行有限数量的递归调用)，但它不需要使用延续(因为深度非常有限，当你开始一个新任务时，它无论如何都不会保留堆栈)。

这意味着您根本不需要将这两个方面结合起来。然后你可以用一种非常直接的方式重写并行版本:

let sumTreeParallelDepthCont tree =  
  let rec sumRec tree depth = 
    match tree with 
    | Leaf(num) -> num 
    | tree when depth <= 0 -> 
        sumTreeContMonad tree id
    | Branch(left, right) ->
        let leftTask = Task.Factory.StartNew(fun () -> sumRec left (depth + 1))
        let rightResult = sumRec right (depth + 1)
        leftTask.Result + rightResult
  sumRec tree 4 // 4 levels deep 

无需复制 sumTreeContMonad 中的代码因为在 tree when depth <= 0 的情况下，您可以在当前树上调用它.

这也通过创建 Task<int> 来避免使用引用单元格。而不是 Task我修改了算法，只生成一个后台任务，并在当前线程上完成第二部分工作。