CODEWITHSUNDEEP
treeocaml
prmz
prmz

Reputation: 311

Ocaml Tree simple functions

I created a tree

type 'a tree = {
      mutable cont: 'a;
      mutable left: 'a bin_tree;
      mutable right: 'a bin_tree
}
and 'a bin_tree =
     Empty
     | Node of 'a tree;;

and I'm struggling to do with some simple functions like

I googled my problem but I'm constantly getting errors. For example: 

let rec insert x tree =
match tree with
 Empty -> Node(x, Empty, Empty)
| Node(y, left, right) ->
   if x <= y then Node(y, insert x left, right)
             else Node(y, left, insert x right)

or if I try:

let rec insert x = function
Empty -> Node(Empty, x, Empty)
| Node(lb, r, rb) -> if x < r then Node(insert x lb, r, rb)
else Node{lb; r; insert x rb} ;;

I'm constantly getting Syntax Error.

Upvotes: 0

Views: 1493

Answers (2)

Thomash
Thomash

Reputation: 6379

Why do you use a mutable record for your tree? OCaml programmers prefer to use immutable data structures. Here the mutability of your tree doesn't improve the complexity but can introduce bugs.

Here is how to implement trees in a persistent way:

type 'a tree =
| Empty
| Node of 'a * 'a tree * 'a tree

and it is actually this type that you use in your code for member and insert.

Upvotes: 4

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

Your match pattern should contain { and } to match a record so code 

match tree with
   Empty -> false
  | Node { cont=x; left=l; right=r } -> (*something here .... *)

Actually, a language extension for record notation permit to avoid the field labels when the pattern variable has the same name as the field, so instead of coding a pattern Node { cont=cont; left=left; right=right } you can code Node{cont;left;right}

You could also look into Ocaml's stdlib/set.ml source file.

Notice that your 'a bin_tree type is nearly equivalent to 'a tree option.

Upvotes: 0

Related Questions