我自學Okasaki's Purely Functional Data Structures, now on exercise 3.4,要求推理和實施重量偏左的堆。這是我的基本實現:現在重量偏左的堆:自上而下版本的優勢?
(* 3.4 (b) *)
functor WeightBiasedLeftistHeap (Element : Ordered) : Heap =
struct
structure Elem = Element
datatype Heap = E | T of int * Elem.T * Heap * Heap
fun size E = 0
| size (T (s, _, _, _)) = s
fun makeT (x, a, b) =
let
val sizet = size a + size b + 1
in
if size a >= size b then T (sizet, x, a, b)
else T (sizet, x, b, a)
end
val empty = E
fun isEmpty E = true | isEmpty _ = false
fun merge (h, E) = h
| merge (E, h) = h
| merge (h1 as T (_, x, a1, b1), h2 as T (_, y, a2, b2)) =
if Elem.leq (x, y) then makeT (x, a1, merge (b1, h2))
else makeT (y, a2, merge (h1, b2))
fun insert (x, h) = merge (T (1, x, E, E), h)
fun findMin E = raise Empty
| findMin (T (_, x, a, b)) = x
fun deleteMin E = raise Empty
| deleteMin (T (_, x, a, b)) = merge (a, b)
end
,在3.4(C)&(d),它要求:
目前,
merge
工作於兩種 遍:自上而下的傳遞由 調用merge
,以及由幫助者 函數makeT
的調用組成的自底向上傳遞 。修改merge
至 在一個自上而下的傳遞中操作。 自頂向下 版本merge
在惰性 環境中有什麼優勢?在併發 環境中?
我通過簡單的內聯makeT
改變merge
功能,但我看不到任何優勢,所以我覺得我還沒有掌握鍛鍊這些部位的精神。我錯過了什麼?
fun merge (h, E) = h
| merge (E, h) = h
| merge (h1 as T (s1, x, a1, b1), h2 as T (s2, y, a2, b2)) =
let
val st = s1 + s2
val (v, a, b) =
if Elem.leq (x, y) then (x, a1, merge (b1, h2))
else (y, a2, merge (h1, b2))
in
if size a >= size b then T (st, v, a, b)
else T (st, v, b, a)
end
我想我已經想通了一個點與問候懶惰的評價。如果我不使用遞歸合併計算尺寸,然後遞歸調用將不再需要,直到孩子是需要進行評估:
fun merge (h, E) = h
| merge (E, h) = h
| merge (h1 as T (s1, x, a1, b1), h2 as T (s2, y, a2, b2)) =
let
val st = s1 + s2
val (v, ma, mb1, mb2) =
if Elem.leq (x, y) then (x, a1, b1, h2)
else (y, a2, h1, b2)
in
if size ma >= size mb1 + size mb2
then T (st, v, ma, merge (mb1, mb2))
else T (st, v, merge (mb1, mb2), ma)
end
是這樣嗎?雖然我不確定併發。