如何在F#中组合状态和延续monad

Question

我正在尝试使用任务并行库对树进行求和,其中只生成子任务,直到遍历树直到某个深度,否则它使用延续传递样式对剩余的子节点求和,以避免堆栈溢出.

但是,代码看起来很丑陋 - 使用状态monad来承载当前深度会很好,但状态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(因为它总是处理树的其余部分).但是,它需要使用continuation,因为树可能很大.

• 另一方面,并​​行版本需要保留depth(因为您只想进行有限数量的递归调用),但它不需要使用continuation(因为深度非常有限,当您启动新任务时,它无论如何都不会保留堆栈).

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

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而且我修改了算法以仅生成一个后台任务并在当前线程上完成第二部分工作.