Hello,
I started coding this hoping that the imperative approach will not be too hard to implement. But it doesn’t seem so. I have come across other functional approaches but before abandoning this I want to ask the forum.
Will this approach work ? The code compiles and executes but the references may not be correct as it is not complete.
Are there full-fledged examples of tree rotations using mutable refs somewhere ?
Thanks,
Mohan
type 'a splay_tree = Leaf | Node of 'a node1
and 'a node1 = { key : 'a;value : 'a; mutable left : 'a splay_tree option; mutable right : 'a splay_tree option; }
type 'a t = 'a splay_tree option ref
let splay i t =
match !t with
|Leaf -> None
| Node { key=_; left ;value=_ ; right} ->
match left, right with
| Some Node _,Some Node {left=_; key=_; value=_; right=_}->None
| Some Node {left; key; value=_; right},Some Leaf | Some Node {left; key; value=_; right}, _ ->
if i < key then (
let y = left in
let _l = right in
let _right = t in
let left = y in
left (* Return 'left' value *)
) else (
let left = t in
let _right = t in
let newT = left in
Some !newT (* Returning 'left' value wrapped in 'Some' *)
)
| Some Leaf,Some Node _-> None
| Some Leaf,Some Leaf-> None
| _ ,Some Leaf -> None
| Some Leaf,None -> None
|(None, Some (Node _))-> None
|None, None ->None
The approach you take here should work. Namely, the mutable approach is to have a top-level reference which holds the real tree structure and an auxiliary type (here splay_tree) which denotes the actual tree structure. A couple of remarks though:
It seems you are translating a C or Java implementation (or some equivalent pseudo-code) using None to represent the null pointer and Some ... for an actual value. I think you don’t need that here, you can just use Leaf to represent an empty tree (I don’t see a situation where you would want both Some Leaf and None).
you can use inline records instead of introducing node1:
type 'a splay_tree = Leaf
| Node of { key : 'a;value : 'a; mutable left : 'a splay_tree ; mutable right : 'a splay_tree ; }
which can make some of the matching a bit lighter.
Even though it works to use a reference to hold the tree structure, you could use a dedicated record type with other fields to store e.g. the height and size of your tree (this is orthogonal).
But regardless of whether you use your type or the simplified version I suggest, you should be able to port any existing Java/C code that for splay tree relatively easily to this mutable version.
Regarding your splay_tree type, I also think you could do without the option everywhere as you already have Leaf to represent an empty tree
I recommend that you implement the purely functional version first, as it is simpler (and likely faster!) and can easily be translated to an imperative version as a second step.
This is my imperative code and it doesn’t look pretty. Moreover it seems to be worse than the C code I was porting. Functional code is better. I think.
It compiles and works but it isn’t tested properly.
Based on earlier comments I can refactor this. Are there any comments ? Can I assume that this is not the way to write this code ?
let insert_with_key_value: int splay_tree option ref=
ref (Some ( Node {
key = 1;
value = 2;
left = Some (Node {key=3; value=1; left=Some (Leaf); right=Some (Leaf)});
right = Some (Node {key=4; value=3; left=Some (Leaf); right=Some (Node {
key = 2;
value = 2;
left = Some (Node {key=3; value=1; left=Some (Leaf); right=Some (Leaf)});
right = Some (Node {key=4; value=3; left=Some (Leaf); right=Some (Leaf)})
})})
}))
let splay (i : int ) (t : int splay_tree option ref) =
let n = { key = 0;value=0; left = None; right = None } in
let l = ref n in
let r = ref n in
let get_key node = match node with
| Some n -> n.key
| None -> 0 in
let loop t =
match !t with
| None -> ()
| Some node ->
let y = ref None in
match !node with
| { key = k; value=0;left = Some left_node; right = _ } as n when i < k ->
let left_key = get_key (Some !node )in
if i < left_key then (
y := Some left_node;
!node.left <- !y;
begin match !y with
| Some y_node ->
begin match y_node with
|Node r -> r.right <- !node.left;
| Leaf -> ()
end;
| None -> ()
end;
node := !r
) else if i = k then node := !node
else (
begin match n.right with
| None -> ()
| Some right ->
match right with
|Node r ->
let right_key = get_key (Some r) in
if i > right_key then (
y := Some right;
!node.right <- !y;
begin match !y with
| None -> ()
| Some y_node ->
begin match y_node with
|Node _l -> r.left <- !node.left;
| Leaf -> ()
end;
end;
node := !l
)
| _-> ()
end;
)
| _ -> ()
in
l := { key = 0; value = 0; left = None; right = !t };
r := !l;
match !t with
| None -> None
| Some node ->
match node with
| Leaf -> None
| Node root ->
loop (ref (Some (ref root)));
match !t with
| None -> None
| Some node ->
!l.right <- n.right;
!r.left <- n.left;
match node with
| Leaf -> None
| Node localnode ->
localnode.left <- n.right;
localnode.right <- n.left;
Some node
As I suggested previously, regardless of whether it is imperative, you should just remove the option.
You can observe that everywhere you have this pattern:
match e with
None -> e1
| Some node -> begin match node with
Leaf -> e1 (* the same as above *)
| Node ... -> ...
end
which indicate that wrapping in an option is useless. Some Leaf and Node serve the same purpose. If you remove this option, your code will already be much short (no nested matches with begin /end etc…).
Then of course, if you want to turn it into a purely functional version (no refs) then the code will be
even shorter since you won’t have the ref/mutable update.
