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 q297Tdwj026412 for ; Fri, 9 Mar 2012 08:29:39 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtcBABSxWU/ZSMDyi2dsb2JhbABDtTAiAQEBCgsLBxIFJIIKAQEEAScTPwULCw4TJQ8BBA0bIRMbh2oJuh2JOIceBJsbhVGHWg X-IronPort-AV: E=Sophos;i="4.73,555,1325458800"; d="scan'208";a="135152973" Received: from fmmailgate04.web.de ([217.72.192.242]) by mail4-smtp-sop.national.inria.fr with ESMTP; 09 Mar 2012 08:29:27 +0100 Received: from moweb001.kundenserver.de (moweb001.kundenserver.de [172.19.20.114]) by fmmailgate04.web.de (Postfix) with ESMTP id 751D5736BB20 for ; Fri, 9 Mar 2012 08:29:27 +0100 (CET) Received: from frosties.localnet ([95.208.118.96]) by smtp.web.de (mrweb002) with ESMTPA (Nemesis) id 0LoYFm-1SYuYW40Rm-00gEzo; Fri, 09 Mar 2012 08:29:27 +0100 Received: from mrvn by frosties.localnet with local (Exim 4.77) (envelope-from ) id 1S5uGU-00088Q-8G; Fri, 09 Mar 2012 08:29:26 +0100 From: Goswin von Brederlow To: Gerd Stolpmann Cc: Goswin von Brederlow , Gabriel Scherer , Edgar Friendly , caml-list@inria.fr References: <87sjhktqwi.fsf@frosties.localnet> <4F5777F2.2000806@gmail.com> <878vjctlr3.fsf@frosties.localnet> <877gyv7k2t.fsf@frosties.localnet> <1331213502.2826.277.camel@thinkpad> Date: Fri, 09 Mar 2012 08:29:26 +0100 In-Reply-To: <1331213502.2826.277.camel@thinkpad> (Gerd Stolpmann's message of "Thu, 08 Mar 2012 14:31:42 +0100") Message-ID: <87vcmez0yx.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:XB35EjzyW3z7onDswfmaFRaAXSnJ47Vwdk3sH++ZjC+ 3FG5gmTQ1bSHEycLdD+xeVynQFDTf9tpvwnm1nL6vNiiwoRgnz I2i+mjSYCkItJqBUJj8SeBoxxNgnhn5wHnjuUQu+URGvtc2PPD hhpJmotFnOCUbBgIGvnJR63lwaijBWgitr1rChkte3WntJHkKq EYlmHB28Af1BljWkPum4w== Subject: Re: [Caml-list] Can one implement greedy/inline data structures in ocaml? Gerd Stolpmann writes: > Am Donnerstag, den 08.03.2012, 06:11 +0100 schrieb Goswin von Brederlow: >> Gabriel Scherer writes: >> >> >> So then you need mutable option types or mutables that you initialize >> >> with dummy values and then overwrite with the real thing once all >> >> members of a cycle are created. Or some other trickery to make it >> >> work. Overall cycles are generally not good. >> > >> > I believe the trick you need (either passing a dummy value of your >> > type, or Obj.magic) is less ugly that your Camlp4 solution for inline >> > access. >> > If I really needed absolute performance, I'd use the inline version >> > just like in C, with mutable fields, but without preprocessor sugar. >> > Preprocessing could avoid a bit of duplication (corresponding to >> > manual inlining) on the structure-definition side, but wouldn't >> > simplify the structure-using code much. >> >> How? >> >> type task = { >> mutable all_next : task; >> mutable all_prev : task; >> mutable state_next : task; >> mutable state_prev : tast; >> ... >> } >> >> Now how do yout write DList.insert, DList.remove, DList.iter, ...? >> >> I'm looking for some nice tricks using closures, functors, first class >> modules or something to make it look pretty and easy to use. > > There is a solution with functors. However, I don't dare to predict how > fast it is (functors add additional indirection): > > module type DLINKABLE = sig > type t > val next : t -> t option > val prev : t -> t option > val set_next : t -> t option -> unit > val set_prev : t -> t option -> unit > end > > module type DHEAD = sig > type dlist > type t > val first : dlist -> t option > val last : dlist -> t option > val set_first : dlist -> t option -> unit > val set_last : dlist -> t option -> unit > end > > module DLIST(H : DHEAD)(L : DLINKABLE with type t = H.t) = struct > (* Here define operations over lists, e.g. *) > > let remove (dl:H.dlist) (x:D.t) = > ( match D.prev x with > | None -> > H.set_first dl (D.next x) > | Some p -> > D.set_next (D.next x) > ); > ( match D.next x with > | None -> > H.set_last dl (D.prev x) > | Some n -> > D.set_prev (D.prev x) > ) > end > > For a concrete application you would only have to implement DLINKABLE > and DHEAD, and then apply DLIST on these implementations. If elements > are members of several lists, do this for each list separately. I guess > you could define macros for generating DLINKABLE and DHEAD (even the > macros built into camlp4 could be good enough for this). > > Gerd That is a start. But you used an open ended doubly linked list. This makes it simpler because you can have an empty list and initialize items to not be linked to anything before inserting them. That avoids the cycles. If you have a closed (cyclic or ring) doubly linked list the problem becomes how to create the first element that must link to itself. Can you come up with something without option type or Obj.magic? Something that doesn't duplicate the initialization of the DList for each instance. MfG Goswin