TD n°3 : Listes

Exercice 1 - Types de listes

On utilise des définitions de fonctions pour faire apparaître tous les types :

In [1]:
let f1 x = [x]
Out[1]:
val f1 : 'a -> 'a list = <fun>
In [2]:
let f2 x = x :: []
Out[2]:
val f2 : 'a -> 'a list = <fun>
In [3]:
let f3 x = [] :: x
Out[3]:
val f3 : 'a list list -> 'a list list = <fun>
In [4]:
let f4 x = 0 :: 1 :: x
Out[4]:
val f4 : int list -> int list = <fun>
In [5]:
let f5 x = 0 :: 1 :: [x]
Out[5]:
val f5 : int -> int list = <fun>
In [6]:
let f6 x y z = x :: y :: [z]
Out[6]:
val f6 : 'a -> 'a -> 'a -> 'a list = <fun>
In [7]:
let f7 x = x :: [x]
Out[7]:
val f7 : 'a -> 'a list = <fun>
In [8]:
let f8 x = x :: x
Out[8]:
File "[8]", line 1, characters 16-17:
Error: This expression has type 'a but an expression was expected of type
         'a list
       The type variable 'a occurs inside 'a list
Characters 16-17:
  let f8 x = x :: x
                  ^
In [9]:
let f9 x y z = [x, y, z]
Out[9]:
val f9 : 'a -> 'b -> 'c -> ('a * 'b * 'c) list = <fun>
In [10]:
let f10 x y z = [x; [y; [z]]]
Out[10]:
val f10 : 'a list list -> 'a list -> 'a -> 'a list list list = <fun>

Exercice 2 - Liste d'éléments de types différents

On peut utiliser un type somme (union) :

In [11]:
type mixte =
  | Int of int
  | Float of float
Out[11]:
type mixte = Int of int | Float of float
In [12]:
[Float 3.0; Int 2; Float 1.0]
Out[12]:
- : mixte list = [Float 3.; Int 2; Float 1.]

Exercice 3 - Produit des éléments d'une liste

In [13]:
let rec produit liste =
  match liste with
  | [] -> 1
  | tete :: queue -> tete * (produit queue)
Out[13]:
val produit : int list -> int = <fun>
In [14]:
(* On peut généraliser à un groupe quelconque *)
let produit_general multiplication neutre liste =
  let rec produit liste =
    match liste with
    | [] -> neutre
    | tete :: queue -> multiplication tete (produit queue)
  in
  produit liste
