(******************)
(* 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
;;