From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: weis
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id RAA07401 for caml-redistribution; Mon, 24 Nov 1997 17:38:43 +0100 (MET)
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA09193 for <caml-list@pauillac.inria.fr>; Fri, 21 Nov 1997 19:26:39 +0100 (MET)
Received: from lri.lri.fr (root@lri.lri.fr [129.175.15.1])
	by nez-perce.inria.fr (8.8.7/8.8.5) with ESMTP id TAA21881
	for <caml-list@inria.fr>; Fri, 21 Nov 1997 19:26:38 +0100 (MET)
Received: from sun-demons.lri.fr (sun-demons.lri.fr [129.175.8.90])
          by lri.lri.fr (8.8.5/jtpda-5.2) with ESMTP id TAA18531
          for <caml-list@inria.fr>; Fri, 21 Nov 1997 19:26:36 +0100 (MET)
Received: from sun-demons by sun-demons.lri.fr
	(8.8.4/local) with SMTP id TAA29589
	for <caml-list@inria.fr>; Fri, 21 Nov 1997 19:26:35 +0100 (MET)
Message-ID: <3475D25B.5066@lri.fr>
Date: Fri, 21 Nov 1997 19:26:35 +0100
From: Emmanuel Engel <Emmanuel.Engel@lri.fr>
X-Mailer: Mozilla 3.01Gold (X11; I; SunOS 5.5 sun4u)
MIME-Version: 1.0
To: caml-list@inria.fr
Subject: Re: type recursifs et abreviations cyclique and Co 
References: <199711211438.PAA04383@spirou.inria.fr>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: weis

D'une facon generale, je ne  pense pas que le  fait  de ne pas  pouvoir
ecrire de type cyclique enleve quelque chose. Une abreviation cyclique
definit en  fait  une instance  recursive  d'un type qui  n'etait  pas
necessairement recursif depuis le debut. Ainsi la definition de type

type x = x option 

doit "moralement" etre equivalente au type 

'a option as 'a

Le fait que caml interdise de tels (definitions de) types me semble une
bonne chose, les erreurs de typage  en presence des  types de la forme
"'a t as 'a"  sont vraiement difficiles a  trouver. De plus, il me
semble
que cela n'enleve   rien.  Par exemple  la definition   precedente est
equivalente (en tout cas a premiere vue) a

type x = None | Some of x;;

Si vraiement je veu utiliser les options,  je peut toujours introduire
une constructeur bidon qui va masquer l'abreviation cyclique:

type x = X of x option;;

Le second mail porte exactement sur le meme probleme.  Le principe est
que tout  type recursifs ('a t as  'a) doit pouvoir etre redefini sous
une forme equivalente sans avoir  besoin de "as".   J'ai bien peur que
le second exemple soit plus  difficile.  Pour simplifier, j'ai mis  la
module a  plat, sans HALF.  De plus  include n'existe  pas (suivant la
doc)

Voici le point de depart.

module type Pre =
  sig
    type ('a, 'b) h_label = | Lexicalized of 'a | Built of 'b
    type ('a, 'b) h_unit = ('a, 'b) h_label option
    type ('a, 'b, 'c) node =
      	{ mutable parent: ('a, 'b, 'c) node option;
          mutable forest: ('a, 'b, 'c) node list;
          mutable state: 'b;
          mutable unit: ('a, 'c) h_unit
	} 
	  
	  
    type p_state
    and s_state
    and p_label
    and s_label
	  
    and p = (p_label, p_state, s) Half.node
    and s = (s_label, s_state, p) Half.node
  end;; 

J'ai deux  solutions.  Le premiere est en  fait  de definir deux types
"node" differents, un par instance consideree. Cela donne plus ou moins

module type Pre =
  sig
    type ('a, 'b) h_label = | Lexicalized of 'a | Built of 'b
    type ('a, 'b) h_unit = ('a, 'b) h_label option
    type node_p =
      	{ mutable parent: node_p option;
          mutable forest: node_p list;
          mutable state: p_state;
          mutable unit: (p_label, node_s) h_unit
	} 
	  
    and node_s =
	{ mutable parent: node_s option;
          mutable forest: node_s list;
          mutable state: s_state;
          mutable unit: (s_label, node_p) h_unit
	}
	  
    and p_state
    and s_state
    and p_label
    and s_label
	  
    type p = node_p
    and s = node_s
  end;; 


Je suis d'accord c'est lourd, de plus les fonctions 

val leq_cost : ('a, 'b, 'c) node -> ('a, 'b, 'c) node -> bool
val leq_p_cost : p -> p -> bool
val leq_s_cost : s -> s -> bool
val p_block : p -> unit
val s_block : s -> unit

doivent  etre  dupliquees.   L'autre  solution   est   le constructeur
bidon. Cela donne


module type Pre =
  sig
    type ('a, 'b) h_label = | Lexicalized of 'a | Built of 'b
    type ('a, 'b) h_unit = ('a, 'b) h_label option
    type ('a, 'b, 'c) node =
      	{ mutable parent: ('a, 'b, 'c) node option;
          mutable forest: ('a, 'b, 'c) node list;
          mutable state: 'b;
          mutable unit: ('a, 'c) h_unit
	} 
	  
	  
    and p_state
    and s_state
    and p_label
    and s_label
	  
    and p = P of (p_label, p_state, s) node
    and s = S of (s_label, s_state, p) node
  end;; 


Hope this help.


-- 

- Emmanuel Engel