Out[14]:
val produit_general : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>
In [15]:
(* C'est en fait la fonction List.fold_left (à l'ordre des arguments près) *)
List.fold_right
Out[15]:
- : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>
In [16]:
(* On peut l'écrire "dans l'autre sens", à la List.fold_right *)
let produit_general multiplication neutre liste =
  let rec produit liste accu =
    match liste with
    | [] -> accu
    | tete :: queue -> produit queue (multiplication accu tete)
  in
  produit liste neutre
Out[16]:
val produit_general : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
In [17]:
List.fold_left
Out[17]:
- : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

Exercice 4

In [18]:
(* Renvoie la liste des éléments de `liste` qui satisfont au prédicat `f` *)
let rec myst f liste =
  match liste with
  | [] -> []
  | tete :: queue when f tete -> tete :: (myst f queue)
  | _ :: queue -> myst f queue
Out[18]:
val myst : ('a -> bool) -> 'a list -> 'a list = <fun>
In [19]:
(* C'est : *)
List.filter
Out[19]:
- : ('a -> bool) -> 'a list -> 'a list = <fun>

Exercice 5

In [20]:
let rec insere x liste =
  match liste with
  | [] -> [x]
  | tete :: queue when x > tete -> tete :: insere x queue
  | _ -> x :: liste
;;
Out[20]:
val insere : 'a -> 'a list -> 'a list = <fun>
In [21]:
let rec tri_insertion liste =
  match liste with
  | [] -> []
  | tete :: queue -> insere tete (tri_insertion queue)
;;
Out[21]:
val tri_insertion : 'a list -> 'a list = <fun>

Dans la fonction insere, il y a au plus un appel récursif par élément de la liste. La complexité (dans le pire cas) de toutes les autres opérations, hors appels récursifs étant en $\Theta(1)$, on obtient une complexité (dans le pire cas) en $O(n)$, si $n$ désigne la longueur de la liste. De plus, dans le cas où l'élément à insérer est supérieur à tous les éléments de la liste, il y a exactement $n$ appels récursifs. C'est donc le pire cas et la complexité dans le pire cas de insere est linéaire, en $\Theta(n)$. Dans le meilleur cas, l'élément à inserer est inférieur au premier de la liste, il n'y a aucun appel récursif et la complexité est constante. La complexité $C(n)$ dans le pire cas du tri_insertion vérifie l'équation de récurrence $C(0) = \Theta(1)$ et $C(n) = C(n - 1) + C_{insere}(n) = C(n - 1) + \Theta(n)$ qui donne une complexité quadratique en $\Theta(n^2)$. On montre sans difficultés que le pire cas est atteint lorsque que la liste est triée par ordre décroissant. Dans le meilleur cas, atteint pour une liste déjà triée dans l'ordre croissant, la complexité de tous les appels à insere est constante et la complexité dans le meilleur cas de tri_insertion est linéaire en $\Theta(n)$.

Exercice 6

In [22]:
let plus_petit_entier_non_present_dans liste =
  let rec cherche_a_partir_de k =
    if List.mem k liste then
      cherche_a_partir_de (k + 1)
    else
      k
  in
  cherche_a_partir_de 0
Out[22]:
val plus_petit_entier_non_present_dans : int list -> int = <fun>

Exercice 7 - Tours de Hanoï

In [23]:
let deplacement n origine arrivee =
  "Deplacer le disque " ^ string_of_int n ^ " de " ^ origine ^ " a " ^ arrivee ^ "."
Out[23]:
val deplacement : int -> string -> string -> string = <fun>
In [24]:
let rec hanoi_liste n debut fin intermediaire liste_depl =
  if n = 0 then
    liste_depl
  else
    let liste1 = hanoi_liste (n - 1) debut intermediaire fin liste_depl in
    let liste2 =  (deplacement n debut fin) :: liste1 in
    hanoi_liste (n - 1) intermediaire fin debut liste2
Out[24]:
val hanoi_liste :
  int -> string -> string -> string -> string list -> string list = <fun>
In [25]:
let hanoi n =
  List.rev (hanoi_liste n "gauche" "droite" "milieu" [])
Out[25]:
val hanoi : int -> string list = <fun>
In [26]:
hanoi 5
Out[26]:
- : string list =
["Deplacer le disque 1 de gauche a droite.";
 "Deplacer le disque 2 de gauche a milieu.";
 "Deplacer le disque 1 de droite a milieu.";
 "Deplacer le disque 3 de gauche a droite.";
 "Deplacer le disque 1 de milieu a gauche.";
 "Deplacer le disque 2 de milieu a droite.";
 "Deplacer le disque 1 de gauche a droite.";
 "Deplacer le disque 4 de gauche a milieu.";
 "Deplacer le disque 1 de droite a milieu.";
 "Deplacer le disque 2 de droite a gauche.";
 "Deplacer le disque 1 de milieu a gauche.";
 "Deplacer le disque 3 de droite a milieu.";
 "Deplacer le disque 1 de gauche a droite.";
 "Deplacer le disque 2 de gauche a milieu.";
 "Deplacer le disque 1 de droite a milieu.";
 "Deplacer le disque 5 de gauche a droite.";
 "Deplacer le disque 1 de milieu a gauche.";
 "Deplacer le disque 2 de milieu a droite.";
 "Deplacer le disque 1 de gauche a droite.";
 "Deplacer le disque 3 de milieu a gauche.";
 "Deplacer le disque 1 de droite a milieu.";
 "Deplacer le disque 2 de droite a gauche.";
 "Deplacer le disque 1 de milieu a gauche.";
 "Deplacer le disque 4 de milieu a droite.";
 "Deplacer le disque 1 de gauche a droite.";
 "Deplacer le disque 2 de gauche a milieu.";
 "Deplacer le disque 1 de droite a milieu.";
 "Deplacer le disque 3 de gauche a droite.";
 "Deplacer le disque 1 de milieu a gauche.";
 "Deplacer le disque 2 de milieu a droite.";
 "Deplacer le disque 1 de gauche a droite."]