Laboratoire 4: Fonctions d'ordre supérieur

Sommaire

Les fonctions d’ordre supérieur sont des fonctions paramétrées par une ou plusieurs fonctions et/ou qui renvoient une fonction. Le but de ce TP est d’utiliser et d’écrire de telles fonctions et de se familiariser avec cette notion.

Premières fonctions d’ordre supérieures et curryfication

Dans cet exercice, on utilisera les deux définitions suivantes :

let square (x : int) : int = x * x
let my_list = [3; 12; 3; 40; 6; 4; 6; 0]

Exprimer le type de la fonction f_sum paramétrée par une fonction f ainsi que deux entiers a et b et qui calcule f(a) + f(b).

Écrire la fonction f_sum.

# f_sum square 2 3;;
- : int = 13

# f_sum (fun x -> x + 1) 2 3;;
- : int = 7

Redéfinir la fonction f_sum en utilisant exclusivement le mot clé function.
Lier aux noms f1, f2, f3, f4 et f5 des définitions de fonctions de sorte à vérifier les types suivants.

val f1 : int -> int -> int = <fun>
val f2 : (int -> int) -> int = <fun>
val f3 : (int -> int) -> int -> int = <fun>
val f4 : (int -> int) -> (int -> int) = <fun>
val f5 : ((int -> int) -> int) -> int = <fun>

Rappel : les parenthèses dans les expressions de types portant sur les flèches -> associent vers la droite. Ainsi, le type t1 -> (t2 -> t3) est équivalent au type t1 -> t2 -> t3.

Sans définir de nouvelle fonction et en utilisant la fonction square de manière appropriée, créer la liste des carrés des éléments de my_list. Utiliser la fonction List.map.

- : int list = [9; 144; 9; 1600; 36; 16; 36; 0]

Sans définir de nouvelle fonction et en utilisant la multiplication (attention, il y a une astuce à suivre pour transformer l’opérateur * en fonction) de manière appropriée, créer la liste des doubles des éléments de my_list.

- : int list = [6; 24; 6; 80; 12; 8; 12; 0]

Exprimer le type de la fonction make_list sachant qu’elle est paramétrée par une fonction make (dont l’unique paramètre est de type unit) et un entier n et qui renvoie une liste de n éléments fabriqués avec la fonction make.
Écrire la fonction make_list.

# let f () = 0;;
val f : unit -> int = <fun>
# make_list f 8;;
- : int list = [0; 0; 0; 0; 0; 0; 0; 0]

En utilisant make_list et la fonction appropriée du module Random, créer une liste de 64 booléens générés aléatoirement. Il est possible d’utiliser Random.bool () pour engendrer aléatoirement un booléen de manière équiprobable.
En utilisant make_list et une fonction anonyme, créer une liste de 16 entiers (compris entre 0 et 127) générés aléatoirement. Il est possible d’utiliser Random.int n pour engendrer aléatoirement et de manière équiprobable un entier compris entre 0 et n - 1.

Sur une ligne

Dans cet exercice, on utilisera les définitions suivantes :

let entiers = [2; 5; 7; 3; 12; 4; 9; 2; 11];;
let animaux = ["Wombat"; "aXolotl"; "pangolin"; "suricate"; "paresseuX"; "quokka"; "lemurien"];;

Toutes les expressions demandées par les descriptions suivantes doivent être sous la forme d’appels de fonctions d’ordre supérieur du module List (comme List.map, List.for_all, List.filter, List.fold_left, etc.). Il est interdit de définir de nouvelles fonctions non anonymes.

Note: penser à consulter la documentation des modules List, Char et String.

Écrire de telles expressions pour :

calculer la liste des longueurs des chaînes de caractères de la liste animaux;

- : int list = [6; 7; 8; 8; 9; 6; 8]

calculer la liste de tous les animaux de la liste animaux écrits en majuscules ;

- : string list = ["WOMBAT"; "AXOLOTL"; "PANGOLIN"; "SURICATE"; ...]

calculer la liste des chaînes de la liste animaux qui sont écrites en minuscules ;

- : string list = ["pangolin"; "suricate"; "lemurien"]

calculer la liste des noms des animaux de longueurs paires ;

- : string list = ["Wombat"; "pangolin"; "suricate"; "quokka"; "lemurien"]

calculer la liste suivante, construite à partir de la liste entiers ;

- : (int * string) list = [(2, "pair"); (5, "impair"); (7, "impair"); 
    (3, "impair"); (12, "pair"); (4, "pair"); (9, "impair"); (2, "pair"); 
    (11, "impair")]

calculer une liste de listes composées de n fois la valeur de n, pour chaque entier n dans la liste entiers ;

- : int list list = [[2; 2]; [5; 5; 5; 5; 5]; [7; 7; 7; 7; 7; 7; 7]; [3; 3; 3];
    [12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12]; [4; 4; 4; 4]; ... ]

