F＃PurelyFunctionalDataStructures WeightBiasedLeftistHeap ex 3.4

Question

我正在研究Okasaki的纯功能数据结构，并尝试构建事物的F＃实现。我也正在阅读本书中列出的练习（有些练习很有挑战性）。好吧，我坚持练习3.4，该练习要求修改WeightBiasedLeftistHeap的合并功能，以使其在单遍执行，而不是原始的2遍实现。

我还无法弄清楚该怎么做，希望能提出一些建议。在SO上还有另外一个发布在这里一个人几乎可以通过内联makeT函数来在SML中做到这一点。我开始走这条路线（在有评论的第3.4节“第一次尝试”中，但是放弃了这种方法，因为我认为这实际上并没有一步完成（它仍然会一直到到达叶子然后展开并重建树）。我将其解释为仍然是两次通过合并吗？

这是一个链接到我的WeightBiasedLeftistHeap的完整实现。

这是我在F＃中失败的尝试： 通用标签

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)。

进行此更改后，生成的函数将比原始函数更懒惰，因为它可以在 评估递归合并之前返回结果的根。 类似地，在涉及锁和变异的并发环境中，新的实现可以通过沿途为每个节点获取和释放锁，而不是锁定整个树来支持更多的并发。 （当然，这仅适用于非常轻巧的锁。）

Answer 2

我不确定我是否正确理解了这个问题，但是这是我的尝试-当前，merge操作执行对merge的递归调用（这是第一遍），并在到达堆末尾（第一遍）这是match中的两种情况），它将新构造的堆返回给调用者，并多次调用makeT（这是第二遍）。

我不认为我们需要做的就是简单地内联mMakeT（如果是的话，只需将inline添加到makeT中就可以了，而不会降低代码的可读性：-））。

但是，可以做的是修改merge函数以使用continuation-passing-style，其中“其余的工作”作为函数传递给递归调用（因此，堆栈上没有待处理的工作）在第一遍完成后完成）。可以这样完成： 通用标签

我不完全相信这是正确的答案-它仅执行一次通行证，但是（续）汇总的工作意味着通行证的时间长两倍。但是，我没有找到使它更简单的方法，因此这可能是正确的答案...