CMSC330 OCaml Code Examples

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


Web Accessibility