Sujet

Correction en OCaml

Exercice 1.

let rec begaie = function
  | [] -> []
  | t :: q -> t :: t :: begaie q
      

Exercice 2.

let rec insert x = function
  | [] -> []
  | t :: _ as l when x < t -> x :: l
  | t :: q -> t :: insert x q
      

Exercice 3.

let rec flip = function
  | [] -> []
  | t :: q as l -> match flip q with
	      | [] -> l
	      | d :: r -> d :: t :: r

let rec rev_flip l =
  match flip l with
  | [] -> []
  | t :: q -> t :: rev_flip q

let test = rev_flip [1;2;3;4;5]
      

Exercice 4.

let rec decoupe l p =
  match l with
  | [] -> ([],[])
  | t :: q when t < p ->
     let (li,ls) = decoupe q p in (t::li,ls)
  | t :: q ->
     let (li,ls) = decoupe q p in (li,t::ls)

let rec decoupe_strict l p =
  match l with
  | [] -> ([],[],0)
  | t :: q ->
     let (li,ls,np) = decoupe_strict q p in
     if t < p then (t::li,ls,np)
     else if t = p then (li,ls,succ np)
     else (li,t::ls,np)

let rec ieme l i =
  match l with
  | [] -> failwith "i >= taille l"
  | t :: q ->
     let (li,ls,np) = decoupe_strict q t in
     let nli = List.length li in
     if i < nli then ieme li i
     else if i <= nli + np + 1 then t
     else ieme ls (i - nli - np - 1)

let test = ieme [4;8;2;4;6;2] 3
      

Exercice 5.

let split l =
  let rec aux acc1 acc2 = function
    | [] -> (acc1,acc2)
    | [ x ] -> (x::acc1, acc2)
    | t1 :: t2 :: q -> aux (t1::acc1) (t2::acc2) q
  in aux [] [] l