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 q288pnNM010686 for ; Thu, 8 Mar 2012 09:51:53 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AoABADlyWE/RVdS2kGdsb2JhbABDtRwIIgEBAQEJCQ0HFAQjggoBAQEEAQIPAiwBGx0BAwwGBQsNLiEBAQUMAQUBHAYTGweHZguccwqLdIJxhTU/iHQBAQQLiS2HNgSTHIIliyGDGD2EBQ X-IronPort-AV: E=Sophos;i="4.73,551,1325458800"; d="scan'208";a="134973600" Received: from mail-wi0-f182.google.com ([209.85.212.182]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 08 Mar 2012 09:51:52 +0100 Received: by mail-wi0-f182.google.com with SMTP id hn6so265603wib.27 for ; Thu, 08 Mar 2012 00:51:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type:content-transfer-encoding; bh=QGkK+W7xP4m+9V2ofP2vromT16xZbpoEnRsMbeXUEVw=; b=wicrdYg0cT8rOrcp0Gx+RjNB+cwjMkQbXb0YpD6epz70dBUcbv+U31OuVbWoRj3HZo s0/0tFHijqmVeAVkUTM6fIhaM1lCOvZWI1TEuK8zfu2yle1/J/QwUtl4EWQo8KlvDoef fBtp++lykb0Ra5gSfq96QVQFuBJ2c35HxTSDOHt8j2Sze+TNlMkqrrosJvxYS/koOF4G Vu4pNB+7U2MeHa08wFXUBeBSfx8ZFCGnztpCPbkanWgoxCpZAXmA3FBT+FpAH83/bLmE QXwIQpVMHH6qVP1peMS83p3xgOJe1EirYFTp0V5iqVIObReEt6f7Pw11Z+DiPVIG75Me uXGw== Received: by 10.180.88.199 with SMTP id bi7mr10740956wib.12.1331196712567; Thu, 08 Mar 2012 00:51:52 -0800 (PST) MIME-Version: 1.0 Received: by 10.227.200.85 with HTTP; Thu, 8 Mar 2012 00:51:10 -0800 (PST) In-Reply-To: <877gyv7k2t.fsf@frosties.localnet> References: <87sjhktqwi.fsf@frosties.localnet> <4F5777F2.2000806@gmail.com> <878vjctlr3.fsf@frosties.localnet> <877gyv7k2t.fsf@frosties.localnet> From: Gabriel Scherer Date: Thu, 8 Mar 2012 09:51:10 +0100 Message-ID: To: Goswin von Brederlow Cc: caml-list@inria.fr 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 q288pnNM010686 Subject: Re: [Caml-list] Can one implement greedy/inline data structures in ocaml? 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 On Thu, Mar 8, 2012 at 6:11 AM, Goswin von Brederlow wrote: > 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. > > 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