Newer
Older
## 1. Manipulations de listes à l'aide de fonctions génériques
On considère les fonctions suivantes prédéfinies en OCaml, voir [la documentation du module `List`](https://v2.ocaml.org/api/List.html) :
- **`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 exactement 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`.
> 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.
En OCaml, on peut voir un 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` s'ils sont différents. Ainsi `(!=) 1 2` renvoie `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]`.
> Recoder `List.map`, `List.filter` et `List.for_all`.
**Faire valider votre progression par votre chargé de TP**
Dans cet exercice, on reprend les fonctionnalités développées dans la section 1. du [TP4](tp4.md), 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`.
**Faire valider votre progression par votre chargé de TP**
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 agrè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 intelligemment `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 intelligemment `fold_left_arbre`, recoder `reduce`.
> Recoder `list_of_arbre` en utilisant `fold_left_arbre`.
**Faire valider votre progression par votre chargé de TP**