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 p89DoNHo022288
	for <caml-list@sympa-roc.inria.fr>; Fri, 9 Sep 2011 15:50:23 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AhwFAPAYak7RVdIpimdsb2JhbABBnR+KaAUDFAEBAQoJDQcSBiKBUgEBAQECARICExMGATgBAwELAQUFDjg0AQUBHAY1h1SaXAqOFYVViSgCAwaGCGAEh2uLTYUVgSmGND2BR4Iz
X-IronPort-AV: E=Sophos;i="4.68,356,1312149600"; 
   d="scan'208";a="108288514"
Received: from mail-pz0-f41.google.com ([209.85.210.41])
  by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 09 Sep 2011 15:50:17 +0200
Received: by pzk4 with SMTP id 4so3394757pzk.14
        for <caml-list@inria.fr>; Fri, 09 Sep 2011 06:50:15 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        h=sender:subject:mime-version:content-type:from:in-reply-to:date:cc
         :content-transfer-encoding:message-id:references:to:x-mailer;
        bh=q5cJas38SR44IRTJhb1tV4IH6ep8fiLdey5DauKBHIA=;
        b=EETVVNo0O+xcW91iMx1SlSlPGEcDHPWiyxjkhFqWDC5wDBhDM4E71XBEcro/R1XeBb
         /5h7kjFxuEc4pDWVdWhO2NchrHlNNwgDyY10I65i3GmxJyfYbIHhGytHOG+quiOsJR8n
         T3vTTc8L65010rAUwiYX7SxXApROEgU+Hrlh8=
Received: by 10.68.29.5 with SMTP id f5mr2947261pbh.149.1315576215627;
        Fri, 09 Sep 2011 06:50:15 -0700 (PDT)
Received: from [192.168.0.153] (g1-223-25-183-15.bmobile.ne.jp. [223.25.183.15])
        by mx.google.com with ESMTPS id f6sm20478312pbp.2.2011.09.09.06.50.11
        (version=TLSv1/SSLv3 cipher=OTHER);
        Fri, 09 Sep 2011 06:50:14 -0700 (PDT)
Sender: Jacques Garrigue <jacques.garrigue@gmail.com>
Mime-Version: 1.0 (Apple Message framework v1084)
Content-Type: text/plain; charset=us-ascii
From: Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>
In-Reply-To: <CAPi0vKWEMh=5PmA1ekpbOMqcEpkGBEzo-LkoCAXd-5cqmusY+w@mail.gmail.com>
Date: Fri, 9 Sep 2011 22:50:01 +0900
Cc: caml-list <caml-list@inria.fr>
Content-Transfer-Encoding: 7bit
Message-Id: <AD8C45FF-E066-4879-AB24-00C4278BA26A@math.nagoya-u.ac.jp>
References: <CAPi0vKXHQ3SyChtphJ7OAtAnDNK5TpfXqq_nKBF7aA0nGHovHw@mail.gmail.com> <14203FCD-811F-41CC-A0D7-5A360D4815CA@math.nagoya-u.ac.jp> <CAPi0vKWEMh=5PmA1ekpbOMqcEpkGBEzo-LkoCAXd-5cqmusY+w@mail.gmail.com>
To: Dmitry Grebeniuk <gdsfh1@gmail.com>
X-Mailer: Apple Mail (2.1084)
Subject: Re: [Caml-list] recursive module, object types, tying knot

On 2011/09/09, at 20:14, Dmitry Grebeniuk wrote:

>> Namely recursive types in ocaml must be regular.
>> I.e., they must expand to a finite graph.
>> In particular this means that, inside the class lst, all occurences
>> of lst must have exactly the parameter 'a.
> 
>  Just interesting: where this graph and its finiteness property
> are used?

Well, there are many algorithms that must do exhaustive traversal
of types to verify some property, and it implies that the type must
be finite.
Also, while unification on regular types is easy, I don't know of
any algorithms for non-regular types.

>> As you have already found, you can avoid this problem by
>> defining a record which "hides" the use of lst.
>> Namely, you must break the cycle with a datatype,
>> either record or sum type.
>> Unfortunately this also means that this type has to belong
>> to some module, and you also lose subtyping.
> 
>  I've tried to make the type (lst 'b) belong to some first-class
> module returned by some method call (to object with type
> lst 'a), but without any success.
>  And while playing with first-class modules I've noted that
> 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.

>  But I can reformulate (and maybe make easier) my task:
> I can move the code that work with different type parameters
> (lst 'a -> lst 'b) to simple functions.  For example, "map" for
> containers -- to the function like "container_map", which
> will work with containers (objects that have some methods),
> to make the code work:
> container_map func (new lst [1;2;3]);
> container_map func (new arr [|1;2;3|]).
>  I understand that the imaginable "container_map" function
> should require some method with some type, that can
> give me the value of type lst 'b for lst 'a in case of lists,
> and the value of type arr 'b for arr 'a in case of arrays,
> but I can't write such type (even with first-class modules).
>  Is it impossible too?

The main problem is that you cannot define a constructor
method which return an object with a different parameter.
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.

Jacques Garrigue