Few words about functions

It's a real big topic but for now let's watch in action basic function declaration

let sum x = function y -> x + y;;

(** just a sum function that has next type *)
(** val sum : int -> int -> int = <fun> *)

How to read such notation
means the type - it's a function
last int before = means return value of function
previous int's means arguments

Let's watch something more complex

Compose function accepts f and g functions and accepts value (x) on which functions should be applied

let compose f g = function x -> f (g x);;

Let's take a glance into high order functions (functional)

Take a look

List.map (function n -> n * 2 + 1) [0;1;2;3;4];;

(** : int list = [1; 3; 5; 7; 9] *)

Recursive functions

let rec sum l =
  match l with
  | [] -> 0                   (* base case *)
  | hd :: tl -> hd + sum tl   (* inductive case *)
;;
val sum : int list -> int = <fun>
sum [1;2;3] ;;
(* - : int = 6 *)

Logically, you can think of the evaluation of a simple recursive function like sum almost as if it were a mathematical equation whose meaning you were unfolding step by step:

sum [1;2;3]
= 1 + sum [2;3]
= 1 + (2 + sum [3])
= 1 + (2 + (3 + sum []))
= 1 + (2 + (3 + 0))
= 1 + (2 + 3)
= 1 + 5
= 6