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 q27EfONV002030
	for <caml-list@sympa-roc.inria.fr>; Wed, 7 Mar 2012 15:41:24 +0100
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AncDAOhyV0/ZSMD4jWdsb2JhbABDtRciAQEBAQcLCwkSBSSCS3s0AQQoiECYaqBUjU2DIgSbEo0q
X-IronPort-AV: E=Sophos;i="4.73,545,1325458800"; 
   d="scan'208";a="134855293"
Received: from fmmailgate07.web.de ([217.72.192.248])
  by mail4-smtp-sop.national.inria.fr with ESMTP; 07 Mar 2012 15:41:18 +0100
Received: from moweb002.kundenserver.de (moweb002.kundenserver.de [172.19.20.108])
	by fmmailgate07.web.de (Postfix) with ESMTP id 2430CDA5AD2
	for <caml-list@inria.fr>; Wed,  7 Mar 2012 15:41:18 +0100 (CET)
Received: from frosties.localnet ([95.208.118.96]) by smtp.web.de (mrweb001)
 with ESMTPA (Nemesis) id 0MOSAP-1RzVAB0KeL-005vdn; Wed, 07 Mar 2012 15:41:18
 +0100
Received: from mrvn by frosties.localnet with local (Exim 4.77)
	(envelope-from <goswin-v-b@web.de>)
	id 1S5I3J-0003jD-IB
	for caml-list@inria.fr; Wed, 07 Mar 2012 15:41:17 +0100
From: Goswin von Brederlow <goswin-v-b@web.de>
To: caml-list@inria.fr
Date: Wed, 07 Mar 2012 15:41:17 +0100
Message-ID: <87sjhktqwi.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:StbICMS414ePghP0hzaQbk0e5LHYiQxUxMrbZcfcc/K
 Uh58vf5fSn+ZGVg/bGEhMx+15SGuS+XhJdskojl++pJIc4l92I
 /YKE8nmBB7SmoIhwGUoLGl+c8F/llO3Hw6W0hwsL8O+sIM+HHo
 uXTMUZUAXdIo54wZlw3PW+aoWxYopVc7KVvW+C4s7CjmFERI+h
 A1CGNzNoFlOlfZE5TRrSg==
Subject: [Caml-list] Can one implement greedy/inline data structures in ocaml?

Hi,

I'm wondering if it is possible to implement greedy/inline data
structures in ocaml in a generic and reusable way.

Maybe you don't know what greedy/inline data structures are or maybe I'm
using the wrong name. So here is what I mean:

Say you have a task structure that is in 2 doubly linked list. One list
links all the structures together and the second list links structures
with the same internal state (running, sleeping, waiting, ...). In C you
would then have something like this:

struct task {
  DLIST(task, all);
  DLIST(task, state);
  foo_t data;
}

The DLIST makro adds the prev/next pointers to the struct, one set
prefixed with all, the other with state. There would also be makros to
to init, insert, remove and iterate of the two lists.

The internal pointer needed for the DLIST are part of the struct
task. The big advantage of this (and why I ask) is that given a task one
can esily remove it from both lists.

On the other hand if the list is external to the struct and only
contains a pointer to the task then removing a task becomes
difficult. The task then needs pointers to each of the lists data
structures creating cycles. Not good for ocaml. It also would waste
memory for 2 pointers (per list).



So how would you design such greedy/inline data structures in ocaml?

Or how else would you design containers (list, doubly linked list,
queue, ...) so that things can be in multiple containers and removing
them is fast?

MfG
        Goswin