小编Der*_*aly的帖子

当我写这个函数时,我知道我不会得到尾调优化.我仍然没有想出一个处理这个的好方法,并希望别人可以提供建议.

我有一棵树:

type Heap<'a> =
| E
| T of int * 'a * Heap<'a> * Heap<'a> 

我想要计算其中有多少个节点:

let count h =
    let rec count' h acc =
        match h with 
        | E -> 0 + acc
        | T(_, value, leftChild, rightChild) ->
            let acc = 1 + acc
            (count' leftChild acc) + (count' rightChild acc)

    count' h 0

由于添加了子节点的计数,因此未进行优化.如果树有100万个节点,任何想法如何制作这样的东西？

谢谢,德里克

这是使用CPS实现计数.它仍然吹响了堆栈.

let count h =
    let rec count' h acc cont =
        match h with
        | E -> cont …

我正在研究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 …