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 100 (function n -> 1./.(2.*.float_of_int(n)+.1.)) (-1.));;


4. 

     L'expression Ocaml

      serie 100 (function n -> 1.)
 
     est bien typée. Elle a pour type float -> float et
     c'est la fonction qui à tout x associe la somme des x^i, pour i=0..100


II Algorithme de typage


    H                E                           T

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

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

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

    d'où:       twice : ('a -> 'a) -> 'a -> 'a     (en utilisant la règle de généralisation)



III Types algébriques
 
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 n = List.length l in
           ((take (n/2) l), (drop (n/2) l));;

4.

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

    let rec tri l =
       match(l) with
         []  -> []
       | [e] -> [e]
       | _   -> 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);;