Boris ENG

PhD Student in Computer Science, Team LoVe, LIPN (Université Sorbonne Paris Nord, France) [last name][first name]@hotmail.fr
« Return to Teaching

Itérateurs en OCaml

Quand on écrit des fonctions récursives sur les listes, on remarque qu’une façon d’écrire les programmes revient souvent :

1
2
3
4
let rec somme l =
    match l with
    | [] -> 0
    | h::t -> h + somme t

On rassemble/connecte les éléments de la liste par un opérateur (“+” dans le cas de la somme) pour terminer sur un élément terminal (“0” dans notre cas). On peut généraliser cette manière de programmer avec une fonction et un élément terminal tous deux génériques :

1
2
3
4
let rec fold_right f l base =
    match l with
    | [] -> base
    | h::t -> f h (fold_right f t base)

Cette fonction calcule f x1 (f x2 (f x3 base)) pour [x1; x2; x3] et existe en OCaml sous le nom de List.fold_right. Elle peut être utilisée pour écrire un grand nombre de fonction de façon très simple. Par exemple, le calcul de la somme peut être remplacé par

1
let somme = List.fold_right (+) l 0

De la même manière, la fonction List.fold_left calculant f (f (f acc x1) x2) x3 pour [x1; x2; x3] généralise les fonctions récursives avec accumulateurs :

1
2
3
4
let rec fold_left f acc l =
    match l with
    | [] -> acc
    | x::s -> fold_left f (f acc x) s

Les deux fonctions sont des sortes de “pliages” de la liste deux à deux jusqu’à obtenir un résultat, d’où le terme “fold” signifiant “pli”.

Exercice 1

Écrivez les fonctions suivantes en utilisant List.fold_right ou List.fold_left (parfois l’un est plus adapté que l’autre mais d’autres fois les deux sont utilisables).

  1. append l1 l2 qui concatène deux listes. Par exemple append [1; 2] [3; 4; 5] = [1; 2; 3; 4; 5].

  2. flatten l qui concaténe toutes les listes d’une liste de listes. Par exemple flatten [[1; 2]; [3; 4; 5]; []] = [1 ; 2; 3; 4; 5].

  3. reverse l qui inverse les éléments d’une liste. Par exemple reverse [1; 2; 3] = [3; 2; 1].

  4. mem x l qui vérifie la présence d’un élément dans une liste. Par exemple mem 3 [2; 3] = true et mem 3 [] = false.

  5. length l qui calcule le nombre d’élément dans une liste. Par exemple length [1; 2; 3] = 3.

  6. map f l qui applique une fonction à tous les éléments d’une liste. Par exemple map f [1; 2; 3] = [f 1; f 2; f 3].

  7. filter p l qui extrait tous les éléments qui valident un prédicat. Supposons qu’on ait un prédicat pair. Par exemple filter pair [1; 2; 3; 4] = [2; 4].

  8. exists p l qui vérifie si un élément d’une liste valide un prédicat. Par exemple exists pair [1; 2; 3] = true et exists pair [1; 3; 7] = false.

Exercice 2

Un arbre binaire est une structure de donnée définie de la façon suivante :

1
type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree

On définit un itérateur sur les arbres binaire rassemblant les sommets par une opération sur les noeuds pour calculer un résultat :

1
2
3
let rec foldtree base f = function
  | Leaf -> base
  | Node (x, l, r) -> f x (foldtree base f l) (foldtree base f r)

Définir les fonctions suivantes :

  1. size : 'a tree -> int qui calcule la taille (nombre de sommets) d’un arbre binaire.

  2. depth : 'a tree -> int qui calcule la profondeur (plus long chemin entre la racine et une feuille) d’un arbre binaire.

  3. elems : 'a tree -> 'a list qui produit la liste des éléments d’un arbre binaire.

  4. Comment définir un arbre avec un nombre quelconque de branches ? Comment définir un itérateur sur un tel arbre ? Réécrivez les fonctions ci-dessus avec cette nouvelle définition.