DS 3 (MP2I 2021-2022) — Programmation récursive en OCaml

Devoir surveillé · MP2I · 2021-2022 · OCaml · partie pratique sur machine du DS 3

Cours : Récursivité

Autres parties : Partie écrite : exponentiation rapide et tri du crêpier · Pratique, impératif

Partie pratique sur machine (exercices Learn OCaml « DS3 - Récursif » et « DS3 - Impératif »).

Attention dans toute cette partie, vous n'avez pas le droit d'utiliser de références ni d'utiliser les modules List ou Array.

Les fonctions avec en indication vous garantissent, si vous les faites toutes, une note de 15.

Question 1

Écrire une fonction fact calculant la factorielle de l'entier naturel passé en argument.

Corrigé

Pas de difficulté pour fact mis-à-part le fait de se rappeler de la définition...

let rec fact n =
  if n = 0 then 1 else n * fact (n-1)

Question 2

Écrire une fonction somme_liste qui renvoie la somme des éléments de la liste d'entiers passée en paramètre.

Corrigé

Toutes les questions qui portent sur un parcours d'une liste vont être récursives et de la forme :

let rec parcours l = match l with
  | [ ] -> (* Cas de la liste vide *)
  | t::q -> (* On traite le cas où la liste commence par t
    et on va appeler parcours q *)

let rec somme_liste l =
  match l with
  | [] -> 0
  | t::q -> t + somme_liste q

Question 3

Écrire une fonction renverse qui renvoie la liste passée en argument dans l'ordre inverse. Attention vous ne pourrez pas la programmer directement en récursif, il faut passer par une fonction auxiliaire qui prend un accumulateur.

Attention vous aurez la moitié des points si votre fonction est en \(O(n^2)\).

Corrigé

Ici, on tire parti du fait que le parcours d'une liste va naturellement voir les éléments de gauche à droite : le premier élément vu est la tête de la liste, ce sera le dernier élément de la liste renversée, donc si on la construit progressivement, c'est le premier élément qui sera mis devant la liste vide. Pour cela, on utilise donc une fonction auxiliaire qui va avoir un accumulateur et qui va rajouter chaque tête à l'accumulateur.

Si on le faisait avec des références ça correspondrait à ça :

let renverse l =
  let acc = ref [] in
  let lr = ref l in
  while !lr <> [] do
    let t::q = !lr in (* warning car possible [] meme si exclu *)
    acc := t :: !acc;
    lr := q
  done;
  !acc

Le code récursif est équivalent mais bien plus clair et élégant.

let renverse l =
  let rec aux l acc = match l with
    | [] -> acc
    | t::q -> aux q (t::acc)
  in aux l []

Question 4

Ici et dans les deux questions qui suivent, on va considérer des listes du type ('a * 'b) list qui permettent de stocker des associations entre des éléments du type 'a et des éléments du type 'b. C'est une manière de réaliser un dictionnaire. Ainsi, la liste [ ("a", 42); ("toto", 12) ] va associer la valeur 42 à la clé "a" et la valeur 12 à la clé "toto". On appelle cette structure de donnée une liste d'associations.

Écrire une fonction ajoute_assoc : ('a * 'b) list -> 'a -> 'b -> ('a * 'b) list qui prend une liste d'associations en entrée et a et b et rajoute une association entre a et b.

Attention cette fonction est très simple.

Corrigé

Question très simple mais qui demande de bien comprendre l'énoncé !

let ajoute_assoc l a b =
  (a,b) :: l

Question 5

Écrire une fonction cherche_assoc : ('a * 'b) list -> 'a -> 'b qui prend une liste d'associations et une valeur a en entrée et renvoie la valeur b qui lui est associée ou produit une erreur avec l'instruction failwith "invalide".

Corrigé

On effectue une simple recherche dans la liste mais en tirant parti du fait que les éléments sont des couples. À noter ici le fait de faire un seul filtrage en filtrant aussi la forme de la tête.

