VIII — Le type list d’OCaml

Entraînement

Le fonctionnement reste le même qu’avant : dans le quiz, les réponses deviennent vertes quand elles sont justes, et il y a des exercices corrigés ensuite.

On a le code suivant :

let ajouter element liste =
  liste @ [ element ]

let rec taille liste =
  match liste with
  | [] -> 0
  | x :: suite -> 1 + (taille suite)

let additionner n liste =
  match liste with
  | [] -> []
  | x :: suite -> (x + n) :: (additionner n suite)

Que donnent ces expressions ?

ajouter 42 [ 1 ; 2 ]

(taille [ 1 ; 1 ; 1 ]) + (taille [ 5 ; 6; 30; 180; 0 ])

(additionner 2 [0 ; 5]) @ (additionner 10 [])

En utilisant les fonctions du module List, écrivez les fonctions suivantes :

plus_grande : prend deux listes et renvoie la plus grande des deux ;
fib : prend un entier n et renvoie la liste des n premiers entiers de la suite de Fibonacci. Une fonction auxiliaire qui donne le n-ième terme de cette suite peut sans doute aider ;
quarante_deux : qui ajoute 42 à tous les éléments d’une liste d’entiers ;
moyenne : qui fait la moyenne d’une liste de flottants.

Proposition de correction

let plus_grande liste_a liste_b =
  if (List.length liste_a) > (List.length liste_b) then
    liste_a
  else
    liste_b

let fib n =
  (* On définit une fonction auxiliaire qui donne un terme de la suite *)
  let rec fib_x x =
    if x < 2 then
      1
    else
      (fib_x (x - 1)) + (fib_x (x - 2))
  in
  List.init n fib_x (* On crée une liste de n éléments qui sont les termes de la suite *)

let ajouter_42 x = x + 42
let quarante_deux liste = List.map ajouter_42 liste

let addition x y = x +. y
let moyenne liste =
  let total = List.fold_left addition 0.0 liste in
  total /. (List.length liste)

Proposition de correction (avec fun et des applications partielles)

(* Cette fonction ne change pas par rapport à la première correction *)
let plus_grande liste_a liste_b =
  if (List.length liste_a) > (List.length liste_b) then
    liste_a
  else
    liste_b

(* Celle-ci non plus, car on ne peut pas faire de fonctions récursives avec fun *)
let fib n =
  (* On définit une fonction auxiliaire qui donne un terme de la suite *)
  let rec fib_x x =
    if x < 2 then
      1
    else
      (fib_x (x - 1)) + (fib_x (x - 2))
  in
  List.init n fib_x (* On crée une liste de n éléments qui sont les termes de la suite *)

(* Ici on utilise bien fun et une application partielle *)
let quarante_deux = List.map (fun x -> x + 42)

(* Ici on ne peut pas utiliser d’application partielle, mais on utilise fun : *)
let moyenne liste =
  List.fold_left (fun x y -> x +. y) 0.0 liste in
  total /. (List.length liste)

En utilisant les fonctions du module List, écrivez une fonction qui fait le produit des valeurs absolues des nombres pairs d’une liste d’entiers (c’est très tordu dit comme ça, mais relisez, vous allez comprendre). Si vous voulez vérifier que votre code marche, la liste [ 13 ; 27 ; -84 ; -12 ; 85; -7 ] devrait donner 1008.

Propositions de correction

Première version : plus longue mais plus simple à comprendre.

let abs x = if x > 0 then -x else x (* Note : cette fonction est prédéfinie en OCaml, on n’aurait même pas besoin de l’écrire. *)
let est_pair x = (x mod 2) = 0
let produit p x = p * x

let calcul_etrange l =
  let liste_abs = List.map abs l in
  let liste_filtree = List.filter est_pair liste_abs in
  List.fold_left produit 1 liste_filtree

Deuxième version : on utilise fun pour tout compacter en une seule expression.

let calcul_etrange l =
  List.fold_left
    (fun p x -> p * x)
    1
    (List.filter
      (fun x -> (x mod 2) = 0)
      (List.map
        (fun x -> if x < 0 then -x else x)
        l
      )
    )

Troisième version (bonus, il y a des choses qu’on a pas vu) : on utilise l’opérateur |> qui permet d’enchaîner des fonctions. En résumé, il passe le résultat de la fonction à sa gauche en paramètre de celle à sa droite. On utilise aussi l’opérateur * directement comme une fonction (attention à ne pas le coller aux parenthèses sinon OCaml pense qu’on écrit un commentaire). Et enfin, pour avoir un code encore plus court et clair, on passe par la fonction abs prédéfinie.

let calcul_etrange l = l
  |> List.map abs
  |> List.filter (fun x -> (x mod 2 = 0))
  |> List.fold_left ( * ) 1