From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA17653; Thu, 18 Apr 2002 12:17:51 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id MAA17649 for ; Thu, 18 Apr 2002 12:17:50 +0200 (MET DST) Received: from sunny.pacific.net.au (sunny.pacific.net.au [203.25.148.40]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g3IAHmb20765 for ; Thu, 18 Apr 2002 12:17:48 +0200 (MET DST) Received: from wisma.pacific.net.au (wisma.pacific.net.au [210.23.129.72]) by sunny.pacific.net.au with ESMTP id g3IAHkXt016193 for ; Thu, 18 Apr 2002 20:17:47 +1000 (EST) Received: from ozemail.com.au (ppp48.dyn71.pacific.net.au [202.7.71.48]) by wisma.pacific.net.au with ESMTP id UAA10779 for ; Thu, 18 Apr 2002 20:17:45 +1000 (EST) Message-ID: <3CBE9D49.4020809@ozemail.com.au> Date: Thu, 18 Apr 2002 20:17:45 +1000 From: John Max Skaller User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.2.1) Gecko/20010901 X-Accept-Language: en-us MIME-Version: 1.0 To: caml-list@inria.fr Subject: [Caml-list] Representation of anonymous recursive types Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk What is a good way to represent an anonymous recursive type so that they can be easily compared for equality? Felix currently supports recursion, but only for generative types, that is, ones for which there is an entry into a symbol table. Binding the type then replaces the name with the symbol table index. This cannot work for an anonymous type, unless of course a secret entry is made in the symbol table, and that would fail to correctly support type comparisons. I'm thinking of something like: type texpr = [ .... | `Rec int | `As int * texpr] where the argument of `Rec indicates the containing `As term with the same index. I think this means that the standard Ocaml comparison <> will correctly test equality. Example: (Cons of int * 'a | Empty) as 'a is modelled by: `As (1, `Sum [`Nctor ("Cons", `Prod [`Int; `Rec 1]); `Cctor "Empty"]) For uniqueness, the index has to be 1 for inner most recursion, 2 for next outer one, etc. -- John Max Skaller, mailto:skaller@ozemail.com.au snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia. voice:61-2-9660-0850 ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners