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 q297oPbb027004 for ; Fri, 9 Mar 2012 08:50:25 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgsDANS1WU/ZSMD3k2dsb2JhbABDtTAiAQEBAQkJCwkUAySCCgEBAQMBAQIkEz8FCwshJQ8BBA0HFCETG4dqCQe6GgSJOIceBJMgh3uFUYda X-IronPort-AV: E=Sophos;i="4.73,557,1325458800"; d="scan'208";a="135155263" Received: from fmmailgate06.web.de ([217.72.192.247]) by mail4-smtp-sop.national.inria.fr with ESMTP; 09 Mar 2012 08:50:24 +0100 Received: from moweb001.kundenserver.de (moweb001.kundenserver.de [172.19.20.114]) by fmmailgate06.web.de (Postfix) with ESMTP id 3424FE3A32A for ; Fri, 9 Mar 2012 08:50:23 +0100 (CET) Received: from frosties.localnet ([95.208.118.96]) by smtp.web.de (mrweb001) with ESMTPA (Nemesis) id 0LqlAw-1Sb6TM2tJi-00eAkL; Fri, 09 Mar 2012 08:50:23 +0100 Received: from mrvn by frosties.localnet with local (Exim 4.77) (envelope-from ) id 1S5uak-0000Wp-6W; Fri, 09 Mar 2012 08:50:22 +0100 From: Goswin von Brederlow To: Gabriel Scherer Cc: Goswin von Brederlow , caml-list@inria.fr References: <87sjhktqwi.fsf@frosties.localnet> <4F5777F2.2000806@gmail.com> <878vjctlr3.fsf@frosties.localnet> <877gyv7k2t.fsf@frosties.localnet> Date: Fri, 09 Mar 2012 08:50:22 +0100 In-Reply-To: (Gabriel Scherer's message of "Thu, 8 Mar 2012 09:51:10 +0100") Message-ID: <87mx7qz001.fsf@frosties.localnet> User-Agent: Gnus/5.110009 (No Gnus v0.9) XEmacs/21.4.22 (linux, no MULE) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Provags-ID: V02:K0:cd+4gW9HLVC0DY6+2MCEnfAVQCLdM2fXj/HzmVNPrjz 7S4na/KuWlIBW1JaTmu/NghJubgl2lb0JADCXSajrawp/GuYhE 4C3KOpudMH69IkzlRMnE3hdBmNNYO28aSmWWcbhwzeP8T7flzX 79Y3z7eaqocoQGEhW1yUYucBdH6k8gHqJehF9w287RWMOZnfFX PbwEFBOphE/Tzig1lRtZA== Subject: Re: [Caml-list] Can one implement greedy/inline data structures in ocaml? Gabriel Scherer writes: > I have implemented a small example in two versions: one with external > dllist (I'm using the Batteries Dllist module), which indeed needs a > small hack to bootstrap a single-element cycle, and one with inline > pointers as you show, using simple value recursion. In the second case > I also have a small abstraction layer for traversals -- only > instantiated in the 'iter' case currently -- that could save some code > duplication; that must be one of the "closures" tricks you were > thinking of, but I don't claim that it's as efficient than duplicated > specialized traversal functions. > > The code is here: > https://gitorious.org/gasche-snippets/outside-or-inline-lists/blobs/master/goswin_dllists.ml For the fun of it I wrote a version with first class modules. It is pretty much like your inline solution with records of closures, just a different syntax. The one thing I can't eliminate is the code duplication for the initialization. I'm starting to believe there is no way around using Obj.magic or option types there. At least for the verry first task (in each dlist). The right-hand restriction in a let rec simply prevents putting that code into a function. For DList the duplication is minimal because the container is so simple. But for more complex container more code would have to be duplicated. The code could be hidden behind camlp4 though. MfG Goswin ---------------------------------------------------------------------- (* Type for doubly linked list *) type 'a dlist = { mutable next : 'a; mutable prev : 'a; } (* Module to access a container in another type *) module type Accessor = sig type a val get : a -> a dlist end (* create an access module from a closure *) let make_accessor : 'a . ('a -> 'a dlist) -> (module Accessor with type a = 'a) = fun (type c) (fn : c -> c dlist) -> let module M = struct type a = c let get x = fn x end in (module M : Accessor with type a = c) (* Iterator over a DList *) let get_next : 'a . (module Accessor with type a = 'a) -> 'a -> 'a = fun (type a) x y -> let module D = (val x : Accessor with type a = a) in (D.get y).next (* Now lets use this: *) (* A task has 2 DList: all and state *) type task = { all : task dlist; state : task dlist; name : string; } (* Accessors for the two DLists *) let all = make_accessor (fun task -> task.all) let state = make_accessor (fun task -> task.state) (* Some sample tasks *) let rec task1 = { all = { next = task2; prev = task2; }; state = { next = task1; prev = task1; }; name = "task1"; } and task2 = { all = { next = task1; prev = task1; }; state = { next = task2; prev = task2; }; name = "task2"; } let () = Printf.printf "all_next = %s, state_next = %s \n" (get_next all task1).name (get_next state task1).name