Imperative OCaml data structure with pointers?

Question

Is such a thing possible?

Hi all,

in my class we were told to implement Binary Search Trees in OCaml, using functional and imperative programming. We are following an ADT and implementation in Pascal, a procedural language where pointers are used.

This is how the data structure looks like:

# Pascal
type
   tKey      = integer;
   tPos      = ^tNode;
   tNode     = record
          key         : tKey;
          left, right : tPos;
           end;      
   tBST = tPosT;

We were also given some basic BST operations. Here is an example of one, if that could help:

# Pascal
procedure add_key(VAR T : tBST; k:tKey);
var new, parent, child :  tBST;
begin
   createNode(new);
   new^.key := k;
   new^.left := nil;
   new^.right := nil;

   if T=nil then
      T := new
   else begin
      parent := nil;
      child := T;
      while (child <> nil) and (child^.key <> k) do begin
     parent := child;
     if k < child^.key then
        child := child^.left
     else
        child := child^.right;
      end;

      if (child = nil) then 
     if k < parent^.key then
        parent^.left := new
     else
        parent^.right := new;
        { duplicates are ignored }
   end;
end;

This is how my functional (if that makes any sense) data structure looks like:

type key =
    Key of int;;

type bst = 
    Empty   
    | Node of (key * bst * bst);;

However, I am having big trouble using the imperative facet of OCaml. I have to make it look as similar as possible as the Pascal implementation and I don't know about the possibilities of data structures and pointers in OCaml since I've always programmed using recursive and so on. I was thinking in using multiple "let", if's and else's, but I have no idea how to define my data structure. Would appreciate enormously input on this.

Answer 1

From what I understand you would have a type like this :

type key = int

type t = Empty | Node of t * key * t

But your add function shouldn't look like this :

let rec add x t =
  match t with
    | Empty ->
      Node (Empty, x, Empty)
    | Node (l, v, r) ->
      let c = compare x v in
      if c = 0 then t
      else if c < 0 then Node (add x l, v, r)
      else Node (l, v, add x r)

Because this is only functional.

Maybe you could change your type to :

type t = Empty | Node of t ref * key * t ref

And try to adapt the add function to this type.