From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 92F4EBCAE for ; Thu, 30 Jun 2005 21:54:11 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j5UJsBWY003331 for ; Thu, 30 Jun 2005 21:54:11 +0200 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 VAA25785 for ; Thu, 30 Jun 2005 21:54:10 +0200 (MET DST) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j5UJs8p8003328 for ; Thu, 30 Jun 2005 21:54:09 +0200 Received: from rosella (ppp5-13.lns1.syd3.internode.on.net [59.167.5.13]) by smtp3.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id j5UJs4NA017395; Fri, 1 Jul 2005 05:24:06 +0930 (CST) Subject: Re: [Caml-list] Type abstraction and (polymorphic) equality From: John Skaller To: Andreas Rossberg Cc: "O'Caml Mailing List" In-Reply-To: <42C3C098.6040303@ps.uni-sb.de> References: <20050629.023111.15476874.debian00@tiscali.be> <42C2E3AA.8090502@yahoo.fr> <42C3C098.6040303@ps.uni-sb.de> Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="=-Sa24V6IEIaRp1XLHwuYM" Date: Fri, 01 Jul 2005 05:54:06 +1000 Message-Id: <1120161246.19517.37.camel@localhost.localdomain> Mime-Version: 1.0 X-Mailer: Evolution 2.2.1.1 X-Miltered: at nez-perce with ID 42C44DE3.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 42C44DE0.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 abstraction:01 rossberg:01 recursives:01 dfas:01 recursive:01 trivial:01 nodes:01 recursion:01 60%:98 wrote:01 wrote:01 sourceforge:01 sourceforge:01 equality:01 X-Attachments: type="application/pgp-signature" name="signature.asc" X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: --=-Sa24V6IEIaRp1XLHwuYM Content-Type: text/plain Content-Transfer-Encoding: quoted-printable On Thu, 2005-06-30 at 11:51 +0200, Andreas Rossberg wrote: > sejourne_kevin wrote: > >=20 > > A generic equality should be one that work with recursives. >=20 > Not so easy. In order to be a proper equivalence test for cyclic data=20 > structures it essentially had to test graph equivalence, which is the=20 > same as testing equivalence of DFAs. So it would be a completely=20 > different algorithm, with significant complexity in space and time. I do not see that. The current algorithm is recursive descent is it not? That can also be used with a trivial modification to test graph equivalence, by simply keeping a list of visited nodes and not revisiting them.=20 The problem of course is that the cost per node is O(N) where N is the recursion depth. Profiling indicates my code spends up to 60% of all time doing comparisons. > In Alice ML, where we have recently added such a co-recursive=20 > equivalence operation, we opted for turning it into a separate=20 > operation, to avoid these issues. That seems reasonable, since the client will usually know if the data structure contains cycles or not. --=20 John Skaller Download Felix: http://felix.sf.net --=-Sa24V6IEIaRp1XLHwuYM Content-Type: application/pgp-signature; name=signature.asc Content-Description: This is a digitally signed message part -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.5 (GNU/Linux) iD8DBQBCxE3cw7vY25tjqN4RArs0AJ9Hc6sEEAm3i9v7f85PafIRXR42uwCfSBep d0GEuxHuPI51bjzRCVtvkhs= =RqOF -----END PGP SIGNATURE----- --=-Sa24V6IEIaRp1XLHwuYM--