From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id DC2BABCAE for ; Fri, 1 Jul 2005 00:28:09 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j5UMS9qe008668 for ; Fri, 1 Jul 2005 00:28:09 +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 AAA28832 for ; Fri, 1 Jul 2005 00:28:09 +0200 (MET DST) Received: from postfix4-1.free.fr (postfix4-1.free.fr [213.228.0.62]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j5UMS82v017779 for ; Fri, 1 Jul 2005 00:28:09 +0200 Received: from [192.168.0.1] (rke75-3-82-229-183-156.fbx.proxad.net [82.229.183.156]) by postfix4-1.free.fr (Postfix) with ESMTP id B96352BA597 for ; Fri, 1 Jul 2005 00:28:08 +0200 (CEST) Message-ID: <42C47109.7060102@inria.fr> Date: Fri, 01 Jul 2005 00:24:09 +0200 From: Alain Frisch User-Agent: Debian Thunderbird 1.0.2 (X11/20050331) X-Accept-Language: en-us, en MIME-Version: 1.0 Cc: "O'Caml Mailing List" Subject: Re: [Caml-list] Type abstraction and (polymorphic) equality References: <20050629.023111.15476874.debian00@tiscali.be> <42C2E3AA.8090502@yahoo.fr> <42C3C098.6040303@ps.uni-sb.de> <1120161246.19517.37.camel@localhost.localdomain> In-Reply-To: <1120161246.19517.37.camel@localhost.localdomain> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 42C471F9.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 42C471F8.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; frisch:01 frisch:01 caml-list:01 abstraction:01 recursive:01 trivial:01 nodes:01 pairs:01 nodes:01 wrote:01 equality:01 polymorphic:01 graph:01 algorithm:01 alain:03 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: John Skaller wrote: > 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. If you want the equivalence to be invariant by unfolding, you need to keep a set of pairs of nodes, not just a set of nodes. -- Alain