From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: weis Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id IAA30946 for caml-redistribution; Tue, 22 Sep 1998 08:37:29 +0200 (MET DST) 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 EAA18694 for ; Tue, 22 Sep 1998 04:36:09 +0200 (MET DST) Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1]) by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id EAA09302 for ; Tue, 22 Sep 1998 04:36:05 +0200 (MET DST) Received: from localhost (safran.kurims.kyoto-u.ac.jp [130.54.16.91]) by kurims.kurims.kyoto-u.ac.jp (8.9.1a/3.6W) with ESMTP id LAA17626; Tue, 22 Sep 1998 11:35:44 +0900 (JST) To: pjt@cs.nott.ac.uk Cc: caml-list@inria.fr Subject: Re: polymorphic recursion In-Reply-To: Your message of "Mon, 21 Sep 1998 17:30:34 +0100" <36067F2A.22FE@cs.nott.ac.uk> References: <36067F2A.22FE@cs.nott.ac.uk> X-Mailer: Mew version 1.93 on Emacs 20.3 / Mule 4.0 (HANANOEN) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-Id: <19980922113340M.garrigue@kurims.kyoto-u.ac.jp> Date: Tue, 22 Sep 1998 11:33:40 +0900 From: Jacques GARRIGUE X-Dispatcher: imput version 980905(IM100) Content-Transfer-Encoding: 7bit Sender: weis > In some languages (most notably Haskell and Miranda) it is possible > to define a function that enjoys polymorphic recursion, i.e., the > types of its recursive calls may be instances of the type scheme at > which the function is defined. > > Can you do the same in OCaml? I am aware of the tricks mentioned in > the FAQ, but I would like to know if there is a cleaner way to do it, > for example by providing a type signature. To my knowledge, there is no direct way to do this. Part of the reason is that type signatures have a different role in Haskell and ML: in Haskell the type signature appears before its function, and restricts it explicitely, while in ML you write it in an independent signature file, which is not known when typing the function itself (signature matching takes place after the type checking). This does not matter very much in ML, since you explicitely decide which functions recurse with which (in Haskell all definitions in a module are a priori recursive), and there are only few examples really needing polymorphic recursion. To be complete on this point, in Objective Label method calls can be polymorphically recursive: # class r = object (self) method virtual m : 'a. 'a -> 'a method m x = let q = self#m true in let r = self#m 0 in x end;; class r : object method m : 'a. 'a -> 'a end Thanks to the mechanisms use for this inference, it would be easy to provide polymorphic recursion for functions also, but we go back to the ML problem: where do we write the signature ? Jacques --------------------------------------------------------------------------- Jacques Garrigue Kyoto University garrigue at kurims.kyoto-u.ac.jp JG