Corrigé de l'interrogation écrite
de Programmation Fonctionnelle

I Récursivité

1.

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

let rec horner l x =
    match(l) with
      []   -> 0.
    | a::r -> (horner r x)*.x +. a;;


II Algorithme de typage

    H                  E                                          T

    x : t1       t = t1 -> t2              function x -> function y -> (x y y) + y : t
    y : t3       t2 = t3 -> t4             function y -> (x y y) + y : t2
                 t4 = int                  (x y y) + y : t4
                t3 = int                  x y y : int
                t3 = t5                   y : int
                t1 = t6 -> t5 -> int      x y : t5 -> int
                t3 = t6                   y  : t5
                                          x : t6 -> t5 -> int
                                          y : t6

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

    d'où:   f : (int -> int -> int) -> int -> int



III Types algébriques
   
1.

type figure =
     Carre of (float*float)*float
   | Disque of (float*float)*float;;

2.

(* distance : float*float -> float*float -> float *)

let inclus fig1 fig2 = match(fig1,fig2) with
     (Disque (c1,r1), Disque  (c2,r2)) -> (((distance c1 c2)+.r1) < r2) or (((distance c1 c2)+.r2) < r1)
    | _ -> false;;

3.

(* inclus : figure -> figure -> bool *)

let rec utile fig1 d = match(d) with
  [] -> true
| fig2::r -> (not (inclus fig1 fig2)) & (utile fig1 r);;

let rec simplifie d1 = match(d1) with
  [] -> []
| fig1::r -> let d2 = simplifie r in
                 if utile fig1 d2 then fig1::d2
                                  else d2;;