Les parties

Exercice · OCaml (option informatique), chapitre 11 — Récursivité et retour sur trace

Énoncé

Écrire parties et vérifier qu'une liste de $n$ éléments produit $2^{n}$ parties.

Corrigé

let rec parties l =
  match l with
  | [] -> [[]]
  | x :: reste ->
      let sous = parties reste in
      sous @ List.map (fun s -> x :: s) sous

À chaque élément, on double le nombre de parties (celles sans x, et les mêmes avec x en tête). Partant de [[]] ( $1$ partie pour la liste vide), on obtient $2^{n}$ : parties [1; 2; 3] en a $8$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.