Aller au contenu

Rappel sur les enregistrements

On rappelle qu'on peut définir en OCaml des types proches des struct du C. On parle de type enregistrement (ou record en anglais) en référence à un parallèle avec une fiche comme celles que l'on vous demande de remplir pour les inscriptions : un certain nombre de champs ayant une référence précise comme adresse ou numéro de téléphone et un type de valeur attendu pour les réponses.

En OCaml, pour stocker le nom, l'âge et la moyenne d'informatique d'un élève, on pourrait ainsi imaginer un enregistrement à trois champs et le définir ainsi :

type eleve = {
    nom : string;
    age : int;
    moyenne : float
}

L'ordre dans lequel les champs sont énumérés n'importe pas. Pour créer une valeur du type eleve, il suffit de renseigner les champs, dans l'ordre qu'on veut, comme si on remplissait une fiche { nom = "Emile"; age = 18; moyenne = 19.9 }.

Si on dispose d'une valeur e du type eleve, on accède aux valeurs de ses champs en utilisant . comme en C : e.nom pour avoir son nom.

Les valeurs des champs sont immuables par défaut, cela signifie qu'on ne peut pas changer la moyenne de l'élève ! Comme souvent, travailler avec des données persistantes est plus simple et ce choix par défaut est raisonnable, mais dans de nombreux cas, on aimerait que certaines valeurs puissent changer. À cette fin, on peut déclarer un champ mutable. On pourrait ainsi redéfinir eleve ainsi :

type eleve = {
    nom : string;
    age : int;
    mutable moyenne : float
}

On aurait alors à écrire e.moyenne <- 12.4 pour changer la valeur de la moyenne.

Attention il est interdit d'écrire cela si le champ n'est pas mutable.

On rappelle que les références de OCaml sont en fait des types enregistrement 'a ref avec un unique champ mutable contents : 'a. On a ainsi une correspondance parfaite entre les notations :

  • ref x est en fait { contents = x }
  • l'évaluation !x est x.contents
  • x := v est en fait x.contents <- v

Question 1. Écrire une fonction plus_age : eleve list -> eleve qui prend en entrée une liste d'élèves non vide et renvoie l'élève le plus âgé.

Tests 
let e1 = { nom = "A"; age = 12; moyenne = 10.0 } in
let e2 = { nom = "A"; age = 15; moyenne = 9.0 } in
let e3 = { nom = "A"; age = 13; moyenne = 11.0 } in
let classe = [ e1; e2; e3 ] in
assert(plus_age classe = e2);
"OK";;
Corrigé 
let rec plus_age l =
    match l with
    | [] -> failwith "Erreur"
    | [e] -> e
    | e::q -> let e' = plus_age q in
        if e.age > e'.age
        then e
        else e'

Question 2. Écrire une fonction moyenne : eleve list -> float qui prend en entrée une liste d'élèves non vide et renvoie la moyenne des moyennes des élèves.

Rappel les flottants en OCaml sont un peu pénibles car ils ont des opérateurs dédiés comme +. et /.. Pour convertir un int en float on peut utiliser float_of_int : int -> float.

Tests 
let e1 = { nom = "A"; age = 12; moyenne = 10.0 } in
let e2 = { nom = "A"; age = 15; moyenne = 9.0 } in
let e3 = { nom = "A"; age = 13; moyenne = 11.0 } in
let classe = [ e1; e2; e3 ] in
assert(moyenne classe = 10.0);
"OK";;
Corrigé 
let moyenne l =
    let n = List.length l in
    let rec aux l = match l with
        | [] -> 0.0
        | e::q -> e.moyenne +. aux q
    in aux l /. (float_of_int n)

Question 3. Écrire une fonction bulletin : eleve list -> unit qui rajoute 2 points à la moyenne de tous les élèves de la liste.

Tests 
let e1 = { nom = "A"; age = 12; moyenne = 10.0 } in
let e2 = { nom = "A"; age = 15; moyenne = 9.0 } in
let e3 = { nom = "A"; age = 13; moyenne = 11.0 } in
let classe = [ e1; e2; e3 ] in
bulletin classe;
assert(e1.moyenne = 12.0);
assert(e2.moyenne = 11.0);
assert(e3.moyenne = 13.0);
"OK";;
Corrigé 
let rec bulletin l =
    match l with
    | [] -> ()
    | e::q ->
        e.moyenne <- 2. +. e.moyenne;
        bulletin q

