CODEWITHSUNDEEP
ocamlheap
David Farthing
David Farthing

Reputation: 247

OCaml Heap Missing Nodes

I have defined a type heap:

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

And the following functions:

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

However, when I insert a second node into the heap, the root disappears. How can I fix this:

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

results in the following output:

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

Upvotes: 0

Views: 61

Answers (1)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66803

You're calling insert as if it's an imperative function. I.e., as if it's going to change some state. But your data structure is immutable. You have to think of insert as returning the new state.

You should read up on pure functional programming before going too much farther, I suspect.

The first few chapters of Okasaki's Purely Functional Data Structures explain things very well.

The answer to your immediate question is something like this:

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

Upvotes: 2

Related Questions