OCaml的堆缺少的節點

Question

我已經定義了類型堆：

type 'a heap = 
| Node of int * int * 'a heap * 'a heap 
| Leaf;; 

和以下功能：

let rank = function Leaf -> 0 | Node (r,_,_,_) -> r;; 

let makeNode x a b = 
if rank a>= rank b then Node(rank b+1,x,a,b) 
else Node (rank a+1,x,a,b);; 

let rec meld = function 
|h,Leaf | Leaf,h -> h 
| (Node(f,x,a1,b1)as h1),(Node(g,y,a2,b2)as h2) -> if x >= y then makeNode x a1 (meld (b1, h2)) 
else makeNode y a2 (meld (h1, b2));; 

let insert h x = meld ((Node(1,x,Leaf,Leaf)), h);; 

然而，當我插入第二個節點到堆中，根消失。我怎樣才能解決這個問題：

let makeheap x = Node(1,x,Leaf,Leaf);; 
let myheap = makeheap 5;; 
insert myheap 7;; 
insert myheap 8;; 
insert myheap 3;; 

結果如下輸出：

val myheap : 'a heap = Node(1,5,Leaf,Leaf) 
'a heap = Node(1,7,Leaf,Node(1,5,Leaf,Leaf)) 
'a heap = Node (1,8,Leaf,Node(1,5,Leaf,Leaf)) 
'a heap = Node(1,5,Leaf,Node(1,3,Leaf,Leaf)) 

Answer 1

你打電話insert，就好像它是一個必要的功能。也就是說，它會改變某種狀態。但是你的數據結構是不可變的。您必須將insert視爲返回新狀態。

你應該仔細閱讀純函數式編程，然後再考慮更遠，我懷疑。

岡崎的前幾章純功能數據結構解釋得很好。

回答你直接的問題是這樣的：

# insert (insert myheap 7) 8;; 
- : 'a heap = Node (1, 8, Leaf, Node (1, 7, Leaf, Node (1, 5, Leaf, Leaf)))