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 p8D7NL1R012121 for ; Tue, 13 Sep 2011 09:23:21 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ApADALkDb07RVdQzk2dsb2JhbABCp2IIFAEBAQEJCQsJFAQigVMBAQEBAxICExkBGx0BAwwGBQsDCi4hAQERAQUBHAYTCBqgdwqLQIJXhUY7iG0CAwaGaASTPYoKgm09g3A X-IronPort-AV: E=Sophos;i="4.68,373,1312149600"; d="scan'208";a="108760634" Received: from mail-vw0-f51.google.com ([209.85.212.51]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 13 Sep 2011 09:23:16 +0200 Received: by vws20 with SMTP id 20so470151vws.10 for ; Tue, 13 Sep 2011 00:23:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type:content-transfer-encoding; bh=sfnfDJjK/bnUYcojJj3GWtULFKO09Vo8SAiP4nHU7uI=; b=GIV8xZvxsXFtqysZmnQGPg2TWYsISTUWbip0Hfk+aMMS4L2+k0oEZ381Y5Ewqi/OKV T6sxYzGWSbSlreihcT1SnD3XAmkJ4EBrapfebJSjVIZ/7gwW4cUpW1yTf9chuT0Z9Oep Wb/f0ej/s9buJlCUM+1GvZWTg2gGu6QXvKSgw= Received: by 10.52.74.105 with SMTP id s9mr1904919vdv.347.1315898594421; Tue, 13 Sep 2011 00:23:14 -0700 (PDT) MIME-Version: 1.0 Received: by 10.52.165.10 with HTTP; Tue, 13 Sep 2011 00:22:52 -0700 (PDT) In-Reply-To: References: <14203FCD-811F-41CC-A0D7-5A360D4815CA@math.nagoya-u.ac.jp> From: Gabriel Scherer Date: Tue, 13 Sep 2011 09:22:52 +0200 Message-ID: To: Dmitry Grebeniuk Cc: Jacques Garrigue Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p8D7NL1R012121 Subject: Re: [Caml-list] recursive module, object types, tying knot On Tue, Sep 13, 2011 at 6:56 AM, Dmitry Grebeniuk wrote: >  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 You may define more general folds. The idea is that from any algebraic datatype you can derive a fold operator. See for example: type 'a list = Nil | Cons of 'a * 'a list val list_fold : 'r -> ('a -> 'r -> 'r) -> 'r type 'a tree = Nil | Leaf of 'a list * 'a * 'a list val tree_fold : 'r -> ('r -> 'a -> 'r) -> 'r type ('a, 'b, 'c) strange_list = | End of 'c | ACons of 'a * ('a, 'b, 'c) strange_list | BCons of 'b * ('a, 'b, 'c) strange_list val strange_list_fold : ('c -> 'r) -> ('a -> 'r -> 'r) -> ('b -> r -> r) -> r The idea is that for each constructor of the datatype, you add an argument to the fold, that has the same signature as its type as a function (Nil : 'a list) (Cons : 'a -> 'a list -> 'a list), with recursive occurences of the type replaced by the elimination type parameter 'r. There is a more abstract construction : if you express recursive datatypes as fixpoint of a type with one more parameter (~ polynomial functor), you can define fold recursively from a `map` operation on this type. For example, ('a list) is the fixpoint on 'b of (type ('a, 'b) cons = Nil' | Cons' of 'a * 'b), which is witnessed by the existence of reciprocal (val wrap : ('a, 'a list) cons -> 'a list) and (val unwrap : 'a list -> ('a, 'a list cons)), and (some form of) list_fold can be defined as let rec list_fold li = f (map_cons (list_fold f) (unwrap li)) For a more abstract and hardly readable presentation of this topic, see the article "Functional programming with Bananas, Lenses, Envelopes and Barbed Wire" by Meijer, Fokkinga and Paterson, 1991. > (and I can imagine the overhead of folding + consing > over arrays). So I prefer to avoid such style of mapping. An `iter` function is sufficient for arrays: class type ['a] array = object ... method length : int method iter : (int -> 'a -> unit) -> unit end You can then express the map operation: let map f t = let result = make_array t#length in t#iter (fun i x -> result#set i (f x)); result An internal map would have to allocate a new array anyway (in the general case where (f : 'a -> 'b), you can't mutate the array in-place), so this is as efficient memory-wise. Similarly, a map defined by the user from a fold on a recursive datatype has the same allocation profile as an internally-defined fold. The only potential overhead comes from the passing of the fold function (which means one more indirect call per node traversed), but if you're at this level of detail you may not want to design your core data structures as object anyway.