From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 7C0EFBC69 for ; Thu, 9 Nov 2006 22:44:54 +0100 (CET) Received: from sigma957.cis.mcmaster.ca (sigma957.CIS.McMaster.CA [130.113.64.83]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id kA9LirVi029600 for ; Thu, 9 Nov 2006 22:44:54 +0100 Received: from Gorash7.UTS.McMaster.CA (Gorash7.UTS.mcmaster.ca [130.113.196.61]) by sigma957.cis.mcmaster.ca (8.13.7/8.13.7) with ESMTP id kA9LiUF7026825 for ; Thu, 9 Nov 2006 16:44:48 -0500 (EST) Received: from cgpsrv2.cis.mcmaster.ca (univmail.CIS.McMaster.CA [130.113.64.46]) by Gorash7.UTS.McMaster.CA (8.13.7/8.13.7) with ESMTP id kA9LhoAI012371 for ; Thu, 9 Nov 2006 16:43:50 -0500 Received: from [69.193.76.85] (account carette@univmail.cis.mcmaster.ca HELO [192.168.1.101]) by cgpsrv2.cis.mcmaster.ca (CommuniGate Pro SMTP 4.1.8) with ESMTP-TLS id 148356269 for caml-list@inria.fr; Thu, 09 Nov 2006 16:44:22 -0500 Message-ID: <4553A139.2070103@mcmaster.ca> Date: Thu, 09 Nov 2006 16:44:25 -0500 From: Jacques Carette Organization: McMaster University User-Agent: Thunderbird 1.5.0.7 (Windows/20060909) MIME-Version: 1.0 To: caml-list@inria.fr Subject: Higher-order kinds? Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-PMX-Version-Mac: 4.7.1.128075, Antispam-Engine: 2.4.0.264935, Antispam-Data: 2006.11.9.123433 X-PerlMx-Spam: Gauge=IIIIIII, Probability=7%, Report='__CP_URI_IN_BODY 0, __CT 0, __CTE 0, __CT_TEXT_PLAIN 0, __HAS_MSGID 0, __MIME_TEXT_ONLY 0, __MIME_VERSION 0, __SANE_MSGID 0, __USER_AGENT 0' X-Miltered: at discorde with ID 4553A155.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; higher-order:01 higher-order:01 ocaml:01 metaocaml:01 oleg:01 haskell:01 bool:01 bool:01 first-order:01 haskell:01 translated:01 functors:01 functors:01 verbose:01 implements:01 Is there any way to get higher-order kinds in Ocaml? While investigating some issues around partial evaluation (in MetaOCaml), we ran across this post from Jacques Guarrigue: http://caml.inria.fr/pub/ml-archives/caml-list/2006/09/05dcdcb7064cc73bfdfb756a419a9010.fr.html After a few emails between Ken Shan and Oleg Kiselyov, Ken produced a very elegant translation of this 'trick' into Haskell, which starts off thus: data T f = Bool (f Bool) | Int (f Int) | Fun (T (F1 f)) newtype F1 f a = F1 { f1 :: T (F2 f a) } newtype F2 f a b = F2 { f2 :: f (a -> b) } Note how f in the above it a type-level function, and the types F1 and F2 are used 'partially applied'. It is possible to expand this all out into first-order, but the end result is not pretty, to say the least! Note that the rest of the Haskell code (classes and instances) can be translated into Functors and Modules [using that nice trick of having functors that produce module types, again thanks to Jacques G.]. The end result is definitely more verbose than the Haskell, but not desperately so. Jacques PS: rest of code, which just implements in an 'open' way what Jacques G. did using closed types in the email linked-to above class Dynamic t where inj :: f t -> T f prj :: T f -> Maybe (f t) instance Dynamic Bool where inj = Bool prj (Bool x) = Just x prj _ = Nothing instance Dynamic Int where inj = Int prj (Int x) = Just x prj _ = Nothing instance (Dynamic a, Dynamic b) => Dynamic (a -> b) where inj x = Fun (inj (F1 (inj (F2 x)))) prj (Fun t) = prj t >>= prj . f1 >>= return . f2 prj _ = Nothing