F＃PurelyFunctionalDataStructures WeightBiasedLeftistHeap ex 3.4
|
我正在研究Okasaki的纯功能数据结构，并尝试构建事物的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
没有找到相关结果
已邀请:
2 个回复
死狸蔽垂藐
。此处需要的关键见解（如另一个SO线程的编辑中所述）是您无需执行合并即可知道结果的大小，因此不需要知道新树的哪一侧。应该继续。这是因为的大小将始终为，可以在合并之外进行计算。 请注意，普通左撇子堆的原始函数不共享此属性，因此无法以这种方式进行优化。 然后，从本质上讲，您内联了对makeT的两个调用，并将形式“ 5”的调用转换为“ 3”。 进行此更改后，结果函数将比原始函数更懒惰，因为它可以在评估递归合并之前返回结果的根。 同样，在涉及锁和变异的并发环境中，新的实现可以通过沿途为每个节点获取和释放锁来支持更多的并发，而不是锁定整个树。 （当然，这仅适用于非常轻巧的锁。）磐剩
操作会递归调用that7 pass（这是第一遍），并在到达堆末尾时进行递归调用（ two9ѭ中的前两种情况），它将新构造的堆返回给调用方，并多次调用（这是第二遍）。 我不认为只需要简单地内联就可以了（如果是的话，只需在内加上即可，而且不会降低代码的可读性:-)）。 但是，可以做的是修改ѭ7函数以使用“继续传递”样式，其中“工作的其余部分”作为函数传递给递归调用（因此，堆栈上没有待处理的工作在第一遍完成后完成）。可以这样完成：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