TP 4 : Listes

List est un module OCaml qui contient de nombreuses fonctions sur les listes : https://ocaml.org/api/List.html.
Dans un sujet de concours, vous avez le droit d'utiliser ces fonctions sauf si l'énoncé demande de le recoder (exemple : si l'énoncé demande de coder une fonction calculant la taille d'une liste, il est implicitement interdit d'utiliser List.length...).

List.mem¶

Si l est une liste, List.mem e l détermine si e est un élément de l.

Exercice

1. Quel est le type de List.mem? Le deviner puis vérifier avec OCaml.
2. Réécrire List.mem (en appelant votre fonction mem, par exemple).

Solution

In [9]:

(* 1. *)
List.mem;;

(* 2. *)
let rec mem l e = match l with
    | [] -> false
    | x::q -> x = e || mem q e;;
    
let l = [1; 5; 2] in
assert ((mem l 5) && not (mem l 3))

(* 1. *) List.mem;; (* 2. *) let rec mem l e = match l with | [] -> false | x::q -> x = e || mem q e;; let l = [1; 5; 2] in assert ((mem l 5) && not (mem l 3))

Out[9]:

- : 'a -> 'a list -> bool = <fun>

Out[9]:

val mem : 'a list -> 'a -> bool = <fun>

Out[9]:

- : unit = ()

List.iter¶

Si l est une liste et f une fonction, List.iter f l applique f sur chaque élément de l.

Exercice

Réécrire List.iter (en appelant votre fonction iter, par exemple).

Solution

In [18]:

let rec iter f l = match l with
    | [] -> ()
    | e::q -> f e; iter f q

let rec iter f l = match l with | [] -> () | e::q -> f e; iter f q

Out[18]:

val iter : ('a -> 'b) -> 'a list -> unit = <fun>

List.filter¶

Si l : 'a list est une liste et f : 'a -> bool une propriété, List.filter f l renvoie les éléments de l vérifiant f.

Exercice

1. Que renvoie List.filter (fun x -> x > 0) [1; -2; 3; 0] ?
2. Réécrire la fonction List.filter (en l'appelant filter, par exemple).

Solution

In [36]:

(* 1. *)
List.filter (fun x -> x > 0) [1; -2; 3; 0];;

(* 2. *)
let rec filter f l = match l with
    | [] -> []
    | e::q -> if f e then e::filter f q else filter f q;;
filter (fun x -> x > 0) [1; -2; 3; 0];;

(* 1. *) List.filter (fun x -> x > 0) [1; -2; 3; 0];; (* 2. *) let rec filter f l = match l with | [] -> [] | e::q -> if f e then e::filter f q else filter f q;; filter (fun x -> x > 0) [1; -2; 3; 0];;

Out[36]:

- : int list = [1; 3]

Out[36]:

val filter : ('a -> bool) -> 'a list -> 'a list = <fun>

Out[36]:

- : int list = [1; 3]

List.map¶

Exercice

1. Écrire une fonction somme pour calculer la somme des termes d'une liste d'entiers.
2. Écrire une fonction range telle que range n renvoie la liste des entiers de 0 à n.
3. List.map est une fonction telle que, si f est une fonction et l une liste, List.map f l renvoie une liste obtenue à partir de l en appliquant f sur chaque élément.
   Par exemple, List.map (fun x -> 2*x) [2; 5; 42] renvoie [4; 10; 84].
   Quel est le type de List.map? Le deviner puis vérifier avec OCaml.
4. Réécrire List.map (en appelant votre fonction map, par exemple).
5. Calculer $\sum_{k=0}^{10} k^4$ en utilisant les fonctions précédentes.

Solution

In [13]:

(* 1. *)
let rec somme = function 
    | [] -> 0
    | e::q -> e + somme q;;

(* 2. *)
let rec range n = 
    if n = 0 then [0]
    else n::range (n - 1);;
    
(* 3. *)
List.map;;

(* 4. *)
let rec map f l = match l with
    | [] -> []
    | e::q -> f e::map f q;;

(* 5. *)
somme (map (fun x -> x*x*x*x) (range 10))

(* 1. *) let rec somme = function | [] -> 0 | e::q -> e + somme q;; (* 2. *) let rec range n = if n = 0 then [0] else n::range (n - 1);; (* 3. *) List.map;; (* 4. *) let rec map f l = match l with | [] -> [] | e::q -> f e::map f q;; (* 5. *) somme (map (fun x -> x*x*x*x) (range 10))

Out[13]:

val somme : int list -> int = <fun>

Out[13]:

val range : int -> int list = <fun>

Out[13]:

- : ('a -> 'b) -> 'a list -> 'b list = <fun>

Out[13]:

val map : ('a -> 'b) -> 'a list -> 'b list = <fun>

Out[13]:

- : int = 25333

List.for_all et List.exists¶

Si l : 'a list est une liste et f : 'a -> bool une propriété :

• List.for_all f l vérifie que tous les éléments de l satisfont f ($\forall e \in l, ~f(e)$)
• List.exists f l vérifie qu'au moins un élément de l satisfait f ($\exists e \in l, ~f(e)$)

Exercice

1. En utilisant une de ces fonctions et l'application partielle de fonction, définir une fonction positif : int list -> bool testant si tous les éléments d'une liste sont positifs.
2. En utilisant une de ces fonctions et l'application partielle de fonction, définir une fonction pair : int list -> bool testant si il y a au moins un élément d'une liste qui est pair.

Solution

In [27]:

(* 1. *)
let positif = List.for_all (fun x -> x >= 0);;
assert ((positif [3; 2; 9]) && not (positif [2; -2; 9]))

(* 2. *)
let pair = List.exists (fun x -> x mod 2 = 0);;
assert ((pair [3; 2; 9]) && not (pair [3; 1; 9]))

(* 1. *) let positif = List.for_all (fun x -> x >= 0);; assert ((positif [3; 2; 9]) && not (positif [2; -2; 9])) (* 2. *) let pair = List.exists (fun x -> x mod 2 = 0);; assert ((pair [3; 2; 9]) && not (pair [3; 1; 9]))

Out[27]:

val positif : int list -> bool = <fun>

Out[27]:

- : unit = ()

Out[27]:

val pair : int list -> bool = <fun>

Out[27]:

- : unit = ()

Liste de listes¶

Exercice

1. Écrire une fonction add : 'a -> 'a list list -> 'a list list telle que add e ll renvoie une liste de listes obtenues en ajoutant e à chaque liste de ll.
   Par exemple, add 2 [[1; 2]; [7; 4]] doit renvoyer [[2; 1; 2]; [2; 7; 4]].
2. Écrire une fonction parties : 'a list -> a list list telle que parties l renvoie une liste composée de tous les sous-ensembles d'éléments de l.
   Par exemple, parties [1; 2; 1] peut renvoyer [[]; [1]; [2]; [2; 1]; [1]; [1; 1]; [1; 2]; [1; 2; 1]].
3. Écrire une fonction decomposition telle que, si l est une liste d'entiers et n un entier, decomposition n l renvoie le nombre de façon d'écrire n comme somme d'éléments de l.
   Par exemple, decomposition 6 [1; 2; 3; 5] doit renvoyer 2, car on peut écrire $6 = 1 + 2 + 3$ et $6 = 1 + 5$.
4. Modifier la fonction précédente pour renvoyer la liste de toutes les possibilités (chaque possibilité étant une liste).

Solution

In [37]:

(* 1. *)
let rec add e ll = match ll with
    | [] -> []
    | l::q -> (e::l)::add e q;;
add 2 [[1; 2]; [7; 4]];;

(* 2. *)
let rec parties = function
    | [] -> [[]]  (* il y a l'ensemble vide *)
    | e::q -> let parties_q = parties q in
              parties_q @ (add e parties_q) in
parties [1; 2; 1];;

(* 3. *)
let rec decomposition n l = match l with
    | [] -> if n = 0 then 1 else 0
    | e::q -> decomposition (n - e) q + decomposition n q in
decomposition 6 [1; 2; 3; 5];;
(* Remarque : on pourrait améliorer cette fonction avec de la programmation dynamique *)

(* 4. *)
let rec decomposition n l = match l with
    | [] -> if n = 0 then [[]] else []
    | e::q -> add e (decomposition (n - e) q) @ decomposition n q;;
decomposition 6 [1; 2; 3; 5]

(* 1. *) let rec add e ll = match ll with | [] -> [] | l::q -> (e::l)::add e q;; add 2 [[1; 2]; [7; 4]];; (* 2. *) let rec parties = function | [] -> [[]] (* il y a l'ensemble vide *) | e::q -> let parties_q = parties q in parties_q @ (add e parties_q) in parties [1; 2; 1];; (* 3. *) let rec decomposition n l = match l with | [] -> if n = 0 then 1 else 0 | e::q -> decomposition (n - e) q + decomposition n q in decomposition 6 [1; 2; 3; 5];; (* Remarque : on pourrait améliorer cette fonction avec de la programmation dynamique *) (* 4. *) let rec decomposition n l = match l with | [] -> if n = 0 then [[]] else [] | e::q -> add e (decomposition (n - e) q) @ decomposition n q;; decomposition 6 [1; 2; 3; 5]

Out[37]:

val add : 'a -> 'a list list -> 'a list list = <fun>

Out[37]:

- : int list list = [[2; 1; 2]; [2; 7; 4]]

Out[37]:

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

Out[37]:

- : int = 2

Out[37]:

val decomposition : int -> int list -> int list list = <fun>

Out[37]:

- : int list list = [[1; 2; 3]; [1; 5]]