(* * ###################################################################### * # Les Listes # * ###################################################################### *) (* * =====================[ 1. Longueur d'une liste ]====================== *) let rec length = function | [] -> 0 | _::t -> 1 + length t;; length [1;2;3];; (* Version recursive terminale *) let length_term l = let rec aux acc = function | [] -> acc | _::t -> aux (acc+1) t in aux 0 l;; length_term [1;2;3;4];; (* * ===================[ 2. Appartenance a une liste ]==================== *) let rec mem a = function | [] -> false | h::t -> h=a || mem a t;; mem 0 [1;2;3;4];; mem 1 [1;2;3;4];; (* * ============================[ 3. Miroir ]============================= *) let rev l = let rec aux acc = function | [] -> acc | h::t -> aux (h::acc) t in aux [] l;; rev [1;2;3;4];; (* * =========================[ 4. Concatenation ]========================= *) let rec concat l l' = match l with | [] -> l' | t :: q -> t :: concat q l';; concat [1;2;3;4] [5;6;7;8];; (* Version recursive terminale *) let concat_term a b = let rec aux acc = function | [] -> acc | h::t -> aux (h::acc) t in aux b (rev a);; concat_term [1;2;3;4] [5;6;7;8];; (* * ============================[ 5. Iterer ]============================= *) let rec iter p = function | [] -> [] | h::t -> (p h)::(iter p t);; iter (fun x->x+1) [0;1;2;3;4;5];; (* Version recursive terminale *) let iter_term p l = let rec aux acc = function | [] -> acc | h::t -> aux ((p h)::acc) t in aux [] (rev l);; iter_term (fun x->x+1) [0;1;2;3;4;5];; (* * ============================[ 6. Filter ]============================= *) let rec filter p = function | [] -> [] | h::t when p h -> h :: (filter p t) | _::t -> filter p t;; filter (fun x->(x mod 2)=0) [0;1;2;3;4;5;6;7];; (* Version recursive terminale *) let filter_term p l = let rec aux acc = function | [] -> acc | h::t when p h -> aux (h::acc) t | _::t -> aux acc t in aux [] (rev l);; filter_term (fun x->(x mod 2)=0) [0;1;2;3;4;5;6;7];; (* * ###################################################################### * # Les Tris # * ###################################################################### *) let swap v i j = let t = v.(i) in v.(i)<-v.(j); v.(j)<-t;; (* * ==================[ 7. Tri Bulle - sur les vecteur ]================== *) let bubble_sort v = let n = vect_length v in for i=0 to n-1 do for i=0 to n-2 do if v.(i)>v.(i+1) then swap v i (i+1); done; done;; let vect = [|1;4;3;2;6;0;5;9;7;8|] in bubble_sort vect; vect;; (* * ================[ 8. Tri insertion - sur les listes ]================= *) let insert_sort l = let rec insert i = function | [] -> [i] | h::t when h < i -> h::(insert i t) | h::t -> i :: h :: t in let rec sort_in acc = function | [] -> acc | h::t -> sort_in (insert h acc) t in sort_in [] l;; insert_sort [1;4;3;2;6;0;5;9;7;8];; (* * ========[ 9.1. Tri Fusion - sur les listes, premiere methode ]======== * * Ici on fractionne la liste en une liste de listes au debut toutes * réduites a un singleton, puis on les fusionne deux a deux jusqu'a * n'avoir plus qu'une seul liste dans notre liste de liste. *) let fusion_sort l = let rec merge = fun | [] l -> l | l [] -> l | (h::t) (h'::t') when h < h' -> h::(merge t (h'::t')) | (h::t) (h'::t') -> h'::(merge (h::t) t') in let rec repeat_merge = function | h::h'::t -> repeat_merge ((merge h h')::repeat_merge t) | e -> e in hd(repeat_merge ([]::iter (fun x->[x]) l));; fusion_sort [1;4;3;2;6;0;5;9;7;8];; fusion_sort [];; (* * ========[ 9.2. Tri Fusion - sur les listes, seconde methode ]========= * * Ici on decoupe la liste en deux, on trie les deux parties et on * fusionne les eux sous listes triées en conservant le caractère trié *) let rec fusion_sort_2 l = let rec merge = fun | [] l -> l | l [] -> l | (h::t) (h'::t') when h < h' -> h::(merge t (h'::t')) | (h::t) (h'::t') -> h'::(merge (h::t) t') in let rec partition = function | [] -> [], [] | [a] -> [a], [] | h::h'::t -> let (l1,l2) = partition t in (h::l1), (h'::l2) in match l with | [] -> [] | [a] -> [a] | l -> let (l1,l2) = partition l in merge (fusion_sort_2 l1) (fusion_sort_2 l2);; fusion_sort_2 [1;4;3;2;6;0;5;9;7;8];; fusion_sort_2 [];; (* * =================[ 10. Tri Rapide - sur les vecteur ]================= *) let quick_sort v = let n = vect_length v in let rec aux i j = if i 'a -> bool};; let new_abr comparator = {abr = Feuille; comparator = comparator};; let mem x abr = let rec aux = function | Feuille -> false | Noeud(e, g, _) when abr.comparator e x -> aux g | Noeud(e, _, d) when abr.comparator x e -> aux d | Noeud(_, _, _) -> true in aux abr.abr;; let insert x abr = let rec aux = function | Feuille -> Noeud(x, Feuille, Feuille) | Noeud(e, g, d) when abr.comparator e x -> Noeud (e, aux g, d) | Noeud(e, g, d) -> Noeud(e, g, aux d) in abr.abr <- aux abr.abr;; let rec delete x abr = let rec extract_max = function | Feuille -> failwith "Cannot extract from empty tree" | Noeud(e, g, Feuille) -> e, g | Noeud(e, g, d) -> let e', d' = extract_max d in e', Noeud(e, g, d') in let rec extract x = function | Feuille -> Feuille | Noeud(e,g,d) when abr.comparator e x -> Noeud(e, extract x g, d); | Noeud(e,g,d) when abr.comparator x e -> Noeud(e, g, extract x d); | Noeud(e, Feuille, d) -> d | Noeud(e, g, d) -> let e',g' = extract_max g in Noeud(e', g', d) in abr.abr <- extract x abr.abr;; let abr_of_list comparator l = let result = new_abr comparator in let rec aux = function | [] -> result | h::t -> insert h result; aux t in aux l;; let list_of_abr abr = let rec aux acc = function | Feuille -> acc | Noeud(x, g, d) -> aux (x::(aux acc g)) d in aux [] abr.abr;; let abr = abr_of_list (prefix <) [7;42;53;13;93;173];; mem 13 abr;; mem 14 abr;; list_of_abr abr;; delete 13 abr;; delete 14 abr;; list_of_abr abr;;