From: Pierre Weis <weis@pauillac.inria.fr>
Message-Id: <199602011403.PAA28184@pauillac.inria.fr>
Subject: Re: Fonction polymorphe
To: canon@poly.polytechnique.fr (Hubert Canon)
Date: Thu, 1 Feb 1996 15:03:42 +0100 (MET)
In-Reply-To: <199601241847.TAA02621@poly.polytechnique.fr> from "Hubert Canon" at Jan 24, 96 07:47:22 pm
> Un bug probable de caml-light : j'ai une fonction qui devrait etre
> polymorphe, mais elle change de type au premier appel :
>
> Avec caml light 7beta2 (le code n'est pas de moi) :
>
> #let permutations =
> let rec permut fixe = fun
> [] [] -> [fixe] |
> debut [] -> [] |
> debut (x :: suite) -> (permut (fixe @ [x]) []
> (debut @ suite)) @
> (permut fixe (debut @ [x]) suite)
> in
> permut [] [];;
>
> - : permutations : '_a list -> '_a list list = <fun>
[English at the end of the message]
Ce n'est pas un bug du compilateur: la re'ponse est parfaitement
conforme a` la the'orie. Comme cela a de'ja` e'te' explique' dans
cette tribune (dont vous pouvez consulter l'historique sur
http://pauillac.inria.fr/), c'est un proble`me de typage du
polymorphisme: seule les fonctions, constantes et identificateurs
peuvent recevoir un type polymorphe; or votre phrase est la
de'finition d'une valeur qui n'est pas syntaxiquement une fonction,
mais une expression ``let .. in ...''; cette expression n'est donc pas
ge'ne'ralise'e (ne rec,oit pas un type polymorphe), ce qui est normal.
Pour re'parer, il suffit de rendre explicite pour le compilateur que
``permutations'' est une fonction en ajoutant un argument explicite:
#let permutations l =
let rec permut ...
in
permut [] [] l;;
permutations : 'a list -> 'a list list = <fun>
Constatez que l'expression interne est ge'ne'ralisable, donc polymorphe:
#let rec permut fixe = fun
[] [] -> [fixe] |
debut [] -> [] |
debut (x :: suite) -> (permut (fixe @ [x]) []
(debut @ suite)) @
(permut fixe (debut @ [x]) suite)
;;
permut : 'a list -> 'a list -> 'a list -> 'a list list = <fun>
Rappelez-vous aussi que '_a signifie: un type ``a'' inconnu, a`
de'terminer par la suite (a` la manie`r d'une variable dans une
e'quation mathe'matique). Ce qui explique que ``a'' rec,oive une
valeur par la suite. Ces inconnues sont utiles, par exemple pour des
cre'er des re'f'erences:
#let l = ref [];;
l : '_a list ref = ref []
La premie`re affectation de l fixera le type re'el de l:
#l := 1 :: !l;;
- : unit = ()
#l;;
- : int list ref = ref [1]
[English]
This is not a bug but a feature. As explained earlier in this
mailing-list (that you may read via the server
http://pauillac.inria.fr/caml), this is due to the treatment of
polymorphism: only functions, constants, and variables may receive a
polymorphic type scheme; since your phrase defines a value that is not
(syntactically) a function but a ``let ... in ...'' expression, this
expression is not polymorphic.
To get a polymorphic type for permutations, you need to add an
explicit argument:
#let permutations l =
let rec permut fixe = fun
...
in
permut [] [] l;;
permutations : 'a list -> 'a list list = <fun>
Remember that '_a means an unknown type named ``a'', to be fixed in
the sequel of the program (similarly to an unknown in mathematical
equations). Thta's why ``a'' is determined by the rest of your
program. These unknowns are useful for instance to define references:
#let l = ref [];;
l : '_a list ref = ref []
The first assigment to l fixes the intended type of l:
#l := 1 :: !l;;
- : unit = ()
#l;;
- : int list ref = ref [1]
Pierre Weis
INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis