Typage de fonctions

Version imprimable

Typage de fonctions

Bonsoir

Je n'arrive pas à comprendre les solutions de l'exercice :

Donner le type des des expressions suivantes :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# fun f x y -> f x y
('a -> 'b -> 'c) -> 'a -> 'b -> 'c = <fun>
 
#fun f g x -> f (g x)
('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
 
#fun f x y -> f (x y f)
('a -> 'b) -> ('c -> ('a -> 'b) -> 'a) -> 'c -> 'b = <fun>
 
#fun f x y -> (f x) (y f)
('a -> 'b -> 'c) -> 'a -> (('a -> 'b -> 'c) -> 'b) -> 'c = <fun>
 
#fun f x y -> (f x) y
('a -> 'b -> 'c) -> 'a -> 'b -> 'c = <fun>
 
#fun f x y -> (f x) / (f y)
('a -> int) -> 'a -> 'a -> int = <fun>
 
#fun f x y -> f x,y
('a -> 'b) -> 'a -> 'c -> 'b * 'c = <fun>
 
#fun f x y -> f (x,y)
('a * 'b -> 'c) -> 'a -> 'b -> 'c = <fun>

Merci

14/10/2015, 17h48
SpiceGuid
Pour chaque type il y a une règle élémentaire de typage.

Pour la flèche :
(f : 'a->'b) & (x : 'a) <=> (f x : 'b)

Pour l'étoile :
(x : 'a) & (y : 'b) <=> (x,y : 'a * 'b)

En appliquant systématiquement ces règles dans un sens ou dans l'autre :
1. on arrive à typer n'importe quelle expression bien formée.
2. ou bien on arrive à trouver une expression bien formée qui possède le type recherché.
Ce qu'on te demande ici c'est (1).
En pratique ça n'est pas le plus difficile, d'ailleurs le top-level Caml sait très bien le faire à ta place.
D'après moi le sens (2) est plus intéressant car il correspond davantage à l'exercice pratique de la programmation. Car généralement on doit répondre à une spécification. Or une spécification signifie souvent que le type précède l'expression et non l'inverse.

Les enseignants omettent parfois certains précisions importantes :

1. L'application (le caractère espace) d'une valeur est associative à gauche.
C'est à dire que f x y = (f x) y.

2. La flèche est associative à droite.
C'est à dire que 'a -> 'b -> 'c = 'a -> ('b -> 'c).

3. L'application d'un type est associative à gauche.
C'est à dire que type 'a tree = N of 'a tree list
Est le même type que type 'a tree = N of ('a tree) list
Et n'a rien à voir avec le type (invalide) type 'a tree = N of 'a (tree list).
14/10/2015, 19h56
AdmChiMay

@SpiceGuid : court, clair. Donc génial.
Je crois que je viens d'économiser quelques arrachages de cheveux, tout comme (àmha) le posteur initial.