Corrigé de l'interrogation écrite
de Programmation Fonctionnelle

I Récursivité

1.

let rec puiss x n = if n=0 then 1.
                           else let u = puiss x (n/2) in
                                if n mod 2 = 0 then u*.u
                                               else u*.u*.x;;
2.

let rec serie n a x = if n=0 then a(0)
                             else a(n)*.(puiss x n) +. serie (n-1) a x;;

3.

4.*.(serie 100000 (function i -> 1./.(2.*.float_of_int(i)+.1.)) (-1.));;


4.

serie 1 (function n -> 1.);;

Cette expression est bien typée :
- son type est float -> float
- sa valeur est la fonction qui à tout x associe x+1


II Algorithme de typage

    H                  E                                          T

    f : t1       t = t1 -> t2              function f -> function x -> f x : t
    x : t3       t2 = t3 -> t4             function x -> f x : t2
                 t1 = t5 -> t4             f x : t4
                t3 = t5                   f : t5 -> t4
                                          x : t5
                     

    d'où:   t = t1 -> t2 = (t5 -> t4) -> t3 -> t4 = (t5 -> t4) -> t5 -> t4

    d'où:   app : ('a -> 'b) -> 'a -> 'b



III Types structurés
   
1.

let rec take n l = if n=0 then []
                          else match(l) with
                                 [] -> []
                               | t::r -> t::(take (n-1) r);;

2.

let rec drop n l = if n=0 then l
                          else match(l) with
                                 [] -> []
                               | t::r -> drop (n-1) r;;

3.

let partage l =
    let long = (List.length l)/2 in
        (take long l, drop long l);;

4.

let rec fusion (l1,l2) = match(l1,l2) with
    ([],l) -> l
|   (l,[]) -> l
|   (t1::r1,t2::r2) -> if t1<t2 then t1::fusion (r1,l2)
                                else t2::fusion (l1,r2);;


5.

let rec tri l = if List.length l < 2 then l
                                     else
       let (l1,l2) = partage l in
           fusion (tri l1,tri l2);;


IV Vous pensiez avoir fini ?

1.

type 'a expr_ens =
    Vide
  | Singleton of 'a
  | Union of 'a expr_ens * 'a expr_ens
  | Intersection of 'a expr_ens * 'a expr_ens;;

2.

Union (Singleton 1, Singleton 2);;