(* append "=" @ *)
let rec append l1 l2 = match l1 with
  | [] -> l2
  | x::xs -> x::(append xs l2)
;;

let rec reverse l = match l with
| [] -> []
| x::xs -> (reverse xs)@[x]
;;







plus efficace?!?;;

























let rec rev acc l = match l with
  | [] -> acc
  | x::xs -> (rev (x::acc) xs)
;;

let renverse l = rev [] l;;

renverse [1;2;3];;












let app1 (f,x) = f x;;


let applique f x = f x;;

let toto b = if b then "vrai" else "faux";;

applique toto;;

applique (applique toto);;

(applique applique) toto;;

let app2 x = (applique applique) x;;

let deuxfois f x = f (f x);;

let bizarre f x = x (f x);;   (*?????*)

let rebizarre f x = (f f) x;;









(* exception *)
let tete l = match l with
  | [] -> failwith "tete: je ne veux pas avoir a faire a la liste vide!"
  | t::q -> t
;;

let tete2 l = match l with
  | t::q -> t
;;

tete2 [];;

tete [];;

let queue l = match l with
  | [] -> failwith "erreur!"
  | t::q -> q
;;

let troisieme l = tete (queue (queue l))
;;

troisieme [2;4];;
















let rec dernier l = match l with
| [] -> failwith "dernier: liste vide"
| x::xs -> (match xs with
  | [] -> x
  | y::ys -> (dernier xs)
	   )
;;
let rec der l = match l with
  | [x] -> x
  | x::xs -> der xs
  | [] -> failwith "dernier: liste vide!"
;;

(* autre maniere d'ecrire *)
let rec der l = match l with
  | [x] -> x
  | _::xs -> der xs
  | [] -> failwith "dernier: liste vide!"
;;


let tete3 l = match l with
  | [] -> failwith "rate!"
  | x::_ -> x
;;

let est_non_vide l = match l with
  | [] -> false
  | _ -> true
(*  | _::_ -> true *)
;;

let toujours3 l = match l with
  | _ -> 3
  | [] -> 4
;;






(* NB: pas de   | l@l' -> ... : pourquoi?!? *)

(**********************************************************************)







let rec zip l1 l2 =
  match l1 with
    | x::xs ->
	begin
	  match l2 with
	    | y::ys ->
		(x,y)::(zip xs ys)
	    | [] -> failwith "le premier argument etait plus long"
	end
    | [] ->
	begin
	  match l2 with
	    | [] -> []
	    | _ -> failwith "le second argument etait plus long"
	end
;;


		













let rec eclair l1 l2 = match (l1,l2) with
  | [],[] -> []
  | x::xs,y::ys -> (x,y)::(eclair xs ys)
  | _ -> failwith "eclair: les listes n'ont pas la meme longueur"
;;


let ajoute x y = x+y;;

let rec accumule l = match l with
  | [] -> []
  | x::xs -> x::(List.map (ajoute x) (accumule xs))
;;

accumule [1;2;3];;

let rec acc2 l = match l with
  | [] -> []
  | x::xs -> x::(map (fun y -> y+x) (accumule xs))
;;
accumule [2;4;6];;





let rec accumule l = match l with
  | [] -> []
  | x::xs -> x::(map (function t -> x+t) (accumule xs))
;;


(**********************************************************************)

(* définir ses propres types *)

type bonhomme = string*int*string;;

let moi :bonhomme = ("daniel",35,"ens lyon");;



type coup = Poum | Tchak | Paf;;

let valse p = match p with
  | Poum -> "1er temps"
  | Tchak -> "2eme ou 3eme temps"
  | Paf -> "le batteur est nul"
;;












type float_inf = Nombre of float | Infini;;

Infini;;
3.5;;
Nombre 3.5;;

(* un constructeur n'est pas une fonction!! *)
Nombre;;

let nomb x = Nombre x;;

let inverse x = match x with
  | (Nombre f) -> if f<>0. then (Nombre (1./.f)) else Infini
  | Infini -> Nombre 0.
;;

type soit = BB of bool | EE of int;;

let f x = if x>3 then BB true else EE x;;

type jour = Lundi | Mardi | Mercredi | Jeudi | Vendredi | Samedi | Dimanche;;

let weekend d = match d with
  | Samedi -> true
  | Dimanche -> true
  | _ -> false
;;

let we d = match d with
| Samedi | Dimanche -> true
| _ -> false
;;



type nombre = Entier of int | Flottant of float;;

let val_entier x = match x with
  | Entier n -> n
  | Flottant f -> failwith "c'est un flottant"
;;





















let f = fun x -> x+1;;

fun x -> x+(f x);;





let rec somme x y = match (x,y) with
  | (Entier n,Flottant m) -> Flottant ((float n)+.m)
  | (Entier n,Entier m) -> Entier (n+m)
  | (Flottant n,Flottant m) -> Flottant (n+.m)
  | _ -> somme y x
;;






(* arbres binaires *)
type arbre = Feuille | Noeud of (int*arbre*arbre);;

let rec ajoute_noeud a k = match a with
  | Noeud (k',a1,a2) -> Noeud (k',ajoute_noeud a1 k, a2)
  | Feuille -> Noeud (k,Feuille,Feuille)
;;



let rec insere_ABR a k = match a with
  | Noeud (k',a1,a2) ->
      if k<k' then Noeud (k', insere_ABR a1 k, a2)
      else Noeud (k', a1, insere_ABR a2 k)
  | Feuille -> Noeud (k,Feuille,Feuille)
;;

let list2ABR l =
  List.fold_left insere_ABR Feuille l
;;

let t = list2ABR [4;1;3;6;2;5];;









(* aplatit: arbre -> int list *)
let rec aplatit a = match a with
  | Feuille -> []
  | Noeud (k,a1,a2) ->
                       (* k::((aplatit a1)@(aplatit a2)) *)
      (aplatit a1)@(k::(aplatit a2))
;;


let l' = aplatit t;;

















(* un type important, pour définir des fonctions partielles *)
type 'a option = None | Some of 'a;;

Some 3;;

Some "bonjour";;

Some (Some 3);;

let tete l = match l with
  | [] -> None
  | x::_ -> Some x;;







type bin_int = Zero | A of bin_int | B of bin_int;;

let rec bin_int_2_int b = match b with
  | Zero -> 0
  | A b' -> 2*(bin_int_2_int b')
  | B b' -> 1+2*(bin_int_2_int b')
;;

let rec bin_int_2_list b = match b with
  | Zero -> [0]
  | A b' -> (bin_int_2_list b')@[0]
  | B b' -> (bin_int_2_list b')@[1]
