Substitutions
Évaluer les expressions :
(fun f -> fun x -> fun y -> f x (x + y)) (fun x -> fun y -> x * y) 2 3
(fun f -> fun g -> fun x -> g (f x)) (fun x -> x + 2) (fun y -> y * 3) 5
repeat 5 (fun n -> n+1) 7
length [3;2;4;5;1;6]
reverse [] [2;3;6;5;4]
permute [3;2;5;4;7;1]
en utilisant les définitions suivantes :
let rec repeat n f start =
if n = 0 then start
else repeat (n-1) f (f start)
let rec length = function
| [] -> 0
| head::tail -> 1 + length tail
let rec reverse xiferp suffix = match suffix with
| [] -> xiferp
| s::uffix -> reverse (s::xipref) uffix
let rec permute = function
| [] -> []
| [single] -> [single]
| 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 l'opérateur = a le type int -> int -> bool.
Considérons la définition de la fonction repeat.
Établir les liste de tous les sous-termes de cette expression.
Attribuer une variable de type à chacun de ces sous-termes.
Lister toutes les contraintes de types induites par les règles de typage, sous forme d'égalité de types.
Simplifier ces égalités pour déterminer le type de repeat.
Recommencer avec la fonction reverse. Vous devrez préalablement attribuer un type aux expressions :: et [].
