Sommaire

Révision pour l’examen intra

Voici une liste des notions qu’il est nécessaire de connaître en prévision de l’examen de mi-session du 9 mars 2026.

Chapitre 1 : Concepts de base

1. Savoir évaluer des expressions de lambda-calcul simples.

Par exemple:

(λx.λy.2 * x + y) 3 10 = ((λy.2 * x + y)[x -> 3]) 10
                      = (λy.6 + y) 10
                      = (6 + y)[y -> 10]
                      = 6 + 10
                      = 16

2. Connaître les types littéraux

int, float, bool, char, string, 'a list, unit, tuples ('a * 'b)

On doit aussi connatître les quelques fonctions de base:

  1. L’arithmétique des entiers
  2. L’arithmétique des flottants
  3. Opérations booléennes
  4. Fonctions de base de la librairie standard

Exemples: string_of_int, int_of_char, float_of_int, etc.

  1. Fonctions de base du module List

Exemples: List.length, List.rev, List.map, List.filter, List.fold_left, List.fold_right, etc.

3. Connaître la différence entre une liste et un tuple.

4. Savoir construire une liste avec le constructeur ::, et connaître la différence avec l’opérateur de concaténation @.

5. Savoir lier des valeurs à des noms de variables, avec le mot-clé let.

6. Reconnaître les liaisons locales (let ... in ...) et leur portée.

7. Connaître la différence entre l’égalité structurelle = et l’égalité physique ==.

8. Savoir faire du filtrage par motif (match)

Savoir utiliser le joker _,

Savoir imposer des conditions avec le mot-clé when

Chapitre 2 : Fonctions et récursivité

1. Connaître les trois syntaxes pour définir une fonction et être en mesure de passer d’une syntaxe à l’autre:

let f = function x -> function y -> ...

let f = fun x y -> ...

let f x y = ...

On peut également s’attendre à devoir convertir des fonctions OCaml simples en expression de lambda-calcul et vice-versa. Par exemple:

(* la fonction *)
function x -> function y -> 2 * x + y
(* est équivalente à *)
λx.λy.2 * x + y

2. Savoir reconnaître les occurences libres d’une variable et connaître le concept de shadowing.

3. Savoir comment définir une fonction récursive, à l’aide du mot-clé rec

4. Savoir définir une fonction locale récursive à l’intérieur d’une fonction, afin d’utiliser un accumulateur pour faciliter la tâche.

Par exemple:

let fact (n : int) : int =
 (* Fonction auxiliaire avec accumulateur : *)
 let rec aux (n : int) (acc : int) : int =
   if n = 0 then
     acc
   else
     let acc = n * acc in
     aux (n - 1) acc
 in
 aux n 1

4. Connaître la notion de récursivité terminale et pouvoir en expliquer l’avantage principal.

5. Savoir comment appliquer une fonction

6. Savoir ce qu’est l’application partielle de fonctions

7. Savoir annoter les variables d’une fonction avec leur type

Exemple:

let f (x : int) (y : string) : int =
  x + (int_of_string y)

Chapitre 3 : typage

1. Types de base: int, float, bool, char, string, unit

2. Types composés: 'a list, 'a option, ('a, 'b) result, fonctions 'a -> 'b, n-uplets 'a * 'b * 'c * ...

3. Savoir définir un nouveau type avec le mot clé type

Type synonyme,

Type énumération

Type produit

Type algébrique

Enregistrements (records)

4. Savoir faire du filtrage par motif (match) sur différents types

5. Savoir comment fonctionne le type 'a option

6. Filtrage et récursivité pour manipuler des listes

Savoir déterminer les bons cas de base et les bons cas récursifs

Chapitre 4 : Fonctions d’ordre supérieur

1. Savoir ce qu’est une fonction d’ordre supérieur

2. Savoir utiliser une fonction d’ordre supérieur

3. Savoir comment fonctionnent les fonctions List.map, List.filter, List.fold_left, List.fold_right, et autres fonctions d’ordre supérieur simples.

Chapitre 5 : Modules

1. Savoir ce qu’est un module, et savoir comment déclarer un module avec la syntaxe suivante:

module NomDuModule = struct 
   ...
end

2. Savoir ce qu’est un type de module

module type NOM_DU_TYPE_DE_MODULE = sig 
   ... 
end

Étant donné un type de module, vous devriez être en mesure de définir un module qui implémente ce type:

module NomDuModule : TYPE_DE_MODULE = struct
   ...
end

Chapitre 6 : Preuves de programmes

1. Connaître l’axiome d’extensionnalité afin de prouver que deux fonctions sont égales

(* pour deux fonctions f et g, on a que *)
f = g
(* si et seulement si *)
f x = g x (* pour toute valeur de x *)

2. Savoir faire une preuve par récurrence structurelle pour prouver l’égalité de deux fonctions ou expressions

Par exemple:

Démonstration d’équivalence (map et fold_right)

Théorème map f l = fold_right g l []

Cas de base : l = []

À gauche :

map f l = [] (* déf. de map *)

À droite :

fold_right g [] [] = []

Cas de récurrence, l = h :: t, avec IH = map f t = fold_right g t []

À gauche :

map f (h :: t) = (f h) :: map t             (* déf. de map *)
              = (f h) :: fold_right g t [] (* IH *)

À droite :

fold_right g (h :: t) [] = g h (fold_right g t []) (* déf. de fold_right *)
                        = (f h) :: fold_right g t [] (* déf. de g *)

C.Q.F.D.