L1 Info S2
Programmation Fonctionnelle OCaml
TP2: types algébriques et récursivité
[Link]@[Link]
1 Destinations postales
On définit:
type desination =
| Departement of int (* n◦ , ex: 37 pour Indre et Loire *)
| Etranger of string (* nom du pays *)
1. Écrire une fonction departement: destination -> int qui donne
le département correspondant à une destination (99 pour un pays
étranger)
2. Écrire une fonction pays: destination -> string qui donne le nom
de pays correspondant à une destination ("France") pour la France
3. Écrire un « prédicat », une fonction qui calcule une condition:
interieure: destination -> bool qui teste si une destination est
intérieure.
1
2 Noms de fichiers
On souhaite représenter des noms de fichier, sans risquer de les confondre
avec des chaînes. Pour cela on utilise un type algébrique à un seul cas:
type file = File of string
1. Écrire des fonctions file_of_string et string_of_file
2. On définit une fois pour toutes la constante « séparateur », qui dépend
du système d’exploitation. Sous Unix: let sep = "/".
Écrire une fonction path: file -> file -> file qui réunit 2
chemins en un seul. Par exemple, sous Unix, File "Documents" et
File "[Link]" se réunissent en File "Documents/[Link]".
3 Entiers naturels avec l’infini
On a souvent besoin de considérer des entiers naturels potentiellement infinis
(ex: cardinaux d’ensembles). En ML on définit donc:
type card = Infini | Naturel of int (* >= 0 *)
1. Écrire des fonctions card_of_int, card_of_string, string_of_card.
L’infini se représente par la chaîne « oo ».
2. Écrire des fonctions plus, fois, maxi, mini. Dans l’exercice, 0 × ∞
est défini et vaut 0 (le produit de l’ensemble vide par n’importe quel
ensemble est vide).
4 Unités de longueur
On définit le type « unité de longueur »
type unite = Metre | KM | Pied | Pouce
2
et le type « mesure de longueur munie d’une unité »
type mesure = Mesure of float * unite
1. Écrire une fonction valeur: unite -> float qui donne la valeur
d’une unité en mètres. Rappel: 1 pouce = 2,54 cm; 1 pied = 12 pouces.
2. Écrire une fonction metres: mesure -> float qui convertit une
mesure de longueur en mètres.
3. Écrire une fonction conversion: float -> unite -> mesure qui
convertit une longueur exprimée en mètres dans une certaine unité.
4. Écrire une fonction somme: mesure -> mesure -> mesure qui calcule
la somme de 2 mesures de longueurs, en convertissant en mètres si les
unités sont différentes.
Voir l’exercice « Grandeurs physiques » pour une méthode garantissant
à la compilation que les unités sont les mêmes.
5 Grandeurs physiques
On considère des grandeurs physiques, par exemple: longueur, surface,
volume, etc.
Il est essentiel de ne pas confondre les différentes grandeurs quand on les
ajoute: c’est le critère d’« homogénéité ». Par exemple, il est incohérent
d’ajouter des litres et des mètres. Le but de l’exercice est de voir une méthode
infaillible pour y parvenir.
On commence par définir ces types:
type longueur = Longueur
type surface = Surface
type volume = Volume
Ces types sont triviaux, isomorphes à unit: leurs valeurs ne transportent
aucune information. Mais ces types portent des noms différents, donc ils sont
non interchangeables.
3
Maintenant on définit le type « grandeur physique homogène à un certain
type »
type ’a grandeur = Grandeur of float
Aucune valeur de type ’a n’est exploitée, mais on a plusieurs grandeurs
physiques de types différents: longueur grandeur, surface grandeur,
volume grandeur.
On définit (manuellement et avec des noms différents) des fonctions pour
multiplier des grandeurs:
let longueur_longueur (Grandeur x: longueur grandeur)
(Grandeur y: longueur grandeur) =
(Grandeur (x *. y): surface grandeur)
let longueur_surface (Grandeur x: longueur grandeur)
(Grandeur y: surface grandeur) =
(Grandeur (x *. y): volume grandeur)
On peut désormais définir une fonction somme, « polymorphe » c’est-à-dire
qu’elle fonctionne pour tout type de grandeur:
let somme (Grandeur x: ’a grandeur) (Grandeur y: ’a grandeur) =
(Grandeur (x +. y): ’a grandeur)
Il y a 3 fois le même type générique ’a dans la définition, donc il est impossible
d’ajouter un volume et une longueur: c’est testé à la compilation.
Pour retrouver une valeur sans dimension, on définit une fonction de conver-
sion, polymorphe de type ’a grandeur -> float:
let conversion (Grandeur x) = x
Pour convertir une valeur sans dimension, de type float, en grandeur, par
exemple en volume v:
let v = (Grandeur 1.: volume grandeur)
let s = (Grandeur 1.: surface grandeur)
On ne peut pas ajouter un volume et une surface: c’est testé à la compilation
et ça provoque une erreur de typage:
let ko = somme s v (* erreur de typage *)
Question: expérimenter concrètement ces définitions.
4
6 Valeurs optionnelles
Voici le type prédéfini en ML pour une valeur optionnelle:
type ’a option = Some of ’a | None
1. Écrire une fonction moitie: int -> int option telle que moitie n
donne, s’il existe, l’entier m tel que 2m = n.
2. Écrire une fonction lift: (’a -> ’b) -> (’a option -> ’b
option) qui transforme une fonction sur les valeurs en fonction
sur les options. Par exemple, string_of_int: int -> string est
une fonction qui prend un entier et qui calcule une chaîne, donc
lift string_of_int: int option -> string option doit être une
fonction qui prend une option sur un entier et qui donne une option
sur une chaîne.
3. Écrire une fonction bind: (’a -> ’b option) -> (’a option ->
’b option) qui transforme une fonction au résultat optionnel en fonc-
tion sur les options. Par exemple, moitie: int -> int option prend
un entier et calcule une option, donc bind moitie: int option ->
int option prend une option et calcule une option.
7 Reconstitution du type list
Le type list ne peut pas être explicitement défini en OCaml pour une raison
de syntaxe. Mais « :: » représente un constructeur et « [] » représente la
liste vide.
On peut donc écrire ce type (recons pour « reconstitution »), différent mais
isomorphe à list:
type ’a recons =
| Cons of ’a * ’a recons (* nom traditionnel: constructeur *)
| Nil (* nom traditionnel: liste vide *)
Question: Écrire des fonctions recons_of_list et list_of_recons pour
convertir d’un type à l’autre.
5
8 Fichiers et dossiers
On définit une arborescence de fichiers par ce type: un élément de
l’arboresence est soit un stock de données (peu importe lesquelles) soit un
dossier/répertoire contenant d’autres sous-arborescences.
type arborescence =
| Fichier of string (* nom, peu importe le contenu *)
| Dossier of string * arborescence list (* nom, contenu *)
1. Sous Unix ouvrir un terminal juste au dessus de Documents, et ta-
per « find Documents ». Ça doit énumerer récursivement tous les
fichiers/sous-dossiers de Documents.
Voici le déroulement de find x: afficher x, puis, si x est un dossier,
appeler récursivement find x/y pour tout sous-fichier y de x.
2. Reconstituer ce comportement (il y a des affichages, donc ce n’est pas
fonctionnel): écrire find: string -> fichier -> () qui réalise ces
affichages.
Voici le déroulement de find chemin x : afficher
chemin ^ nom(x), puis, si x est un dossier, appeler récursivement
find (chemin ^ nom(x) ^ "/") y pour tout sous-fichier y de x.
Pour effectuer une action sur tous les éléments d’une liste `:
[Link] ` (fun élément -> . . . )
3. Essayer avec cet exemple:
let x = find "" x doit afficher:
Dossier ("Documents", [ Documents
Fichier "[Link]"; Documents/[Link]
Dossier ("fonctionnel", [ Documents/fonctionnel
Fichier "[Link]"; Documents/fonctionnel/[Link]
Fichier "[Link]"]); Documents/fonctionnel/[Link]
Fichier "[Link]"]) Documents/[Link]
6
9 Puissance
Effectuer l’exercice supplémentaire « Puissance efficace », partie A: « Puis-
sance par multiplications ».
10 PGCD
Effectuer l’exercice supplémentaire « PGCD et coefficients de Bézout ».
11 Grands entiers
Effectuer l’exercice supplémentaire « Manipulation de grands entiers »,
questions fact et pgcd. On utilisera [probablement] la version avec
ersatz_arith, en version interactive.
Effectuer l’exercice supplémentaire « Puissance efficace », partie B: « Puis-
sance modulaire ».
12 Fibonacci
Effectuer l’exercice supplémentaire « Suite de Fibonacci ».