OCaml Programming Examples: Functions and Data Structures

Posted on Mar 12, 2025 in Computer Engineering

OCaml Programming Examples

Basic Functions

Fibonacci:

let rec fib x = if x <= 1 then 1 else fib (x-1) + fib (x-2);;

Factorial:

let rec fact x = if x <= 1 then 1 else x * fact (x-1);;

List Operations

Insert and Sort:

let rec insert elem = function
  | [] -> [elem]
  | h::t -> if elem < h then elem::h::t else h::insert elem t;;

let rec sort = function
  | [] -> []
  | h::t -> insert h (sort t);;

sort [4;2;3;5];;

Reverse List:

let rev list =
  let rec aux acc = function
    | [] -> acc
    | h::t -> aux (h::acc) t in aux [] list;;

99 Problems (Partial)

Last Element (returns an int):

let rec last = function
  | [] -> 0
  | [x] -> x
  | _::t -> last t;;

Last Two Elements:

let rec last_two = function
  | [] -> []
  | [x;y] -> [x;y]
  | _::t -> last_two t;;

Element at K (k=1):

let rec at k = function
  | [] -> None
  | h::t -> if k=1 then Some h else at (k-1) t;;

List Length:

let length list =
  let rec aux n = function
    | [] -> n
    | _::t -> aux (n+1) t in aux 0 list;;

Last Element (returns a list):

let rec last = function
  | [] -> []
  | [x] -> [x]
  | _::t -> last t;;

Last Element (returns an option):

let rec last = function
  | [] -> None
  | [x] -> Some x
  | _::t -> last t;;

Element at K (k=0):

let rec at k = function
  | [] -> None
  | h::t -> if k=0 then Some h else at (k-1) t;;

Length (alternative):

let rec len x = match x with
  | [] -> 0
  | h::t -> 1 + len t;;

Even Numbers:

let rec pares = function
  | [] -> []
  | h::t -> if h mod 2 = 0 then h::(pares t) else pares t;;

Odd Numbers:

let rec impares = function
  | [] -> []
  | h::t -> if h mod 2 = 1 then h::(impares t) else impares t;;

Append:

let rec append l1 l2 = match l1 with
  | [] -> l2
  | h::t -> h::(append t l2);;

Merge:

let rec merge l1 l2 = match l1 with
  | [] -> l2
  | h::t -> h::(merge l2 t);;

Sum (with match):

let rec soma l = match l with
  | [] -> 0
  | h::t -> h + soma t;;

Is List Empty? (bool):

let empty l = match l with
  | [] -> true
  | h::t -> false;;

Is List Empty? (function):

let empty = function
  | [] -> true
  | h::t -> false;;

Member:

let rec membro x = function
  | [] -> false
  | h::t -> if x=h then true else membro x t;;

Member (with match):

let rec membro x l = match l with
  | [] -> false
  | h::t -> if x=h then true else membro x t;;

Remove Element:

let rec remove x l = match l with
  | [] -> []
  | h::t -> let t' = remove x t in if h=x then t' else h::t';;

Higher-Order Functions

Apply a function once:

let apl1 f x = f x;;

Apply a function twice (adds the results):

let apl2 f x = (f x) + (f x);;

Apply a function k times:

let rec apl k f x = if k=1 then (f x) else apl (k-1) f x;;

Greatest Common Divisor:

let rec gcd m n = if n=0 then m else gcd n (m mod n);;

Filter:

let rec filter f = function
  | [] -> []
  | h::t -> if (f h) then h::(filter f t) else filter f t;;

Map:

let rec map f = function
  | [] -> []
  | h::t -> (f h)::map f t;;

Binary Search Trees

type 'a abp =
  | Leaf
  | Node of 'a abp * 'a * 'a abp;;

Lookup (finds the rightmost element – incorrect):

let rec lookup = function
 | Leaf -> assert false
 | Node (_, x, Leaf) -> x
 | Node (_, x, r) -> lookup r;;

Insert:

let rec insert x = function
  | Leaf -> Node (Leaf, x, Leaf)
  | Node (l, y, r) ->
    if x=y then Node (l, y, r)
    else if x < y then Node (insert x l, y, r)
    else Node (l, y, insert x r);;

Delete:

let rec delete x = function
  | Leaf -> Leaf
  | Node (l, y, r) ->
    if x = y then join l r
    else if x < y then Node (delete x l, y, r)
    else Node (l, y, delete x r)
and join l r = match l, r with
  | Leaf, r -> r
  | l, Leaf -> l
  | l, r -> let m = find_max l in Node (delete m l, m, r);;

OCaml Programming Examples: Functions and Data Structures