Ce chapitre a pour objet de vous montrer des exemples de fonctions en Caml afin de mieux comprendre ce qui était dans les chapitres précédent. Pour chaque exemple, un premier paragraphe (objet) explique le but et précise les sujets que l'exemple aborde, avec un lien sur le chapitre correspondant. Un deuxième paragraphe explique comment on peut coder la fonction. Enfin, je donne une solution pour la fonction.
Sommaire
Booléens : ou exclusif
Racine cubique
Liste et fonctions : redéfinition de map
Du tableau à la chaîne de caractères
Nombres premiers
Exposant maximal
Décomposition en facteurs premiers
Mémo
Clics et traits
Clics et traits : suite
I) Booléens : ou exclusif
1) Objet
Caml dispose déjà des opérateurs logiques and (notée &), or et not. On veut coder le ouex (« ou exclusif », parfois aussi noté xor) : a ouex b est vrai si parmi a et b, un seul est vrai. Je donne déjà un code pour cette fonction dans le cours sur les types. Cependant ici, le but est de le faire en utilisant seulement les fonctions or, and et not. Sujet abordé : Opérations sur les booléens
2) Méthode
On peut faire le tableau de valeurs de A ouex B :
| | B est vrai | B est faux |
| A est vrai | FAUX | VRAI |
| A est faux | VRAI | FAUX |
On voit donc que a ouex b est vrai si (a et non b) ou (non a et b), ce qu'on va traduire directement.
3) Fonction
let ouex a b = (a & (not b)) or ((not a) & b);;
On peut aussi replacer & et or par leurs équivalents dits « paresseux » pour gagner du temps de calcul (les opérateurs paresseux n'évaluent leur second argument que si le premier argument ne suffit pas pour conclure). On obtient :
let ouex a b = (a&&(not b))||((not a)&&b);;
II) Racine cubique
1) Objet
Ocaml dispose de la fonction sqrt qui calcule la racine carrée. On veut créer une fonction qui donne la racine cubique de tout nombre réel avec une précision de 10-6. Sujets abordés :
Opérations sur les flottants
Références
Boucles while
Tests, syntaxe de if
2) Méthode
On va construire deux suites de réels a et b. Initialement, a vaut n'importe quel nombre inférieur à la racine cubique de x et b un nombre supérieur. Un choix (celui fait ici) est par exemple : si x est entre -1 et 1, a = -1 et b = 1 ; si x est supérieur à 1, a = 0 et b = x ; si x est inférieur à -1, a = x et b = 0. L'idée est d'itérer en utilisant la moyenne de a et b : si celle-ci est inférieure à la racine cubique de x (on teste cela en comparant son cube à x lui-même) alors ce sera la nouvelle valeur de a, sinon ce sera la nouvelle valeur de b. Cette répétition, qui se fera donc par une boucle while, se fera jusqu'à ce que les deux valeurs de a et b soient proches à 10-6 près de la racine cherchée. Pour s'assurer de ceci, il suffit en fait de vérifier que la différence b - a est elle-même inférieure à 10-6.
On ne s'intéresse pas ici à la justification mathématique que cette méthode fonctionne. Pour ceux que ça intéresse, la clé est que les suites a et b sont adjacentes. Notons aussi qu'on peut trouver des méthodes plus rapides...
3) Fonction
let racine x =
let a_initial,b_initial = if x > 1. then 0.,x else if x < -.1. then x,0. else -.1.,1. in
let a = ref a_initial and b = ref b_initial in
while !b -. !a > 0.000001 do
let moyenne = (!a +. !b) /. 2. in
if moyenne *. moyenne *. moyenne > x then b := moyenne else a := moyenne
done;
!a;;
III) Listes et fonctions : redéfinition de map
1) Objet
Il existe dans Caml une fonction map dont le type est ('a -> 'b) -> 'a list -> 'b list. Elle prend en argument une fonction et une liste. Elle rend une nouvelle liste qui correspond à la liste donnée, dans laquelle on a appliqué la fonction à chaque élément. Exemple : Si la fonction (nommée f, c'est très original) sert à doubler un entier, alors map f [1;2;5] donne [2;4;10]. L'objet de ce paragraphe est de redéfinir cette fonction. Sujets abordés :
Filtrages par motif
Définition locale de fonction
Fonctions à deux arguments
Généralités sur les listes
Récurrence
2) Méthode
On utilise une fonction auxiliaire récursive prenant en argument deux listes : arguments et résultats. On fait un filtrage sur arguments.
- si arguments est vide, c'est qu'on a parcouru toute la liste et qu'on a mis dans résultats l'ensemble des calculs. On rend cette liste
- sinon, on prend la tête t de arguments. On lui applique la fonction f et on place le résultat en tête de résultats. On applique la récurrence avec la queue de arguments et la nouvelle liste de résultats.
La fonction récursive doit être appelée avec la liste donnée par l'utilisateur et la liste vide (car au début, on n'a aucun résultat !)
3) Fonction
let map f liste =
let rec aux arguments resultats = match arguments with
|[] -> resultats
|t::q -> aux q ((f t)::resultats)
in aux liste [];;
Note : cette fonction n'est pas exactement la même que la fonction map normale. En effet elle inverse l'ordre dans la liste. Pourquoi ? Lors de la récurrence, on prend le premier élément de liste. On lui applique f et on le place dans résultats. Puis on applique f à tous les autres éléments de la liste en les plaçant en tête de résultats. Ainsi, le premier résultat (f du premier élément de liste) se retrouve en dernier dans la liste résultats. Pour arranger cela, il suffit de rendre au lieu de résultats la liste résultats renversée :
let map f liste =
let rec aux arguments resultats = match arguments with
|[] -> List.rev resultats
|t::q -> aux q ((f t)::resultats)
in aux liste [];;
OU UNE AUTRE POSSIBILITE :
let map f liste =
let rec aux arguments resultats = match arguments with
|[] -> resultats
|t::q -> aux q ((f t)::resultats)
in List.rev (aux liste []);;
IV) Du tableau à la chaîne de caractères
1) Objet
Nous allons définir une fonction qui reçoit un tableau de caractères (char array) et doit rendre la chaîne de caractères correspondante. Par exemple : string_of_array [|'H';'e';'l';'l';'o';' ';'W';'o';'r';'l';'d'|] doit rendre "Hello World". Sujets abordés :
Définition locale
Généralités sur les tableaux
Généralités sur les chaînes de caractères
Boucle for
2) Méthode
On utilise la structure des tableaux et des chaînes de caractères et leur avantage de numéroter les éléments. On crée une chaîne contenant n'importe quel caractère, de longueur égale au tableau puis on recopie caractère par caractère en utilisant une boucle impérative.
3) Fonction
let string_of_array t =
let longueur = Array.length t in
let texte = String.make longueur 'a' in
for i = 0 to (longueur-1) do
texte.[i] <- t.(i)
done;
texte;;
Notez d'abord que cet exemple illustre la différence de syntaxe entre chaîne de caractères (l'indice d'un élément est noté entre crochets) et tableau (entre parenthèses). Ensuite, vu que les numéros commencent à 0, il est normal que le numéro du dernier caractère ne soit pas longueur mais (longueur-1).
V) Nombres premiers
1) Objet
On veut savoir si un entier est premier ou non. La fonction est_premier doit prendre un entier comme argument et rendre un booléen. On rappelle que 2 est premier et que 1 ne l'est pas. Sujets abordés :
Définition locale de fonction
Opérations sur les entiers
Récurrence
Booléens, tests, syntaxe de if
2) Méthode
On va tester pour tous les entiers de 2 à n-1 s'ils divisent n. Pour cela, on fait une récurrence : on commence avec 2. Pour chaque entier i, si i divise n, on a trouvé un diviseur différent de n donc on rend false (n n'est alors pas premier). Sinon, on teste l'entier suivant (i+1). On continue jusqu'à n. Si on est arrivé à n, c'est qu'aucun entier plus petit ne le divise donc on rend true.
Comment teste-t-on si i divise n ? C'est simple : on calcule le reste de la division euclidienne de n par i (n mod i) et on demande s'il vaut 0.
Sauf que cette fonction ne marche que pour un entier à partir de 2. Si on appelle avec 1, on va se lancer dans une boucle sans fin (car on va commencer avec 2 et on augmentera de 1 à chaque fois, on n'atteindra jamais 1). Il faut donc traiter ce cas à part en rajoutant un test demandant si n vaut 1, en dehors de la récurrence.
Je signale enfin que ma fonction n'est pas optimale : on sait qu'il suffit de tester les entiers jusqu'à la racine carrée de n, sans aller jusqu'à n lui-même. Mais bon, le but de cette page est de vous apprendre Caml, pas de faire dans la subtilité...
3) Fonction
let est_premier n =
let rec aux i =
if i = n then true (* je n'hésite pas à indenter ! *)
else if n mod i = 0 then false
else aux (i+1)
in (* regardez comment j'indente : j'aligne ce in avec le let qui correpond *)
if n = 1 then false else aux 2;;
Il y a ici une syntaxe un peu maladroite : j'utilise des structures conditionnelles en rendant des booléens. Ce type de syntaxe peut toujours être simplifié. Le plus simple (selon moi) est d'aller de la fin vers le début. Simplifions aux :
Sur les deux dernières lignes, on a une expression du type « si A alors FAUX sinon B ». On fait un tableau que l'on remplit en respectant cette règle :
| | B est vrai | B est faux |
| A est vrai | FAUX | FAUX |
| A est faux | VRAI | FAUX |
Il n'y a qu'une case avec VRAI. Notre « si A alors FAUX sinon B » correspond donc en fait à « (non A) et B ». On peut réécrire la fonction :
let est_premier n =
let rec aux i =
if i = n then true
else (n mod i <> 0)&&(aux (i+1))
in
if n = 1 then false else aux 2;;
On a à présent dans aux une expression « si A alors VRAI sinon B ». En utilisant encore un tableau, on voit que c'est « A ou B ». D'où :
let est_premier n =
let rec aux i = (i = n)||((n mod i <> 0)&&(aux (i+1))) in
if n = 1 then false else aux 2;;
On peut encore simplifier la dernière ligne. Finalement, la syntaxe la plus compacte est :
let est_premier n =
let rec aux i = (i = n)||((n mod i <> 0)&&(aux (i+1))) in
(n <> 1)&&(aux 2);;
VI) Exposant maximal
1) Objet
On veut écrire, car cela sera utile après, une fonction expomax qui prend en argument deux entiers n et i et rend le nombre maximum a tel que ia divise n. Par exemple, expomax 18 3 doit donner 2. Sujets abordés :
Définition locale de fonction
Fonctions à deux arguments
Récurrence
Opérations sur les entiers
Tests, syntaxe de if
2) Méthode
On fait une fonction récursive avec comme arguments a et ipuissancea. Si ipuissancea (qui correspond à ia) divise n, on augmente a de 1, on multiplie ipuissancea par i et on recommence. Quand ipuissancea ne divise pas n, a est plus grand de 1 que le nombre cherché.
3) Fonction
let expomax n i =
let rec aux a ipuissancea =
if n mod ipuissancea = 0 then aux (a+1) (i*ipuissancea)
else (a-1)
in
aux 1 i;;
VII) Décomposition en facteurs premiers
1) Objet
Maintenant que nous avons la fonction ci-dessus, nous voulons décomposer un entier (autre que 1 et non premier) en nombres premiers. On rend une liste contenant des couples d'entiers : les facteurs premiers et leurs exposants. Par exemple, 12 donne [2,2;3,1]. Sujets abordés :
Définition locale
Fonctions à deux arguments
Récurrence
Opérations sur les entiers
Tests, syntaxe de if
2) Méthode
On va ici utiliser une méthode assez idiote mais simple à comprendre. On fait une récurrence avec un entier i (qui vaut au départ 2) et une liste de résultats. Pour chaque i, on regarde :
- si i n'est pas premier (on se sert de l'exemple V) on passe directement à (i+1)
- sinon si i ne divise pas n, on passe aussi à (i+1)
- sinon, i doit apparaître dans la décomposition et on calcule l'exposant avec l'exemple précédent.
On continue jusqu'à n+1 : quand on l'atteint, on a testé tous les diviseurs éventuels de n donc on s'arrête et on rend la liste.
3) Fonction
let decompose n =
let rec aux i resultats =
if i > n then resultats
else if not (est_premier i) then aux (i+1) resultats
else if n mod i > 0 then aux (i+1) resultats
else let exposant = expomax n i in aux (i+1) ((i,exposant)::resultats)
in
aux 2 [];;
VIII) Mémo
1) Objet
On veut créer un petit programme servant de mémo à l'utilisateur. Quand on l'appelle, cette fonction commence par réécrire à l'écran le texte précédemment enregistré par l'utilisateur et conservé dans le fichier « C:/memo.tmp ». Puis la fonction demande à l'utilisateur d'entrer une nouvelle phrase. Enfin cette nouvelle phrase est enregistrée dans le fichier memo.tmp, en écrasant l'ancienne phrase. Sujets abordés :
Effets de bord
Ecriture et lecture de fichier
Récupération d'erreur : try
2) Méthode
Il nous faut d'abord une fonction auxiliaire qui ouvre le mémo et récupère la phrase qui est dedans, en rendant la phrase « Mémo vide » si le fichier est inexistant ou vide (on utilise pour cela une récupération d'erreur). Le reste de la fonction principale s'écrit naturellement avec print_string et read_line (fonction qui demande une ligne de texte à l'utilisateur). Il faut aussi penser à insérer des sauts de ligne après les affichages sans quoi l'écran sera difficile à lire.
3) Fonction
let ouvrir_fichier() =
try
(let canal_entree = open_in "C:/memo.tmp" in
let resultat = input_line canal_entree in
close_in canal_entree;
resultat)
with
|_ -> "Mémo vide";;
let memo() =
print_string "La phrase actuellement enregistrée est :"; print_newline();
print_string (ouvrir_fichier()); print_newline(); print_newline();
print_string "Entrez la nouvelle phrase"; print_newline();
let phrase = read_line() in
let canal_sortie = open_out "C:/memo.tmp" in
output_string canal_sortie phrase;
close_out canal_sortie;;
IX) Clics et traits
1) Objet
Quittons l'arithmétique pour le graphisme. Je veux une fonction clic_trait qui n'a pas d'argument. Elle permet à l'utilisateur de cliquer à deux endroits de l'écran et de tracer un trait entre ces deux endroits. Sujets abordés :
Définition locale
Effets de bord
Evènements
Souris
Point courant et lignes
2) Méthode
On utilise wait_next_event pour attendre que l'utilisateur clique et on prend les coordonnées de la souris. Puis on recommence. On place le point courant (avec moveto) au premier point, on se déplace au deuxième (avec lineto).
Note : avant d'écrire la fonction, on doit charger le module graphique. Je vais aussi supposer ici qu'on a ajouté open Graphics;; pour simplifier l'écriture de la fonction (les « Graphics. » partout, ça surcharge).
3) Fonction
let clic_trait () =
let attend1 = wait_next_event [Button_down] in let (a,b) = (attend1.mouse_x,attend1.mouse_y) in
let attend2 = wait_next_event [Button_down] in let (c,d) = (attend2.mouse_x,attend2.mouse_y) in
moveto a b; lineto c d;;
X) Clics et traits : suite
1) Objet
Faisons plus complexe. Je veux améliorer la fonction précédente : le but est toujours de tracer un trait entre deux endoits désignés par clics. Cependant, quand l'utilisateur aura cliqué au premier endroit, et jusqu'à ce qu'il clique à un autre endroit, une ligne devra joindre le point de départ au curseur à tout instant. Sujets abordés :
Définition locale
Fonctions à deux arguments
Effets de bord
Evènements
Souris
Point courant et lignes
Couleurs
2) Méthode
Comme précédemment, notre fonction va d'abord attendre un clic et prendre les coordonnées (a,b) de ce clic. Ensuite elle appelera une fonction auxiliaire récursive. Cette deuxième fonction prend en argument deux couples d'entiers (des coordonnées) (a,b) et (c,d). Elle attend que l'utilisateur clique ou bouge la souris (évènement Mouse_motion). Si l'utilisateur bouge la souris (ce qu'on repère en observant la valeur de button dans le résultat de wait_next_event), on joint une ligne blanche de (a,b) à (c,d), on repère les coordonnées (e,f) de la nouvelle position du curseur et on joint une ligne noire de (a,b) à (e,f). La récurrence s'arrête quand l'utilisateur clique, auquel cas la fonction ne fait plus rien.
Ainsi vous voyez que tant qu'on bouge la souris, cette fonction trace un trait entre une position de départ fixe et la nouvelle position, en effaçant au passage le trait correspondant à la position précédente du curseur.
3) Fonction
Là encore, je suppose que le module graphique a été ouvert.
let rec clic_trait_aux (a,b) (c,d) =
let attend = wait_next_event [Button_down; Mouse_motion] in
if not (attend.button) then
(
set_color white; moveto a b; lineto c d;
let (e,f) = (attend.mouse_x,attend.mouse_y) in
set_color black; moveto a b; lineto e f;
clic_trait_aux (a,b) (e,f)
);;
let clic_trait() =
let attend = wait_next_event [Button_down] in let x = (attend.mouse_x,attend.mouse_y) in
clic_trait_aux x x;;
Ecrite ainsi, cette fonction a deux inconvénients auxquels vous pouvez réfléchir. Premièrement, elle ne marche que si on veut tracer un trait noir sur un fond blanc. Ensuite, le fait d'effacer le trait précédent simplement en traçant un trait blanc efface aussi tout motif qui n'aurait aucun rapport avec le trait mais sur lequel on serait passé. Quand vous créez et distribuez un module, c'est le genre d'effet secondaire de votre fonction que vous devez signaler aux éventuels utilisateurs.
Autre remarque : la première fonction, clic_trait_aux, n'est qu'une fonction auxiliaire servant la deuxième fonction. J'aurais donc pu la définir à l'intérieur de l'autre en tant que définition locale, comme dans l'exemple VII. Cependant, quand une fonction auxiliaire devient longue à écrire, il peut être bon de procéder ainsi pour la lisibilité du programme.
> Haut de la page
