F#PurelyFunctionalDataStructures WeightBiasedLeftistHeap ex 3.4

Question

我正在研究Okasaki的Purely Functional Data Structures并尝试构建F#实现的东西.我也正在阅读本书中列出的练习(有些非常具有挑战性).好吧,我坚持练习3.4,它要求修改WeightBiasedLeftistHeap的合并功能,使其在单个传递中执行,而不是原始的2传递实现.

我还没弄清楚如何做到这一点,并希望得到一些建议.在SO上有另一篇文章,其中一个人通过几乎内联makeT函数在SML中完成它.我开始走这条路线(在评论部分3.4首先尝试.但是放弃了这种方法,因为我认为这真的不是在一次传递中执行(它仍然是'直到达到叶子然后展开并重建树).我在解释那仍然是两次合并时错了吗？

这是我完整实施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

第一个问题是:什么构成"一次通过"算法？可以自然地作为单个自上而下循环实现的东西将符合条件.相比之下,递归 - 天真编译 - 通常有两个通道,一个在路上,一个在路上. 尾递归可以很容易地编译成循环,通常是函数式语言. 尾递归模数缺点是一种类似的,虽然不常见的优化.但是,即使您的编译器不支持尾递归模数缺点,您也可以轻松地将这样的实现转换为循环.

尾递归模数缺点类似于普通尾递归,除了尾调用包装在构造函数中,可以在递归调用之前分配和部分填充.在这种情况下,您希望返回表达式类似于T (1+size(a)+size(b)+size(c),x,a,merge(b,c)).这里需要的关键洞察力(如在另一个SO线程的编辑中所提到的)是你不需要执行合并来知道它的结果有多大,因此它应该在新树的哪一侧继续.这是因为大小merge(b,c)始终是size(b)+size(c),可以在合并之外计算.

请注意,rank普通左派堆的原始函数不共享此属性,因此无法以此方式进行优化.

从本质上讲,那么,你内联两次调用MAKET 并转换形式的叫声size(merge(b,c))来size(b)+size(c).

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

类似地,在涉及锁和变异的并发环境中,新实现可以通过在整个过程中获取和释放每个节点的锁来支持更多的并发性,而不是锁定整个树.(当然,这只适用于非常轻巧的锁.)