data-structures - F# PurelyFunctionalDataStructures WeightBiasedLeftistHeap ex 3.4

Question

我正在研究 Okasaki 的 Purely Functional Data Structures 并尝试构建事物的 F# 实现。我也在完成书中列出的练习(有些非常具有挑战性)。好吧，我坚持练习 3.4，它要求修改 WeightBiasedLeftistHeap 的合并函数，使其在单次执行中执行，而不是原始的 2 次执行实现。

我还没有弄清楚如何做到这一点，并希望得到一些建议。还有一个post here on SO一个人通过几乎内联 makeT 函数在 SML 中做到这一点。我开始走这条路线(在评论部分 3.4 First Try 中。但放弃了这种方法，因为我认为这真的不是在一次传递中执行的(它仍​​然会直到到达一片叶子然后展开并重建树)。我是否错误地将其解释为仍然是两次通过合并？

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

第一个问题是:什么构成了“one-pass”算法？可以自然地作为单个自上而下循环实现的东西是合格的。相比之下，递归——天真地编译——通常有两次传递，一次在下降过程中，另一次在返回过程中。尾递归可以很容易地编译成一个循环，并且通常是在函数式语言中。 Tail recursion modulo cons是一种类似的优化，尽管不太常见。但是，即使您的编译器不支持尾递归模 cons，您也可以轻松地手动将此类实现转换为循环。

尾递归取模 cons 与普通尾递归类似，只是尾调用被包裹在一个构造函数中，可以在递归调用之前分配和部分填充。在这种情况下，您可能希望返回表达式类似于 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) .

一旦进行了此更改，生成的函数将比原始函数明显懒惰，因为它可以在评估递归合并之前返回结果的根。

类似地，在涉及锁和变异的并发环境中，新的实现可以通过获取和释放沿途每个节点的锁来支持更多的并发，而不是锁定整个树。 (当然，这只对非常轻量级的锁才有意义。)