Corrigé de l'interrogation écrite
de Programmation Fonctionnelle

I Récursivité

1.

let toujours = List.fold_left (&) true;;

2.

let parfois = List.fold_left (or) false;;



II Algorithme de typage


    H                E                                       T

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


    d'après (°) et (°°), on a:  t5 = t6 = int

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

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



III Types algébriques
   
1.


type expr_bool =
     Val of bool
   | Ou of expr_bool * expr_bool
   | Non of expr_bool
   | Var of char
;;


2.


let exemple = Ou (Ou ((Non (Var 'A')), (Var 'B')), (Ou ((Val false), (Var 'A'))));;


3.


let rec val_of x env = match(env) with
     []        -> failwith "erreur"
   | (id,v)::r -> if id = x then v else val_of x r;;

let rec eval e env = match(e) with
   Val b      -> b
 | Ou (e1,e2) -> (eval e1 env) or (eval e2 env)
 | Non e      -> not (eval e env)
 | Var x      -> val_of x env
;;


4.


let adjoint a = List.map (function b -> a::b);;

let rec cree_envs vars = match(vars) with
   []   -> [[]]
 | t::r -> let l = cree_envs r in
               (adjoint (t,true) l) @ (adjoint (t,false) l)
;;


5.


let est_valide e vars =
  let envs = cree_envs vars in
      toujours (List.map (eval e) envs);;