;;

let k = A (B (B (A (B Zero))));;

bin_int_2_list k, bin_int_2_int k;;









(**********************************************************************)
(* sauter dans les programmes: les exceptions *)


exception Impossible;;

Impossible;;

exception PasPossible;;

PasPossible;;

exception Rate;;

let toto x = if x>0 then 3 else raise Rate;;

let g n =
  if (toto n) = 2 then "bonjour" else "salut"
;;

let gere x =
  try
    g x
  with Impossible -> "trois"
;;




let f x = match x with
| [] -> 2;;

f [2];;

let inv x =
  if x <> 0. then 1. /. x
  else raise Impossible
;;

inv 2.;;
inv 0.;;

(* comportement `inne' de Caml *)
1./.0.;;
1/0;;

let divise x y =
  try
    let z = inv y in
      Nombre (x *. z)
  with
  | Impossible -> raise PasPossible
;;

let enveloppe f x = try f x with | Impossible -> raise PasPossible;;



let f x = if x then 3 else failwith "je m'en vais";;

f false;;


(* en fait, exception Failure of string *)
(* et *)
(* failwith s == synonyme de "raise (Failure s)" *)

(**********************************************************************)

(* programmation impérative: les références *)

let e = ref 2;;

!e;;


e := 3;;

!e;;

e := !e + 1;;

!e;;

let e' = ref 0.;;

e' := 0.01;;

(* le type unit *)
();;

print_string "bonjour monde\n";;


(* unit pour "retarder un calcul" *)

let v = ref 0;;

(* en fait on voudrait plutot ca: *)
let incremente, inspecte = (fun () -> v:= !v+1), fun () -> !v;;

incremente;;
incremente ();;

inspecte ();;


(* les tableaux: *)
let tab = Array.create 4 "hop";;

tab.(1) <- "hip";;

tab;;

let t = Array.create 10 0;;

for i = 1 to 9 do t.(i) <- i done;;

t;;

Array.iter print_int t;;

let m = Array.create 3 (Array.create 3 "boom");;

m.(0).(1) <- "wooq";;

m;;


let imp_fib n =
  let a = Array.make 2 0 in 
    a.(1) <- 1;
    for i = 2 to n do
      let aux = a.(0)+a.(1) in
	a.(0) <- a.(1);
	a.(1) <- aux
    done
    ;
    a.(1)
;;