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 PAA13771; Thu, 25 Apr 2002 15:20:30 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f 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 PAA13648 for ; Thu, 25 Apr 2002 15:20:29 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g3PDKTr11009 for ; Thu, 25 Apr 2002 15:20:29 +0200 (MET DST) Received: from foobar.pps.jussieu.fr (IDENT:root@helium.pps.jussieu.fr [134.157.168.2]) by shiva.jussieu.fr (8.12.3/jtpda-5.4) with ESMTP id g3PDKST4080579 ; Thu, 25 Apr 2002 15:20:28 +0200 (CEST) Received: from strontium.pps.jussieu.fr (mail@strontium.pps.jussieu.fr [134.157.168.38]) by foobar.pps.jussieu.fr (8.11.0/jtpda-5.3.2) with ESMTP id g3PDThn12684 ; Thu, 25 Apr 2002 15:29:43 +0200 Received: from vouillon by strontium.pps.jussieu.fr with local (Exim 3.35 #1 (Debian)) id 170jAh-0001Gd-00; Thu, 25 Apr 2002 15:20:27 +0200 Date: Thu, 25 Apr 2002 15:20:27 +0200 To: John Max Skaller Cc: caml-list@inria.fr Subject: Re: [Caml-list] How to compare recursive types? Message-ID: <20020425132027.GA4702@strontium.pps.jussieu.fr> References: <3CBD4523.6080707@ozemail.com.au> <87y9fmr4fo.dlv@wanadoo.fr> <3CC656E1.5020108@ozemail.com.au> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <3CC656E1.5020108@ozemail.com.au> User-Agent: Mutt/1.3.28i From: Jerome Vouillon Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Wed, Apr 24, 2002 at 04:55:29PM +1000, John Max Skaller wrote: > How to compare recursive types? You should definitively read "Recursive Subtyping Revealed" by Vladimir Gapeyev, Michael Levin, and Benjamin Pierce. (Available from http://www.cis.upenn.edu/~bcpierce/papers/index.html) If you are only interested in equality, you can use the same algorithm as for subtyping (equality is a preorder). The complexity of this algorithm can be improved from quadratic to (almost) linear by exploiting the fact that type equality is an equivalence relation: the algorithm uses a set of pairs of already encountered types, but you can use a union-find datastructure instead. -- Jerome ------------------- 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