tester s’il existe une élément de la liste animaux qui commence par le caractère 's' ;
tester si tous les éléments de la liste animaux sont de longueur congrue à 2 modulo 5.

Replis

Écrire les fonctions suivantes de sorte à avoir un corps de fonction qui tienne sur une seule ligne et utilise des fonctions d’ordre supérieur :

sum l qui renvoie la somme des éléments d’une liste d’entiers l ;
size l qui renvoie la longueur d’une liste l ;
last l qui renvoie le dernier élément d’une liste l non vide ;
nb_occ e l qui renvoie le nombre d’occurrences d’un élément e dans l ;
max_list l qui renvoie le maximum de la liste l non vide ;
average l qui renvoie la moyenne (de type float) des nombres entiers de la liste l. Il est interdit d’utiliser size et sum.

Rappel : la plupart de ces fonctions ont été implantées sans utiliser de fonctions d’ordre supérieur lors du labo 3

Prédicats sur les listes

Un prédicat est une fonction qui teste si une propriété est vérifiée par son paramètre (et renvoie donc un booléen). Par exemple :

# let is_even = fun x -> x mod 2 = 0;;
val is_even : int -> bool = <fun>

# is_even 0, is_even 1, is_even 2;;
- : bool * bool * bool = (true, false, true)

Écrire la fonction my_for_all paramétrée par un prédicat p et une liste l et qui teste si tous les éléments de l vérifient p. Comme contraintes, cette fonction ne doit rien utiliser du module List (autre que l’opérateur de construction :: et bien sûr la liste vide []).
Écrire la fonction my_for_all2 qui fait la même chose que my_for_all mais qui utilise la fonction fold_left du module List.
Si ce n’est pas déjà fait, réécrire la fonction my_for_all2 sans utiliser la fonction map du module List.
Écrire la fonction my_for_all3 qui fait la même chose que my_for_all mais qui utilise la fonction fold_right du module List.
Écrire la fonction my_exists paramétrée par un prédicat p et une liste l et qui teste s’il existe un élément de l vérifiant p. Cette fonction doit respecter les contraintes exposées dans la question sur my_for_all.
Écrire la fonction none paramétrée par un prédicat p et une liste l et qui teste si aucun des éléments de la liste ne vérifie p. Cette fonction doit respecter les contraintes exposées dans la question sur my_for_all.
Écrire la fonction not_all paramétrée par un prédicat p et une liste l et qui teste s’il existe un élément de l ne vérifiant pas p. Cette fonction doit respecter les contraintes exposées dans la question sur my_for_all.
Écrire la fonction ordered paramétrée par un prédicat binaire p et une liste \([a_1; \dots; a_n]\) et qui teste si toutes les expressions \(p~a_i~ a_{i + 1}\) sont vraies pour tout \(1 \leq i \leq n - 1\).

# ordered (<) [1; 2; 3];;
- : bool = true

# ordered (<) [1; 4; 3];;
- : bool = false

# ordered (fun x y -> x + y >= 1) [1; 4; -3; 6];;
- : bool = true  

# ordered (fun x y -> x + y >= 1) [1; 4; -5; 6];;
- : bool = false

Écrire la fonction filter2 paramétrée par un prédicat binaire p et deux listes \([a_1; \dots; a_n]\) et \([b_1; \dots; b_n]\) et qui renvoie la liste des couples \((a_i, b_i)\) tels que l’expression \(p~a_i~ b_i\) est vraie.

# filter2 (<) [2; 2; 3] [1; 4; 5];;
- : (int * int) list = [(2, 4); (3, 5)]

Génération exhaustive de permutations

Une permutation d’une liste l est une liste l' qui contient les mêmes éléments que ceux de l mais dans un ordre potentiellement différent.

Écrire une fonction perm l qui renvoie la liste de toutes les permutations de la liste l.

# perm [1;2];;
- : int list list = [[1; 2]; [2; 1]]

# perm [1;2;3];;
- : int list list =
[[1; 2; 3]; [2; 1; 3]; [2; 3; 1]; [1; 3; 2]; [3; 1; 2]; [3; 2; 1]]

# perm [1;2;3;4];;
- : int list list =
[[1; 2; 3; 4]; [2; 1; 3; 4]; [2; 3; 1; 4]; [2; 3; 4; 1]; [1; 3; 2; 4];
 [3; 1; 2; 4]; [3; 2; 1; 4]; [3; 2; 4; 1]; [1; 3; 4; 2]; [3; 1; 4; 2];
 [3; 4; 1; 2]; [3; 4; 2; 1]; [1; 2; 4; 3]; [2; 1; 4; 3]; [2; 4; 1; 3];
 [2; 4; 3; 1]; [1; 4; 2; 3]; [4; 1; 2; 3]; [4; 2; 1; 3]; [4; 2; 3; 1];
 [1; 4; 3; 2]; [4; 1; 3; 2]; [4; 3; 1; 2]; [4; 3; 2; 1]]