From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <keiko@kurims.kyoto-u.ac.jp>
X-Original-To: caml-list@yquem.inria.fr
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 7794EBB9C;
	Wed, 16 Nov 2005 08:40:50 +0100 (CET)
Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1])
	by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id jAG7emSf032722;
	Wed, 16 Nov 2005 08:40:49 +0100
Received: from localhost (orion [130.54.16.5])
	by kurims.kurims.kyoto-u.ac.jp (8.13.1/8.13.1) with ESMTP id jAG7emnk003213;
	Wed, 16 Nov 2005 16:40:48 +0900 (JST)
Date: Wed, 16 Nov 2005 16:40:48 +0900 (JST)
Message-Id: <20051116.164048.68541720.keiko@kurims.kyoto-u.ac.jp>
To: Alain.Frisch@inria.fr
Cc: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Recursive types
From: Keiko Nakata <keiko@kurims.kyoto-u.ac.jp>
In-Reply-To: <437AD616.7060006@inria.fr>
References: <20051116.084030.02302710.garrigue@math.nagoya-u.ac.jp>
	<20051116.112005.68539737.keiko@kurims.kyoto-u.ac.jp>
	<437AD616.7060006@inria.fr>
X-Mailer: Mew version 4.2 on Emacs 20.7 / Mule 4.1 (AOI)
Mime-Version: 1.0
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Miltered: at nez-perce with ID 437AE280.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; caml-list:01 recursive:01 frisch:01 frisch:01 recursive:01 coinductive:01 nodes:01 memoization:01 eta-expand:01 coinductive:01 algorithm:01 underlying:01 tuple:02 tuple:02 implemented:02 
X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled 
	version=3.0.3

From: Alain Frisch <Alain.Frisch@inria.fr>
> 
> The restriction ensures that structural recursive types are necessarily
> regular. So standard coinductive algorithms (implemented by keeping
> track of visited nodes or by memoization) are ok.

Thanks for the reply.

I think that it is not easy to know when to apply eta-expansion, 
namely, to replace a type name with its underlying definition.

For instance, to check equivalence betweeen the types t and s below:
 type t = < m : t * t >
 type 'a tuple = 'a * 'a
 type s = < m : s tuple >

the algorithm should memorize that t * t and s tuple are equivalent,
and then expands s tupl into s * s  
so as to check between t * t and s * s? 

When type abbreviations are more verobse as in 

 type 'a id = 'a 
 type 'a tuple = 'a id * 'a id 
 type u = < m : < m : u tuple> * < m : u tuple> > 

it seems difficult to know when to memorize in what representations
and when to eta-expand by the definitions.

I know easy standard coinductive algorithms found in textbooks,
but how to handle abbreviations is still unclear for me.

With best regards,
Keiko.