tp5.md

TP5: Parcours génériques de structure et projets dune

1. Manipulations de listes à l'aide de fonctions génériques

On considère les fonctions suivantes prédéfinies en OCaml:

• List.map: ('a -> 'b) -> 'a list -> 'b list Cette fonction transforme une liste en utilisant la fonction passée en paramètre pour transformer les éléments un par un. Ainsi List.map f [x1; x2; x3; ... ] renverra une liste égale à [f x1; f x2; f x3; ... ].
• List.filter: ('a -> bool) -> 'a list -> 'a list Cette fonction transforme une liste en utilisant la fonction passée en paramètre conserver uniquement certains éléments. Ainsi List.filter f [x1; x2; x3; ... ] renverra une liste contenant exatctement les xi pour lesquels f xi vaut true.
• List.for_all: ('a -> bool) -> 'a list -> bool Cette fonction indique si une fonction renvoie vrai pour tous les éléments d'une liste. Ainsi List.for_all f [x1; x2; x3; ... ] renvoie true si pour tous les xi, on a f xi vaut true.

1.1. Utilisation des fonctions sur les listes

En utilisant List.map, coder les fonctions suivantes:

• Une fonction f1 qui prend une liste d'int et renvoie la liste de leur représentation sous forme de string.
• Une fonction f2 qui prend un int x et une liste d'int l et renvoie la liste transformée en multipliant chaque élément de l par x.
• Une fonction f3 qui prend deux int x et y et une liste d'int l et renvoie la liste (de bool) indiquant pour chacun des éléments de l s'il est bien compris entre x et y.

Bien tester vos fonctions avec assert.

En utilisant List.filter, coder les fonctions suivantes:

• Une fonction f4 qui prend deux int x et y et une liste d'int l et renvoie la liste des éléments de l qui sont compris entre x et y.
• Une fonction f5 qui prend une liste de liste d'int et renvoie la liste sans les (sous-)listes vides.

Bien tester vos fonctions avec assert.

En OCaml, on peut voir une opérateur comme une fonction en le plaçant tout seul entre parenthèses. Ainsi (!=) est une fonction qui prend deux arguments et renvoie true si il sont égaux. Ainsi (!=) 1 2 revoie true, alors que (!=) 1 1 renvoie false.

Recoder la fonction f5 sans le mot clé fun en utilisant une application partielle de (!=).

On peut bien sûr combiner List.map et List.filter.

Coder une fonction f6 qui prend une liste d'int option l et renvoie une liste d'int contenant les valeurs int contenues dans l. Par exemple, f6 [ Some 3; None; Some 18; Some 42; None; Some 37; None] vaudra [3; 18; 42; 37].

1.2 Recodage de fonctions sur les listes

Recoder List.map, List.filter et List.for_all.

2. Arbre n-aires: recodage

Dans cet exercice, on reprend les fonctionnalités développées dans la section 1. du TP4, mais en les recodant avec les fonctions déjà fournies avec OCaml.

Remarque: en OCaml on peut écrire fun x y -> ... à la place de fun x -> fun y -> ....

2.1. Recodage de quelques fonctions de base avec la bibliothèque standard OCaml

Reprendre le type 'a arbre_n du TP4, section 1.1

On pourra reprendre les tests écrits lors du TP4.

Recoder la fonction hauteur_arbre sans utiliser hauteur_foret, mais en appelant directement List.map et List.fold_left pour extraire les hauteurs des arbres fils et trouver la hauteur maximale parmi celles-ci.

Recoder list_of_arbre_aux en utilisant List.fold_right pour remplacer les appels à list_of_foret. Encapsuler list_of_arbre_aux avec un let ... in ... dans la définition de list_of_arbre. On écrira le let avant de prendre l'argument de list_of_arbre.

2.2. Gestion d'option, fold et minimum

Pour gérer proprement le calcul du minimum, on va s'équiper d'un décorateur lift_option_2 ayant le comportement suivant. Soit f: 'a -> 'a -> 'a. On suppose que g = lift_option_2 f. Alors g aura le type 'a option -> 'a -> 'a option. Si le premier argument de g est None, alors g renvoie Some x si x est son second argument. Sinon g renvoie Some (f y x) où y est la valeur contenue dans son premier argument et x est son second argument.

Définir lift_option_2 en commençant par préciser son type. Tester avec assert en passant la fonction min à lift_option_2.

On veut à présent définir fold_left_arbre qui aggrège une valeur via un accumulateur à la manière de List.fold_left, mais en parcourant un arbre et pas une liste.

Définir le type, puis coder fold_left_arbre. On pourra utiliser intelligement List.fold_left pour gérer le cas des Noeud. Tester en calculant la somme des éléments d'arbres bien choisis.

On peut remarquer que reduce du TP4 ressemble énormément à fold_left_arbre: les deux vont parcourir les éléments de l'arbre les combinant via un accumulateur. Elles diffèrent cependant sur les points suivants:

• reduce prend en argument une fonction de type 'a -> 'a -> 'a alors que fold_left_arbre prend une fonction un peu plus générique de type 'b -> 'a -> 'b.
• reduce renvoie forcément une option alors que fold_left_arbre renvoie uniquement une option si 'b est lui-même une option.

En utilisant intelligement fold_left_arbre, recoder reduce.

Recoder list_of_arbre en utilisant fold_left_arbre.