On utilise des définitions de fonctions pour faire apparaître tous les types :
let f1 x = [x]
let f2 x = x :: []
let f3 x = [] :: x
let f4 x = 0 :: 1 :: x
let f5 x = 0 :: 1 :: [x]
let f6 x y z = x :: y :: [z]
let f7 x = x :: [x]
let f8 x = x :: x
let f9 x y z = [x, y, z]
let f10 x y z = [x; [y; [z]]]
On peut utiliser un type somme (union) :
type mixte =
| Int of int
| Float of float
[Float 3.0; Int 2; Float 1.0]
let rec produit liste =
match liste with
| [] -> 1
| tete :: queue -> tete * (produit queue)
(* 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
(* C'est en fait la fonction List.fold_left (à l'ordre des arguments près) *)
List.fold_right
(* 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
List.fold_left
(* 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
(* C'est : *)
List.filter
let rec insere x liste =
match liste with
| [] -> [x]
| tete :: queue when x > tete -> tete :: insere x queue
| _ -> x :: liste
;;
let rec tri_insertion liste =
match liste with
| [] -> []
| tete :: queue -> insere tete (tri_insertion queue)
;;
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)$.
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
let deplacement n origine arrivee =
"Deplacer le disque " ^ string_of_int n ^ " de " ^ origine ^ " a " ^ arrivee ^ "."
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
let hanoi n =
List.rev (hanoi_liste n "gauche" "droite" "milieu" [])
hanoi 5