Évidemment, dans un langage fonctionnel, cette partie est très importante.

let f = fun x -> x+1;;
(* affiche : val f: int -> int = <fun> *)

On a assigner à f une fonction en utilisant le mot-clé fun. Cette fonction est comme une fonction mathématique, elle consiste en l'association d'un item à un autre.

La fonction est ici reconnue comme associant un entier à un entier.

On pourra calculer :

f 5;; (*affiche 6*)
f(5);; (*idem*)

Une fonction à deux variables devient un peu plus bizarre :

let g = fun x y -> x * y;;
(* renvoie val g: int -> int -> int <fun> *)
g 4 13;; (* renvoie 52 *)
g(4,13);; (* Erreur ! *)
g 4;; (* renvoie une fonction int -> int ??? *)
g(4);; (* idem *)
g(4)(13);; (* renvoie 52 *)

Il faut comprendre que la fonction g reçoit d'abord l'argument x, disons x = 4 pour l'exemple. x étant connu, on sait que le résultat sera 4 * y.

g 4 produit donc une fonction y → 4 * y.

Puisque g(4) est une la fonction y → 4 * y on peut lui appliquer un argument : g(4)(13) qui fait 52.

Remarquez que les parenthèses sont inutiles et ne servent qu'à préciser une priorité en cas de besoin.

Par exemple :

f f 5;; (* Erreur : le premier f essaie de prendre le 2e f comme argument *)
f (f 5);; (* Ok : le premier f prendra le résultat de (f 5) comme argument *)

Une fonction peut avoir une une fonction comme argument. Par exemple, on pourrait définir une fonction repete consistant, à partir d'une fonction $x \mapsto f(x)$ d'obtenir la fonction $x \mapsto f(f(x))$.

let repete f = fun x -> f ( f x );;
(* equivalent a : *)
let repete f x = f ( f x ) ;;

(* Exemple : *)
let g = fun x -> 3 * x + 2;;
let h = repete g;;
(* g est la fonction x -> g(g(x)) *)
g(1);; (* renvoie 5 *)
g(5);; (* renvoie 17 *)
h(1);; (* renvoie g(g(1)), soit 17 *)

OCaml autorise les fonctions récurrentes mais il faut alors préciser le mot clé rec.

Par exemple, le classique factoriel :

let rec facto = fun n -> if n > 1 then n * (facto (n-1) ) else 1;;

La récurrence est le chemin privilégié. Supposez que vous souhaitiez faire la somme des n premiers entiers. Il serait naturel d'écrire

(* attention code faux *)
let n = 10;;
let t = 0;;
for i = 1 to n do
  t = t + i;
done;;
t;;

Mais cela ne fonctionne pas : La commande t = t + i suppose de modifier la valeur de t ce qui n'est en principe pas possible ! Il faut passer par une récurrence :

let rec somme = fun n -> if n = 0 then 0 else n + somme(n-1);;
somme 10;;

La boucle est alors contenue dans l'utilisation de la récurrence.

Bien sûr une récursion terminale est bienvenue :

let rec somme_rec = fun n s -> if n = 0 then s else somme_rec(n-1, s);;
let somme = fun n -> somme_rec n 0

La fonction somme précédente prévoyait deux cas : n = 0 ou n quelconque. Il pourrait y avoir plus de cas et OCaml prévoit une syntaxe pour cela :

let rec somme = function
  | 0 -> 0 
  | n -> n + somme(n-1) ;;

Il suffit d'énumérer les cas possibles et d'indiquer quoi faire à chaque fois.