Fonctions OCaml : Types, Pattern Matching et Récursivité

1. Introduction à OCaml : Expressions, Types et Immutabilité

Contrairement à un langage comme Python que vous connaissez, où le style est principalement impératif (on donne une séquence d'instructions qui modifient un état), OCaml encourage un style fonctionnel. Un programme est vu comme l'évaluation d'expressions qui transforment des données pour en produire de nouvelles, plutôt que de modifier des données existantes.

Les concepts fondamentaux à saisir sont :

• Les expressions avant tout : Presque tout est une expression qui s'évalue en une valeur.
• Le typage statique fort avec inférence : Chaque valeur a un type, vérifié à la compilation. Cependant, vous n'avez que rarement besoin de l'écrire ; le compilateur le déduit pour vous. C'est le meilleur des deux mondes : la sécurité du typage sans la verbosité.
• L'immutabilité par défaut : Une fois qu'un nom est lié à une valeur avec let, cette liaison ne change plus. Cela simplifie radicalement le raisonnement sur le code.

Pour vous familiariser avec la syntaxe de base, le plus simple est d'utiliser l'interpréteur OCaml, aussi appelé toplevel.

Pour résumer quelques points essentiels :

• Une définition se fait avec let nom = expression;;. Le ;; est nécessaire dans le toplevel pour lancer l'évaluation.
• Une fonction se définit par let nom_fonction arg1 arg2 = corps_de_la_fonction;;.
• Le type d'une fonction qui prend un int et retourne un string est noté int -> string.
• L'appel de fonction est une simple juxtaposition : nom_fonction val1 val2. Les parenthèses ne sont nécessaires que pour lever des ambiguïtés d'évaluation, par exemple f (x + 1).

2. La Récursivité : L'Itération Fonctionnelle

En programmation fonctionnelle, la récursivité remplace les boucles for et while du monde impératif. Puisque les variables sont immuables, on ne peut pas avoir une variable i que l'on incrémente. À la place, on effectue un calcul et on passe le résultat à l'appel récursif suivant.

En OCaml, une fonction doit être explicitement déclarée comme récursive avec le mot-clé let rec. Oublier rec est une erreur très fréquente pour les débutants.

La vidéo suivante explique cette nécessité et illustre la syntaxe avec l'exemple classique de la factorielle.

La section "Recursive Functions" du document "A Tour of OCaml" (ressource LINK que vous avez déjà ouverte) fournit un autre exemple, la fonction range, qui construit une liste de manière récursive.

3. Le Filtrage par Motif (Pattern Matching)

Le filtrage par motif est sans doute la construction la plus puissante et la plus idiomatique d'OCaml. Il permet de combiner des tests de condition, des branchements et l'extraction de valeurs de structures de données de manière concise et sûre. C'est l'équivalent d'un switch surpuissant que l'on trouve dans d'autres langages.

On l'utilise principalement avec la syntaxe match ... with. On va l'explorer dans le contexte des listes, qui est leur terrain de jeu naturel.

Une liste en OCaml a une structure récursive simple :

• Soit elle est vide, notée [].
• Soit elle est non vide, composée d'un premier élément (la tête) et du reste de la liste (la queue). On la note tete :: queue.

Le filtrage par motif permet de distinguer ces deux cas.

La vidéo présente la fonction sum pour calculer la somme des éléments d'une liste d'entiers. Voici sa structure :

let rec sum lst =
  match lst with
  | [] -> 0 (* Cas de base : la somme d'une liste vide est 0 *)
  | h :: t -> h + sum t (* Cas récursif : la tête plus la somme du reste *)

Cette structure est le patron de base pour la quasi-totalité des fonctions récursives sur les listes.

4. Exercice de synthèse

Pour mettre en pratique ces trois concepts, je vous propose d'écrire une fonction.

Énoncé :
Écrivez une fonction récursive product : int list -> int qui calcule le produit des éléments d'une liste d'entiers.

1. Utilisez let rec pour la définition.
2. Utilisez le filtrage par motif (match ... with) pour distinguer le cas de la liste vide du cas d'une liste non vide.
3. Réfléchissez bien à la valeur que votre fonction doit retourner pour le cas de base (product []). Quelle est l'identité pour la multiplication ?

Indice : La structure de votre fonction sera très similaire à celle de la fonction sum.

Prenez quelques minutes pour essayer de l'écrire.

let rec product lst =
  match lst with
  | [] -> 1 (* L'élément neutre pour la multiplication est 1 *)
  | h :: t -> h * product t

(* Testons la fonction *)
let () =
  assert (product [1; 2; 3; 4] = 24);
  assert (product [5; 10] = 50);
  assert (product [] = 1);
  assert (product [10; 0; 20] = 0)

Conclusion

Cette première incursion en OCaml vous a confronté à une nouvelle façon de penser la programmation, plus déclarative et mathématique. La combinaison de l'immutabilité, de la récursivité et du filtrage par motif est extraordinairement expressive et sûre.

Points clés à retenir :

• Les programmes OCaml sont des ensembles d'expressions qui s'évaluent en valeurs.
• Le typage est statique et inféré, offrant sécurité sans verbosité.
• Les liaisons sont immutables par défaut, ce qui simplifie le raisonnement.
• La récursivité, déclarée avec let rec, est le mécanisme d'itération principal.
• Le filtrage par motif (match ... with) est l'outil idiomatique pour inspecter des données et contrôler le flux d'exécution, notamment dans les fonctions récursives. Le motif h :: t est fondamental pour le traitement des listes.

Dans notre prochaine leçon, nous franchirons une étape supplémentaire. Maintenant que vous savez écrire des fonctions simples, nous verrons comment définir nos propres types de données complexes avec les types algébriques. Cela nous permettra de modéliser des structures comme les arbres binaires de manière élégante et purement fonctionnelle, une compétence essentielle pour les épreuves de l'Agrégation.