F＃PurelyFunctionalDataStructures WeightBiasedLeftistHeap ex 3.4

Question

我正在研究Okasaki的Purely Functional Data Structures並嘗試構建F＃實現的東西。我也正在閱讀書中列出的練習（有些非常具有挑戰性）。那麼我被困在練習3.4中，它要求修改WeightBiasedLeftistHeap的合併函數，以便它在一次執行中執行，而不是原始的2次執行。

我還沒有能夠找出如何做到這一點，並希望得到一些建議。還有另外一個post here on SO，一個人在SML中做了很多內聯makeT函數。我開始走這條路線（在3.4的第一次嘗試的評論部分），但放棄了這種方法，因爲我認爲這確實不是一次執行（它仍然會「直到達到一片葉子然後放鬆並重建樹）。我錯了解釋，由於仍然是雙通合併

Here is a link to my complete implementation of WeightBiasedLeftistHeap.

這裏是我失敗的嘗試，在F＃中做到這一點：？

type Heap<'a> = 
| E 
| T of int * 'a * Heap<'a> * Heap<'a> 

module WeightBiasedLeftistHeap = 
    exception EmptyException 

    let weight h = 
     match h with 
     | E -> 0 
     | T(w, _,_,_) -> w 

    let makeT x a b = 
     let weightA = weight a 
     let weightB = weight b 
     if weightA >= weightB then 
      T(weightA + weightB + 1, x, a, b) 
     else 
      T(weightA + weightB + 1, x, b, a) 

    // excercise 3.4 first try 
    // let rec merge3_4 l r = 
    //  match l,r with 
    //  | l,E -> l 
    //  | E,r -> r 
    //  | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) -> 
    //   if lx <= rx then 
    //    let right = merge3_4 lb rh 
    //    let weightA = weight la 
    //    let weightB = weight right 
    // 
    //    if weightA >= weightB then 
    //     T(weightA + weightB + 1, lx, la, right) 
    //    else 
    //     T(weightA + weightB + 1, lx, right, la) 
    //   else 
    //    let right = merge3_4 lh rb 
    //    let weightA = weight ra 
    //    let weightB = weight right 
    // 
    //    if weightA >= weightB then 
    //     T(weightA + weightB + 1, rx, ra, right) 
    //    else 
    //     T(weightA + weightB + 1, rx, right, ra) 

    // excercise 3.4 second try (fail!) 
    // this doesn't work, I couldn't figure out how to do this in a single pass 
    let merge3_4 l r = 
     let rec merge' l r value leftChild = 
      match l,r with 
      | l,E -> makeT value leftChild l 
      | E,r -> makeT value leftChild r 
      | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) -> 
       if lx <= rx then 
        merge' lb rh lx la //(fun h -> makeT(lx, la, h)) 
       else 
        merge' lh rb rx ra //(fun h -> makeT(rx, ra, h)) 

     match l, r with 
     | l, E -> l 
     | E, r -> r 
     | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) -> 
      let lf = fun h -> makeT(lx, la, h) 
      if lx <= rx then 
       merge' lb rh lx la // (fun h -> makeT(lx, la, h)) 
      else 
       merge' lh rb rx ra // (fun h -> makeT(rx, ra, h)) 

    let rec merge l r = 
     match l,r with 
     | l,E -> l 
     | E,r -> r 
     | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) -> 
      if lx <= rx then 
       makeT lx la (merge lb rh) 
      else 
       makeT rx ra (merge lh rb) 

    let insert3_4 x h = 
     merge3_4 (T(1,x,E,E)) h 

Answer 1

第一個問題是：什麼構成「單程」算法？某些自然可以實現爲單個自上而下循環的內容將符合要求。相比之下，遞歸 - 天真地編譯 - 通常有兩個通行證，一個在回程中，一個在回程中。 尾遞歸可以很容易地編譯成一個循環，通常是在功能語言。 Tail recursion modulo cons是一個類似的，儘管不太常見的優化。但是，即使您的編譯器不支持尾遞歸模的缺點，您也可以輕鬆地將這種實現轉換爲循環。

尾遞歸modulo cons類似於普通的尾遞歸，只是tail調用被包裝在一個構造函數中，可以在遞歸調用之前分配和部分填充。在這種情況下，您希望返回表達式類似於T (1+size(a)+size(b)+size(c),x,a,merge(b,c))。這裏需要的關鍵見解（如編輯other SO thread所述）是，你不需要執行合併來知道它將會產生多大的結果，因此它應該繼續進行新樹的哪一側。這是因爲merge(b,c)的大小始終爲size(b)+size(c)，可以在合併之外進行計算。

請注意原始的rank功能對於普通的左邊堆具有而不是共享這個屬性，所以不能用這種方式進行優化。

本質，那麼，你內聯兩次調用MAKET 也形式size(merge(b,c))的電話轉換爲size(b)+size(c)。

一旦你做了這個改變，結果函數比原來的函數顯着更加懶惰，因爲它可以在之前返回的根目錄，評估遞歸合併。同樣，在涉及鎖和變異的併發環境中，通過獲取和釋放沿途每個節點的鎖，新實現可以支持更多併發性，而不是鎖定整個樹。 （當然，這隻適用於非常輕便的鎖。）

Answer 2

我不能完全肯定，如果我的理解正確的問題，但這裏是我的嘗試 - 目前，merge操作執行遞歸電話merge（這是第一次通過），當它到達堆的末尾（match中的前兩個例子）時，它將新構造的堆返回給調用者並且幾次調用makeT（這是第二遍） 。

我不認爲這只是內聯mMakeT就是我們要求做的（如果是，只需添加inline到makeT這還沒有使代碼的可讀性:-)完成）。

但是，可以做些什麼呢是修改merge函數以使用continuation-passing-style，其中「剩餘工作」作爲函數傳遞給遞歸調用（所以沒有掛起工作第一遍完成後要完成堆棧）。這是可以做到這樣的：

let rec merge' l r cont = 
    match l,r with 
    | l,E -> cont l // Return result by calling the continuation 
    | E,r -> cont r // (same here) 
    | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) -> 
     if lx <= rx then 
      // Perform recursive call and give it 'makeT' as a continuation 
      merge' lb rh (makeT lx la) 
     else 
      // (same here) 
      merge' lh rb (makeT rx ra) 

// Using 'id' as a continuation, we just return the 
// resulting heap after it is constructed 
let merge l r = merge' l r id 

我並不完全相信這是一個正確的答案 - 它執行只是一個單一的傳球，但聚集的工作（在繼續）指證是兩倍更長的時間。但是，我沒有看到讓這個更簡單的方法，因此它可能是正確的答案...