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 E6F1CBC88 for ; Mon, 7 Feb 2005 04:17:13 +0100 (CET) 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 j173HD3O007051 for ; Mon, 7 Feb 2005 04:17:13 +0100 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 EAA17922 for ; Mon, 7 Feb 2005 04:17:13 +0100 (MET) Received: from mail.kaba.or.jp (cascade.kaba.or.jp [202.249.19.34]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j173HBOl027685 for ; Mon, 7 Feb 2005 04:17:12 +0100 Received: from localhost (crossbill.kaba.or.jp [202.249.19.22]) by mail.kaba.or.jp (Postfix) with ESMTP id BDB5549AB7; Mon, 7 Feb 2005 12:17:07 +0900 (JST) Date: Mon, 07 Feb 2005 12:17:07 +0900 (JST) Message-Id: <20050207.121707.74656685.keiko@kaba.or.jp> To: caml-list@inria.fr Cc: keiko@kaba.or.jp Subject: polymorphic recursion with type constraint? From: nakata keiko X-Mailer: Mew version 3.3 on Emacs 21.3 / Mule 5.0 (SAKAKI) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 4206DDB9.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 4206DDB7.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; recursion:01 kaba:01 rec:01 subst:01 subst:01 well-typed:01 well-typed:01 recursion:01 inherently:01 recursive:01 ....:98 polymorphic:01 polymorphic:01 define:01 functions:01 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: Hello. Can I make the following function 'subst' well-behave, so that it can be used in the contexts where: 1) 'p' (the first argument) is assumed of type 'path', and 'env' (the first argument)is assumed of type '(string * tau) list; and 2)'p' is assumed of type 'tau', and 'env' is assumed of type '(string * tau) list; type tau = [`Root | `Apply of path * tau |`Var of string] and path = [`Root | `Apply of path * tau] let rec subst p env = match p with `Root -> `Root | `Apply (p1, p2) -> `Apply(subst p1 env , subst p2 env) | `Var s -> List.assoc s env Yet 'subst' is well-typed, let sub (p : path) (env : (string * tau)) = subst p env fails. At first I tried to make 'subst' explicitly typed, but I could not. 'subst' would have type 'a -> (string * tau) list -> 'a, where the type variable 'a is only instantiated to either 'tau' or 'path'. Then, the second clause of match | `Apply (p1, p2) -> `Apply(subst p1 env , subst p2 env) would be well-typed. It seems that I need polymorphic recursion with type constraint.... Or such encoding is inherently wrong, and should I define 2 mutually recursive functions? Best regards, Keiko.