如何在F中組合狀態單元和連續單元＃

Question

我正在嘗試使用任務並行庫來對樹進行求和，其中子任務僅在樹遍歷到特定深度之前產生，否則它將使用剩餘的子節點進行求和延續傳遞風格，避免堆棧溢出。

但是，代碼看起來非常難看 - 使用狀態monad來攜帶當前深度會很好，但狀態monad不是尾遞歸。或者，我將如何修改繼續monad以攜帶狀態？或者創建一個狀態和延續monads的組合？

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

在我眼裏，深度看起來很好，醜位裁判細胞和分配。我不清楚爲什麼你需要他們;我認爲只是通過id（身份函數）作爲cont參數意味着sumRec將返回值，然後您將不需要ref單元格。 （我可能是錯的，這是分析，在一目瞭然的。）

（我也想擺脫newDepth，只是內嵌(depth-1)在遞歸調用的地方，作爲一個風格問題。）

最後，我不知道sumTreeContMonad是什麼，但看起來你可以使用sumRec t -1 k而不是sumTreeContMonad t k，它的工作原理是一樣的。

（如果你的博客有代碼，而不是代碼的圖片，我可能只是發表我自己的這些改進的代碼，但我不喜歡抄寫的數據類型和這樣的。爲什麼要發佈照片？）

Answer 2

我認爲首先了解您的要求非常重要。

• 算法的順序版本並不需要保持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來使用引用單元格，並且我修改了算法以僅產生一個後臺任務並在當前線程上完成第二部分工作。