Corrigé de l'interrogation écrite
de Programmation Fonctionnelle

I Récursivité

1.

    let rec change n l =
       if n=0 then []
              else match(l) with
                     [] -> failwith "Je ne peux pas faire de change"
                   | t::r -> if n>=t then t::(change (n-t) l)
                                     else change n r;;
2.

    let rec intervalle n m =
       if n=m then [n]
              else n::(intervalle (n+1) m);;

3.

    let adjoint x = List.map (function l -> x::l);;

ou

   let rec adjoint x l =
       match(l) with
          [] -> []
        | t::r -> (x::t)::(adjoint x r);;

4. 

      let rec ensemble_des_parties l =
        match(l) with
           []   -> [[]]
         | t::r -> let l' = ensemble_des_parties r in
                       (adjoint t l') @ l';;

5. 

      let rec insere a deb fin =
         match(fin) with
            []   -> [deb@[a]]
          | t::r -> (deb@[a]@fin) :: (insere a (deb@[t]) r);;

    let insertions a l = insere a [] l;;



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 structurés
 
1.

    let rec eclate a = match(a) with
       Vide -> (Vide,Vide)
     | Noeud(g,(x,y),d) -> let (g1,g2) = eclate g in
                           let (d1,d2) = eclate d in
                               (Noeud(g1,x,d1), Noeud(g2,y,d2));;

2.

    let rec renverse a = match(a) with
       Vide -> Vide
     | Noeud(g,(x,y),d) -> Noeud((renverse g),(y,x),(renverse d));;

3.

    let rec map_arbre f a = match(a) with
       Vide -> Vide
     | Noeud(g,x,d) -> Noeud((map_arbre f g),(f x),(map_arbre f d));;

4.

    let renverse a = map_arbre (function (x,y) -> (y,x)) a;;