Sujet

Correction en OCaml

Exercice 1.

let rec remove x = function
  | [] -> []
  | t::q -> if t = x then q else t :: remove x q
      

Exercice 2.

let rec sum_m l = function
  | [] -> l
  | t :: q -> sum_m (t::l) q

let rec union_m l = function
  | [] -> l
  | t :: q -> union_m (t::remove t l) q

let rec substract_m l = function
  | [] -> l
  | t :: q -> substract_m (remove t l) q

let intersect_m l1 l2 =
  substract_m (sum_m l1 l2) (union_m l1 l2)
      

Exercice 4.

let rec insert_s x = function
  | [] -> [x]
  | t :: q as l ->
     if x < t then x::l else t::insert_s x q
      

Exercice 5.

let rec sort = function
  | [] -> []
  | t :: q -> insert_s t (sort q)
      

Exercice 6.

(* C'est ce que fait l1 = l2 en réalité *)
let rec test_s l1 l2 =
  match l1,l2 with
  | [], _ -> l2 = []
  | _, [] -> l1 = []
  | t1::q1, t2::q2 -> t1=t2&&test_s q1 q2

let is_equal_m l1 l2 =
  test_s (sort l1) (sort l2)
      

Exercice 7.

let insert_partout x acc l =
  let rec aux acc' avant = function
    | [] -> (List.rev_append avant [x])::acc'
    | t :: q as l ->
       aux ((List.rev_append avant (x::l))::acc') (t::avant) q
  in aux acc [] l

let it_list = List.fold_left
let list_it = List.fold_right

let rec permutation = function
  | [] -> [[]]
  | t :: q ->
     it_list (fun acc l -> insert_partout t acc l) [] (permutation q)
      

Exercice 8.

let list_map f l =
  list_it (fun el acc -> f el::acc) l []