Références et pointeurs

On va se servir des références pour faire des pointeurs comme en C.

On définit le type

type 'a ptr = 'a option ref

Note on a ici à la fois une référence et un type option, tout l'enjeu de l'exercice est d'apprendre à bien manipuler ce type qu'on retrouvera dans beaucoup de contextes où on a besoin d'une information partielle, comme lorsqu'on veut résoudre petit à petit une grille de Sudoku.

On rappelle que le type 'a option est prédéfini et qu'il correspond au type somme type 'a option = None | Some of 'a. La valeur None signifie qu'il n'y a pas d'information et Some v signifie qu'on a une information de valeur v.

Pour utiliser une valeur de type option il est ainsi nécessaire d'effectuer un filtrage :

match x with
| None -> (* ce qu'on fait quand il n'y a rien *)
| Some v -> (* ce qu'on fait quand il y a une valeur v *)

Pour plus d'informations sur le type option, on pourra lire ce chapitre du cours.

Ici, un pointeur sur la valeur v sera donc défini par ref (Some v). Le pointeur invalide que l'on note NULL en C sera défini par ref None.

Question 4. Écrire une fonction null_pointer : unit -> 'a ptr qui renvoie le pointeur nul.

Tests 
let p = null_pointer () in
assert(!p = None);
"OK";;
Corrigé 
let null_pointer () =
    ref None

Question 5. Écrire une fonction is_null : 'a ptr -> bool qui renvoie un booléen indiquant si un pointeur est nul.

Tests 
assert(is_null (ref None));
assert(not (is_null (ref (Some 3))));
"OK";;
Corrigé 
let is_null p =
    !p = None

Question 6. Écrire une fonction dereference : 'a ptr -> 'a qui renvoie la valeur pointée par un pointeur.

Cette fonction devra produire une erreur avec un failwith si le pointeur est nul.

Tests 
let p = ref (Some 3) in
assert (dereference p = 3);
"OK";;
Corrigé 
let dereference p =
    match !p with
    | None -> failwith "Null pointer"
    | Some v -> v

Question 7. Écrire une fonction set_pointer : 'a ptr -> 'a -> unit qui change, ou définit s'il était nul, la valeur pointée par un pointeur.

Tests 
let p = ref None in
set_pointer p 3;
assert(p = ref (Some 3));
set_pointer p 5;
assert(p = ref (Some 5));
"OK";;
Corrigé 
let set_pointer p v =
    p := Some v

Ce n'est pas très pratique d'écrire dereference p ou set_pointer p v. On peut utiliser des raccourcis avec des opérateurs préfixes et infixes. Ainsi, on peut définir :

let (!!) p = dereference p
let (<==) p v = set_pointer p v

On peut alors directement utiliser ces symboles ainsi :

let p = null_pointer () in
p <== 3; (* p pointe vers 3 *)
!!p (* la valeur pointée, donc 3 *)

Pour le moment, l'usage semble un peu limité, on va voir une utilisation possible : initialiser des paramètres dans des boucles.

let recherche t x = (* renvoie un indice de x dans t s'il est présent *)
    let p = null_pointer () in
    for i = 0 to Array.length t - 1 do
        if t.(i) = x
        then p <== i
    done;
    !!p

Si x n'est pas présent dans t, l'appel à !!p déclenche l'erreur Failure "Null pointer".

A link to the future

Cette partie prend un peu d'avance sur le cours sur les listes chaînées.

On va considérer maintenant le type

type link = {
    mutable value : int;    
    next : link ptr
}

Les valeurs de ce type seront appelées des maillons et leur assemblage constitue une chaîne.

Un maillon de type link contient ainsi une valeur, qui peut changer, et un pointeur vers le maillon suivant. Quand il n'y a pas de maillon qui fait suite, on placera le pointeur nul.

En suivant les pointeurs next, on voit ainsi apparaître une chaîne :

<1,|>        |---> <3,NUL>
   |---> <2,|>

Cette chaîne est ainsi une autre manière de représenter une liste comme [1;2;3].

Dans les questions suivantes, on utilise le mot chaîne quand il s'agit de voir non seulement un maillon, mais l'ensemble de la chaîne qui s'en déduit.

Question 8. Écrire une fonction single_link : int -> link qui crée une chaîne comportant un unique maillon contenant une valeur.

Tests 
let l = single_link 3 in
assert(l = { value = 3; next = ref None });
"OK";;
Corrigé 
let single_link x =
    {
        value = x;
        next = null_pointer ()
    }

Question 9. Écrire une fonction link_connect : link -> link -> unit telle que link_connect m1 m2 place m2 comme maillon suivant de m1.

Tests 
let m1 = { value = 3; next = ref None } in
let m2 = { value = 1; next = ref None } in
link_connect m1 m2;
assert(!!(m1.next) = m2);
"OK";;
Corrigé 
let link_connect m1 m2 =
    m1.next <== m2

Question 10. Écrire une fonction is_last : link -> bool qui renvoie un booléen indiquant si un maillon est le dernier.

Remarque : il faut utiliser is_null.

Tests 
let m = { value = 3; next = ref None } in
let m' = { value = 3; next = ref (Some m) } in
assert(is_last m);
assert(not (is_last m'));
"OK";;
Corrigé 
let is_last m = is_null m.next

Question 11. Écrire une fonction next_link : link -> link qui renvoie le maillon suivant après un maillon qui n'est pas le dernier.

Remarque : il faut utiliser dereference ou !!.

Tests 
let m1 = { value = 3; next = ref None } in
let m2 = { value = 1; next = ref None } in
link_connect m1 m2;
assert(next_link m1 = m2);
"OK";;
Corrigé 
let next_link m =
    !!(m.next)

Question 12. Écrire une fonction link_of_list : int list -> link qui crée une chaîne depuis une liste d'entiers non vide.

Tests 
let s = link_of_list [1;2;3] in
let m3 = { value = 3; next = ref None } in
let m2 = { value = 2; next = ref (Some m3) } in
let m1 = { value = 1; next = ref (Some m2) } in
assert(s = m1);
"OK";;
Corrigé 
let rec link_of_list l = match l with
    | [] -> failwith "Empty list"
    | [v] -> single_link v
    | t::q ->
        let m = single_link t in
        let s = link_of_list q in
        link_connect m s;
        m

Dans les fonctions suivantes, on fera les parcours de chaîne uniquement en récursif mais sans match en utilisant is_last et next_link à la place.

Question 13. Écrire une fonction last_link : link -> link qui renvoie le dernier maillon d'une chaîne en descendant, tant que c'est possible, le long des pointeurs next.

Tests 
let l = link_of_list [1;2;3] in
assert(last_link l = { value = 3; next = ref None });
"OK";;
Corrigé 
let rec last_link m =
    if is_last m
    then m
    else last_link (next_link m)

Question 14. Écrire une fonction print_link : link -> unit qui affiche les éléments d'une chaîne.

Tests 
let l = link_of_list [1;2;3] in
print_link l;;
Corrigé 
let rec print_link m =
    print_int m.value;
    if not (is_last m)
    then print_link (next_link m)

Question 15. Écrire une fonction link_to_list : link -> int list qui renvoie la liste des valeurs dans une chaîne.

Tests 
let l = link_of_list [3;2;1] in
let ll = link_to_list l in
assert(ll = [3;2;1]);
"OK";;
Corrigé 
let rec link_to_list m = 
    if is_last m
    then [ m.value ]
    else m.value :: link_to_list (next_link m)

Question 16. En déduire une fonction append : link -> link -> unit qui colle la seconde chaîne à la fin de la première.

Tests 
let m1 = link_of_list [1;2] in
let m2 = link_of_list [3;4] in
append m1 m2;
assert(link_to_list m1 = [1;2;3;4]);
"OK";;
Corrigé 
let append m1 m2 =
    link_connect (last_link m1) m2

Attention : append m m crée une chaîne cyclique, sur laquelle last_link ne termine plus.