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 q28DVdMw020346 for ; Thu, 8 Mar 2012 14:31:44 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AoYEACO0WE/U4xEIjWdsb2JhbABDgwmCLK9pIgEBAQEHCwsJEgUkggoBAQQBIwRSEAsaAiYCAiE2BhMJEodqCQeoD5I0gS+ICYYggRYEjUeNY4U9h1o X-IronPort-AV: E=Sophos;i="4.73,552,1325458800"; d="scan'208";a="135030433" Received: from moutng.kundenserver.de ([212.227.17.8]) by mail4-smtp-sop.national.inria.fr with ESMTP; 08 Mar 2012 14:31:43 +0100 Received: from office1.lan.sumadev.de (dslb-084-059-064-196.pools.arcor-ip.net [84.59.64.196]) by mrelayeu.kundenserver.de (node=mreu1) with ESMTP (Nemesis) id 0M1CM0-1SKyQw1wrI-00tTs5; Thu, 08 Mar 2012 14:31:43 +0100 Received: from [192.168.5.106] (dslb-084-059-064-196.pools.arcor-ip.net [84.59.64.196]) by office1.lan.sumadev.de (Postfix) with ESMTPSA id 2A205C00CF; Thu, 8 Mar 2012 14:31:42 +0100 (CET) From: Gerd Stolpmann To: Goswin von Brederlow Cc: Gabriel Scherer , Edgar Friendly , caml-list@inria.fr In-Reply-To: <877gyv7k2t.fsf@frosties.localnet> References: <87sjhktqwi.fsf@frosties.localnet> <4F5777F2.2000806@gmail.com> <878vjctlr3.fsf@frosties.localnet> <877gyv7k2t.fsf@frosties.localnet> Content-Type: text/plain; charset="UTF-8" Date: Thu, 08 Mar 2012 14:31:42 +0100 Message-ID: <1331213502.2826.277.camel@thinkpad> Mime-Version: 1.0 X-Mailer: Evolution 2.28.3 Content-Transfer-Encoding: 7bit X-Provags-ID: V02:K0:fbwS4TCgd1hbmBHnqJolOsILaNUWlxCqZMt39STmZhg IsGvhCWgNqV/UmupKP1kFHDCrc/N/QBJRgeOJnoIzVVLYj5CFM QNWS7EQd6pzh8f9o+GRrCPMEs/dEWE6qsjDOpiVzgBbWE5Tyj2 HVzpQ1BoGylKpbTVu3FmMK2+CWEtNGCFxCCmiAd0UAM+nuH0/G r463dCkdZHqAYGUh+PUvNQniFIaLEzMjyAZrx2XsfrrQkYCUfT GU2eFEOSx8EEr+Kd2mZ2TbVB+twW65p4fUJKFbGRYnuPi0f5iR h3zAGPvXCqaiNQlohjWBEDbnNqTwx31yNNJcmkz0o1K634DbIe q/STebiQCHhg97LFU6gaSOwh6wGcU3NlmZSKFfIy9 Subject: Re: [Caml-list] Can one implement greedy/inline data structures in ocaml? 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 > > I do have an ugly solution but I'm hoping for some fresh idea not based > on what I already know is ugly. I can't be the only one that found the > need to keep an item in two containers and be able to remove it from > both quickly, right? > > MfG > Goswin > -- ------------------------------------------------------------ Gerd Stolpmann, Darmstadt, Germany gerd@gerd-stolpmann.de Creator of GODI and camlcity.org. Contact details: http://www.camlcity.org/contact.html Company homepage: http://www.gerd-stolpmann.de *** Searching for new projects! Need consulting for system *** programming in Ocaml? Gerd Stolpmann can help you. ------------------------------------------------------------