let rec cherche_assoc l a =
  match l with
  | [] -> failwith "invalide"
  | (a',b)::q -> if a = a' then b else cherche_assoc q a

Question 6

Écrire une fonction cherche_assoc_opt : ('a * 'b) list -> 'a -> 'b option qui se comporte comme la fonction précédente hormis qu'elle utilise le type option pour renvoyer None en cas d'échec plutôt que de produire une erreur.

Corrigé

Comme précédemment mais avec des options.

let rec cherche_assoc_opt l a =
  match l with
  | [] -> None
  | (a',b)::q -> if a = a' then Some b else cherche_assoc_opt q a

Question 7

Écrire une fonction zip : 'a list -> 'b list -> ('a * 'b) list qui prend deux listes de même longueur et renvoie la liste des couples d'un élément de la première liste associé avec l'élément correspondant de la seconde.

Ainsi zip [1;2;3] ['a';'b';'c'] doit renvoyer [ (1,'a'); (2,'b'); (3,'c') ].

Corrigé

Encore une question assez simple mais qui déroute par l'énoncé. Prenez l'habitude de vous appuyer sur les exemples.

let rec zip l1 l2 =
  match l1, l2 with
  | t1::q1, t2::q2 -> (t1, t2)::zip q1 q2
  | _ -> []

Question 8

Écrire une fonction range : int -> int -> int list telle que l'appel à range a b renvoie la liste d'entiers [ a;a+1;...;b ].

Corrigé

Ici, on calcule \(\range{a}{b}\) en remarquant que \(\range{a}{b} = \emptyset\) = [ ] quand \(a > b\) et sinon, \(\range{a}{b} = a\) :: \(\range{a+1}{b}\).

let rec range a b =
  if a > b
  then []
  else a :: range (a+1) b

Question 9

(Difficile) Écrire une fonction gen_tuples : 'a list -> int -> 'a list list qui prend en entrée une liste [a1;...;an] et un entier p et renvoie tous les p-uplets de la liste sous forme de liste et dans l'ordre lexicographique correspondant à l'ordre de la liste. Ainsi pour ['a';'c';'b'] et 2 on va renvoyer

[ ['a';'a']; ['a';'c']; ['a';'b']; ['c';'a']; ['c';'c'];
  ['c';'b']; ['b';'a']; ['b';'c']; ['b';'b'] ]

Corrigé

let rec gen_tuples l n =
  if n = 0
  then [ [] ]
  else
    let tt = gen_tuples l (n-1) in
    let rec ajoute t l = match l with
      | [] -> []
      | ll::q -> (t::ll) :: ajoute t q
    in
    let rec aux l' =
      match l' with
      | [] -> []
      | t::q -> (ajoute t tt) @ aux q
    in aux l

Question 10

(Difficile) Écrire une fonction gen_plists : 'a list -> int -> 'a list list qui prend en entrée une liste [a1;...;an] et un entier p et renvoie toutes les p-listes de la liste sous forme de liste et dans l'ordre lexicographique correspondant à l'ordre de la liste.

La différence entre une p-liste et un p-uplet est qu'on ne peut avoir qu'une seule fois chacun des ai dans une p-liste. Attention, on distingue ici les positions dans la liste d'une même valeur. Pour [1;2;1] on a une 2-liste [1;1] mais [2;2] n'en est pas une.

Ainsi pour ['a';'c';'b'] et 2 on va renvoyer

[ ['a';'c']; ['a';'b']; ['c';'a']; ['c';'b']; ['b';'a']; ['b';'c'] ]

Corrigé

let rec gen_plists l n =
  if n = 0
  then [ [] ]
  else
    let rec retire t l =
      match l with
      | [] -> []
      | x::q -> if x = t then q else x :: retire t q
    in
    let rec ajoute t l = match l with
      | [] -> []
      | ll::q -> (t::ll) :: ajoute t q
    in
    let rec aux l' =
      match l' with
      | [] -> []
      | t::q -> (ajoute t (gen_plists (retire t l) (n-1))) @ aux q
    in aux l