(******************)
(* Listes en caml *)
(******************)
(* Les listes existent dejà en tant que type de base *)
let l = [ 1; 2; 3 ];;
let l2 = 1 :: 2 :: 7 :: [];;
let rec length = function
| [] -> 0
| t::q -> 1 + (length q)
;;
(* val length : 'a list -> int = <fun> *)
length l;;
(* - : int = 3 *)
length l2;;
let estVide = function
| [] -> true
| _ -> false
;;
(* val estVide : 'a list -> bool = <fun> *)
let rec estDans x = function
| [] -> false
| t::q -> if x=t
then
true
else
estDans x q
;;
(* val estDans : 'a -> 'a list -> bool = <fun> *)
let rec concat l1 l2 = match l1 with
| [] -> l2
| t::q -> t::(concat q l2)
;;
(* val concat : 'a list -> 'a list -> 'a list = <fun> *)
let rec renverse = function
| [] -> []
| t::q -> concat (renverse q) (t::[])
;;
(* val renverse : 'a list -> 'a list = <fun> *)
(* On peut aussi definir un type *)
(* Une liste est soit
* Vide
* Une tete (de type int) suivie d'une autre liste (eventuellement vide)
*)
type meslistes = Vide | Elt of int * meslistes;;
Elt(0, Elt(7, Vide));;
(*- : meslistes = Elt (0, Elt (7, Vide))*)
let rec longueur = function
| Vide -> 0
| Elt(_, queue) -> 1+ (longueur queue)
;;
(* val longueur : meslistes -> int = <fun> *)
(* De meme, on peut reecrire les fonctions precedentes *)
(******************)
(* Piles et Files *)
(******************)
(* Une pile est similaire a une liste dont les operations de base sont
* * empiler
* * depiler
* * sommet
*)
(* Une pile est soit Vide, soit E(element, pile) *)
type 'a pile = Vide | E of 'a * 'a pile;;
let empiler x p = E(x, p);;
let depiler = function
| E(x, p) -> p
;;
(* # depiler Vide;;
* Exception: Match_failure ("", 59, -73).*)
let sommet = function
| E(x, p) -> x
;;
(* Une file est une pile dans laquelle on n'ajoute pas en tete mais en queue
* Les operations de base sont
* * enfiler
* * defiler
* * premier
*)
(* Une file est soit Vide, soit F(element, file) *)
type 'a file = Vide | F of 'a * 'a file;;
let enfiler x p = match p with
| Vide -> F(x, [])
| F(t, q) -> F(t, enfiler x q)
;;
let defiler = function
| F(x, p) -> p
;;
let premier = function
| F(x, p) -> x
;;