Formation programmation par l’exemple en Caml, tutoriel & guide de travaux pratiques en pdf.

TRAITEMENT DES LISTES

La liste chaînée est la structure de données fourre-tout la mieux adaptée à la récursivité car elle est représentée par un doublet d’adresses. La première pointant sur une valeur (la tête de la liste « hd ») et la seconde sur la sous-liste qui suit (la queue « tl » c’est à dire également un doublet d’adresses. La liste vide [] joue donc toujours le rôle de dernier doublet. L’opérateur infixe double deux points :: (« cons » en Lisp, : en Haskell, . (le point) en ML et dans les anciens Lisp, enfin la barre | en Prolog) construit une liste en ajoutant le premier argument en tête du second qui doit être une liste.
0 :: [];; p int list = [0] 1 :: 2 :: 3 :: [];; p int list = [1; 2; 3] Les autres fonctions commodes sur les listes sont :
– hd (le premier élément, List.hd en Ocaml), – tl (la queue de la liste privée de son premier élément, List.tl en Ocaml), – @ est la concaténation des listes (rappel ^ est celle des chaînes) – enfin [] est la liste vide et le point virgule est le séparateur au sein d’une liste. – rev est l’opération miroir.
hd [1; 2; 3 ];; p int = 1 tl [« z »; « d »; « f »] ;; p string list = [« d »; « f »] [1; 2; 3; 4; 5; 6] @ [7; 8; 9];; p int list = [1; 2; 3; 4; 5; 6; 7; 8; 9] rev [1;2;3;4;5;6;7];; p int list = [7; 6; 5; 4; 3; 2; 1] Nous redéfinissons ci-dessous quelques fonctions de base à titre d’exercice, il faut bien entendu utiliser celles qui existent dans Caml.
let rec long = fun [] -> 0 | (a :: q) -> 1 + long q;; (* déjà prédéfinie list_length *) p long : ‘a list -> int = <fun>let rec app x = fun [] -> false | (y :: q) -> (x = y) or (app x q);; (* appartenance déjà prédéfinie avec mem ou List.mem en Ocaml*) p app : ‘a -> ‘a list -> bool = <fun>
28 Programmation par l’exemple en Caml
Exemples app 1 [ 4; 2; 5; 1; 8];; p bool = true app 1 [2; 5];; p bool = false let rec concat = fun [] q -> q | (a :: q) r -> a :: concat q r;; (* concaténation de deux listes prédéfinie de manière infixe avec le symbole @ *)
La fonction qui donne l’élément de rang n (à partir de 0) d’une liste est souvent commode, elle peut être définie avec un argument structuré, bien que l’interpréteur signalera que tous les cas ne sont pas considéré.
let rec nth (a::q) = fun 0 -> a | n -> nth q (n – 1);; (* n-ième élément d’une liste à partir de 0*)
let rec tete q n = if q = [] or n = 0 then [] else (hd q):: (tete (tl q) (n – 1));; (* les n premiers éléments de q*)
let rec queue q n = if q = [] or n = 0 then q else queue (tl q) (n – 1);; (* tout sauf les n premiers éléments de q *)
Deux prédicats quantificateurs « exists » et « for_all » commodes pour les listes : exists (fun x -> (x=2)) [1;8;2;6];; p bool = true exists (fun x -> (x=2)) [1;6;9];; p bool = false for_all (fun x -> (x=2)) [2;9];; p bool = false for_all (fun x -> (x=2)) [2;2];; p bool = true Signalons encore la fonction « union » éliminant les répétitions dans le premier argument :
union [1;2;3;3;4] [2;3;4;5;5];; p int list = [1; 2; 3; 4; 5; 5] L’association « assoc » donne la première ordonnée possible pour une abscisse et une liste de couple en second argument, cette fonction, facile à redéfinir existe en Ocaml sous le nom de « List.assoc » :
assoc 2 [(1, 5) ;(5, 6); (8, 2); (2, 7); (0, 4); (2, 5)];; p int = 7

1. Aplatissement d’une liste
L’aplatissement est en quelque sorte le retrait de toutes les parenthèses intérieures au sein d’une liste (« List.flatten » en Ocaml) .
let rec aplatir = fun [] -> [] | ([] :: q) -> aplatir q | ((a :: q) :: r) -> a :: aplatir (q :: r);; p aplatir : ‘a list list -> ‘a list = <fun> aplatir [[1; 2]; [3; 4; 5]; [6; 7]; [8]];; p int list = [1; 2; 3; 4; 5; 6; 7; 8]

2. Retrait d’un élément dans une liste
let rec ret x = fun [] -> [] | (a :: q) -> (if x = a then q else a :: (ret x q));; p ret : ‘a -> ‘a list -> ‘a list = <fun> ret 4 [2; 3; 5; 4; 7; 5; 4; 8; 4];; p [2; 3; 5; 7; 5; 4; 8; 4].
Pour le retrait de toutes les occurrences :
let rec retout x = fun [] -> [] | (a :: q) -> (if x = a then (retout x q) else a :: (retout x q));; p retout : ‘a -> ‘a list -> ‘a list = retout 4 [2; 3; 5; 4; 7; 5; 4; 8; 4];; p [2; 3; 5; 7; 5; 8]

3. Somme termes à termes
Etant donné deux listes, on souhaite obtenir la liste des sommes des éléments de même rang sur la plus courte longueur.
let rec som = fun (a::q) (b::r) -> (a + b) :: (som q r) | [] _ -> [] | _ [] -> [];; p som : int list -> int list -> int list = som [1; 2; 3] [3; 4; 5; 6];; p int list = [4; 6; 8]

4. Transformation d’une liste de couple en couple de listes
Soient deux listes de couples, on forme de façon récursive terminale, le couple formé par la liste m de toutes les abscisses et celle n des ordonnées.
let split lc = split’ [] [] lc (* prédéfinie mais renvoie les éléments à l’endroit *) where rec split’ m n = fun [] -> m, n | ((x, y)::r) -> split’ (x::m) (y::n) r;;p split : (‘a * ‘b) list -> ‘a list * ‘b list = split [(1, « a »); (2, « z »); (3, « e »); (4, « r »); (5, « t »); (6, « y »)];; p int list * string list = [6; 5; 4; 3; 2; 1], [« y »; « t »; « r »; « e »; « z »; « a »]