我正在研究Okasaki的纯功能数据结构，并试图构建F#实现。我还在复习书中列出的练习（有些很有挑战性）。我一直在练习3.4中，它要求修改WeightBiasedLeftistHeap的merge函数，使其在单个过程中执行，而不是原来的2个过程实现。
我还不知道该怎么做，希望能得到一些建议。在SO上还有另一篇文章，一个人在SML中通过几乎内联makeT函数来实现这一点。我开始走这条路（在评论的第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
第一个问题是：什么构成"一次通过"算法？可以自然地作为一个自上而下的循环来实现的东西就是合格的。相反，递归——天真地编译——通常有两个过程，一个在向下的过程中，另一个在向上的过程中尾递归可以很容易地编译成一个循环，通常是在函数语言中Tail递归modulo-cons是一种类似的优化，尽管不太常见。但是，即使您的编译器不支持尾部递归模cons，您也可以轻松地手动将这样的实现转换为循环。
尾部递归modulo-cons类似于普通的尾部递归，只是尾部调用被封装在构造函数中，构造函数可以在递归调用之前进行分配和部分填充。在这种情况下，您可能希望返回表达式类似于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)。
一旦您进行了此更改，生成的函数将比原始函数明显延迟，因为它可以在评估递归合并之前返回结果的根。
类似地，在涉及锁和突变的并发环境中，新的实现可以通过获取和释放每个节点的锁来支持更大的并发性，而不是锁定整个树。（当然，这只对非常轻量级的锁有意义。）
我不确定我是否正确理解了这个问题，但这是我的尝试-目前，merge操作对merge执行递归调用（这是第一次），当它到达堆的末尾时（match中的前两种情况），它将新构建的堆返回给调用者，并调用makeT几次（这是第二次）。
我不认为我们需要简单地内联mMakeT（如果是的话，只需将inline添加到makeT中，这样做不会降低代码的可读性：-）。
不过，可以做的是修改merge函数，使其使用延续传递样式，其中"其余工作"作为函数传递给递归调用（因此，在第一次传递完成后，堆栈上没有待完成的工作）。可以这样做：
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
我不完全相信这是正确的答案——它只执行一次传递，但（在延续中）聚合的工作量意味着传递要长两倍。然而，我看不出有什么方法可以让这件事变得更简单，所以这可能是正确的答案。。。