Polymorphic data types
User defined types
type gen = Int of int
|Str of string;;
let l = [Int 10; Str "alice"; Int 30; Str "bob"];;
let rec print_gen_list l =
match l with
[]->print_string ""
|h::t->
(match h with
|Int x->print_int x;print_string "\n"
|Str s->print_string s;print_string "\n"
);
print_gen_list t
;;
print_gen_list l;;
(* We can also use map to print the list *)
let print_gen x =
match x with
|Int i->print_int i;print_string "\n"
|Str s->print_string s;print_string "\n"
;;
List.map print_gen l;;
List
(* Polymorphic data types *)
type 'a my_list =
Nil
| Cons of 'a * 'a my_list;;
let rec len = function
Nil -> 0
| Cons (_, t) -> 1 + (len t);;
let rec my_list_of_list (ls : 'a list) : 'a my_list =
match ls with
[] -> Nil
| h::t -> Cons(h, (my_list_of_list t));;
let ol = my_list_of_list [1;2;3;4];;
let rec sum l =
match l with
|Nil->0 (* we had None ->0 in class. That does not work. *)
|Cons(y,t)->y + (sum t);;
len (Cons (10, Cons (20, Cons (30, Nil))));;
List Module
(* OCaml List Module: MyLis *)
module type MYLIST =
sig
type 'a mylist
val create: unit->'a mylist
val insert: 'a mylist -> 'a ->'a mylist
val to_list: 'a mylist->'a list
val remove: 'a ->'a mylist->'a mylist
end;;
module MyList : MYLIST =
struct
type 'a mylist =Nil
|Cons of 'a * 'a mylist
let create ()=Nil
let insert l n = Cons(n, l);;
let rec to_list l=
match l with
Nil->[]
|Cons(s,t)->s::to_list t
;;
let rec remove x l =
match l with
Nil->Nil
|Cons (h,t)->if(h = x) then t
else Cons (h, remove x t)
end;;
let l = MyList.create ();;
let l = List.fold_left MyList.insert l [10;20;30;40;50];;
let m = MyList.to_list l;;
Binary Search Tree
open Queue;;
type tree =
|Leaf
|Node of tree * int * tree
;;
let rec insert r n =
match r with
|Leaf->Node(Leaf, n,Leaf)
|Node(left,value,right)-> if n < value then Node((insert left n), value,right)
else if n > value then Node(left, value,(insert right n))
else Node(left,value,right)
;;
let rec count t =
match t with
Leaf->0
|Node(l,v,r)-> 1+count l+count r
;;
let rec height t=
match t with
|Leaf -> (-1)
|Node(l,v,r)->1 + max (height l) (height r)
;;
let rec inorder t =
match t with
|Leaf->print_string ""
|Node(l,v,r)->
(inorder l);
print_string (string_of_int v);print_string "->";
(inorder r)
;;
let rec preorder t =
match t with
|Leaf->print_string ""
|Node(l,v,r)->
print_string (string_of_int v);print_string "->";
(preorder l);
(preorder r)
;;
let rec postorder t =
match t with
|Leaf->print_string ""
|Node(l,v,r)->
(postorder l);
(postorder r);
print_string (string_of_int v);print_string "->";
;;
let rec aux queue =
if Queue.is_empty queue then () else
let c = Queue.pop queue in
match c with
|Leaf ->aux queue
|Node(l,v,r)->print_int v; print_string ",";
let _= Queue.push l queue in
let _ = Queue.push r queue in
aux queue
;;
(*
print the binary tree in level order
*)
let print_level_order t=
let q=Queue.create () in let _ = Queue.push t q in
aux q; print_string "\n"
;;
(*
100
/ \
50 200
/ \ / \
10 60 250
\
300
*)
let root = List.fold_left insert Leaf [100;50;200;10;60;250;300];;
preorder root;;
inorder root;;
postorder root;
print_level_order root;;