Programmation Fonctionnelle, TD2

Version & licenses
Creative Commons License

Programmation Fonctionnelle, TD2 : Évaluation par substitution.

Guyslain Naves

Substitutions

Évaluer les expressions :

  1. (fun f -> fun x -> fun y -> f x (x + y)) (fun x -> fun y -> x * y) 2 3

  2. (fun f -> fun g -> fun x -> g (f x)) (fun x -> x + 2) (fun y -> y * 3) 5

  3. repeat (fun n -> n+1) 5 7

  4. length [3;2;4;5;1;6]

  5. rev_accu [] [2;3;6;5;4]

  6. permute [3;2;5;4;7;1]

en utilisant les définitions suivantes :

  1. let rec repeat = fun f -> fun n -> fun start ->
  2. if n = 0 then start
  3. else repeat f (n-1) (f start)

  4. let rec length = function
  5. | [] -> 0
  6. | head::tail -> 1 + length tail

  7. let rec rev_accu = fun xiferp suffix -> match suffix with
  8. | [] -> xiferp
  9. | middle::uffix -> rev_accu (middle::xipref) uffix

  10. let rec permute = fun list -> match list with
  11. | [] -> []
  12. | [single] -> [single]
  13. | first::second::others -> second::first::(permute others)

Typages des fonctions

Dans cet exercice, nous utilisons le fait que, pour trois termes t1, t2 et t3, alors if t1 then t2 else t3 est aussi un terme. La règle de typage associée est : si t1 a le type bool, t2 et t3 ont le type A pour un type arbitraire A, alors if t1 then t2 else t3 a le type A. De plus = a le type A -> A -> bool.

Considérons la définition de la fonction repeat.

  1. Établir les liste de tous les sous-termes de cette expression.
  2. Attribuer une variable de type à chacun de ces sous-termes.
  3. Lister toutes les contraintes de types induites par les règles de typage, sous forme d'égalité de types.
  4. Simplifier ces égalités pour déterminer le type de repeat.

Recommencer avec la fonction rev_accu. Vous devrez préalablement attribuer un type aux expressions :: et [].