From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p8D4uEr2007905 for ; Tue, 13 Sep 2011 06:56:14 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Au4BANXhbk7RVaGzkGdsb2JhbABChFWjFggUAQEBAQkJDQcUBCKBUgEBAQECARICDwQZARseAwELBgULAwwCJgICIgERAQUBHAY1h1WZUQqKfkKCV4VJO4htAgMGgSaEMYERBIdni1WMdD2DcA X-IronPort-AV: E=Sophos;i="4.68,372,1312149600"; d="scan'208";a="108741997" Received: from mail-gx0-f179.google.com ([209.85.161.179]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 13 Sep 2011 06:56:08 +0200 Received: by gxk1 with SMTP id 1so246016gxk.10 for ; Mon, 12 Sep 2011 21:56:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=mugk9Ty2M0byjujIARvHeB3u8ltc88QYK9WFF40x+LU=; b=Z8mUxJKSplzEr9qMjE2XWRzLW9nYb1d4F0P1KQ4d/FryvZLgflFCwFe7GTZHQWU8fn Yp8Z7zyIq9b0lLigBpp5VjTOkHSoLxprcsFwyjpFk4GuXxefCe1z062rCul6lUx6NF7A CI5L1bPlYAqF6XwpYe16MDoVR0mLRN0g3cfBY= MIME-Version: 1.0 Received: by 10.43.52.199 with SMTP id vn7mr1092192icb.414.1315889766980; Mon, 12 Sep 2011 21:56:06 -0700 (PDT) Received: by 10.42.218.10 with HTTP; Mon, 12 Sep 2011 21:56:06 -0700 (PDT) In-Reply-To: References: <14203FCD-811F-41CC-A0D7-5A360D4815CA@math.nagoya-u.ac.jp> Date: Tue, 13 Sep 2011 07:56:06 +0300 Message-ID: From: Dmitry Grebeniuk To: Jacques Garrigue Content-Type: text/plain; charset=UTF-8 Subject: Re: [Caml-list] recursive module, object types, tying knot Hello. >> I can't constrain the parametric type of module: >> let module M = (lst#mapmodule : Mappable with type t 'a = list a) >> -- one more way is blocked (but don't know was it the way >> really). > > This is indeed a restriction of locally abstract types that one > cannot use them as row variables. This might be done if there > are applications. I don't know whether it can help. In general, there seems to be no way to write a type of function that is polymorphic on some parametric type: "forall _ t, forall 'a, 'b, map: ('a -> 'b) -> 'a t -> 'b t". Maybe something like this could work: module type MAP = sig type 'a t val map : ('a -> 'b) -> 'a t -> 'b t end let gen_map1 = fun (type 'a tt) -> fun mapmodule -> let module M = (val mapmodule : MAP with type 'a t = 'a tt) in fun f -> fun (x : 'a tt) -> M.map f x (* or *) let gen_map2 mapmodule = let module M = (val mapmodule : MAP) in fun f (x : 'a M.t) -> M.map f x But the changes in typechecker should be too massive to make it work. So, it's better to forget my perfectionistic attempts. Anyway, I've learned many things about OCaml type system, so this was not completely useless work for me. And if some code should use "any mappable data structure", there is no other way than wrapping this code into functor. > On the other hand, fold can be defined as a polymorphic > method, allowing you to define functions building various kinds > of containers, starting from an arbitrary one. I've tried to write some code where the initial container is stored in the object itself, but couldn't make it work. And this approach (map = fold_right + cons) is somewhat limited, it will work good for single-linked lists, but I can't imagine it can work with more complex data structures like trees (and I can imagine the overhead of folding + consing over arrays). So I prefer to avoid such style of mapping.