Fonction polymorphe

Fonction polymorphe

[Hubert Canon]

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>

#permutations ["3";"456";""];;
- : string list list =
[["3"; "456"; ""]; ["3"; ""; "456"]; ["456"; "3"; ""]; ["456"; ""; "3"];
 [""; "3"; "456"]; [""; "456"; "3"]]

#permutations;;
- : string list -> string list list = <fun>

#permutations [1;2];;
Entrée interactive:
>permutations [1;2];;<EOF>
>             ^^^^^^^^^^
Cette expression est de type int list,
mais est utilisée avec le type string list.


-- 
-------------------------- Hubert Canon --------------------------
        Email : canon@poly.polytechnique.fr
        WWW   : http://www.polytechnique.fr/poly/~canon/
------------------------------------------------------------------

Re: Fonction polymorphe

[Pierre Weis]

> 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

Re: Fonction polymorphe

[Eric Hassold]

> Un bug probable de caml-light

Sauf erreur de ma part, ce n'est pas un bug, mais une fonctionnalite
introduite dans CL 0.7, qui permet l'affectation dynamique d'un type lors
de la 1ere evaluation ( pour les types representes par '_a  au lieu de 'a).

Pour conserver le typage polymorphe, il suffit d'ecrire explicitement
les parametres de la fonction, c-a-d :

let permutations l =
  let rec permut fixe = fun
    [] [] -> [fixe] |
    debut [] -> [] |
    debut (x :: suite) -> (permut (fixe @ [x]) []
                                  (debut @ suite)) @
                          (permut fixe (debut @ [x]) suite)
  in
  permut [] [] l;;

- : permutations : '_a list -> '_a list list = <fun>

et tout marche.