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 q2ACc5uQ005023 for ; Sat, 10 Mar 2012 13:38:05 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AjoEAJdKW0/ZSMDyjmdsb2JhbABDtT8iAQEBAQkLEhIFJIIKAQEEATIBRgULCyElDwEEKCEKCYgFCbo8kQEEizCPcn6MMw X-IronPort-AV: E=Sophos;i="4.73,561,1325458800"; d="scan'208";a="135352924" Received: from fmmailgate04.web.de ([217.72.192.242]) by mail4-smtp-sop.national.inria.fr with ESMTP; 10 Mar 2012 13:38:00 +0100 Received: from moweb002.kundenserver.de (moweb002.kundenserver.de [172.19.20.108]) by fmmailgate04.web.de (Postfix) with ESMTP id DA9E5737E77B for ; Sat, 10 Mar 2012 13:37:59 +0100 (CET) Received: from frosties.localnet ([95.208.118.96]) by smtp.web.de (mrweb002) with ESMTPA (Nemesis) id 0M9oW8-1SCyK728Cm-00BrUP; Sat, 10 Mar 2012 13:37:59 +0100 Received: from mrvn by frosties.localnet with local (Exim 4.77) (envelope-from ) id 1S6LYc-0001xm-NG; Sat, 10 Mar 2012 13:37:58 +0100 From: Goswin von Brederlow To: Markus Weissmann Cc: "Gabriel Scherer" , caml-list@inria.fr In-Reply-To: <57461.143.164.102.13.1331299783.squirrel@webmail.mwn.de> ("Markus Weissmann"'s message of "Fri, 9 Mar 2012 14:29:43 +0100 (CET)") References: <87sjhktqwi.fsf@frosties.localnet> <4F5777F2.2000806@gmail.com> <878vjctlr3.fsf@frosties.localnet> <877gyv7k2t.fsf@frosties.localnet> <87mx7qz001.fsf@frosties.localnet> <57461.143.164.102.13.1331299783.squirrel@webmail.mwn.de> User-Agent: Gnus/5.110009 (No Gnus v0.9) XEmacs/21.4.22 (linux, no MULE) Date: Sat, 10 Mar 2012 13:37:58 +0100 Message-ID: <878vj8skbd.fsf@frosties.localnet> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Provags-ID: V02:K0:YSh3xQouvk2D2ynSZs1Xh8Z7SPGZIxPIf2dcJTMMMDC 5nkiGc1gfWAa8+TXtSx5qwmghIIW+jv4q/Lx5iQO+sjZCHr2Un qmLKnKbNxX7xCWgvoy7DUZ4U/g22QFB42EQ/NWyFhH2VLumygM 6cD1Kg9AhiNnOeAuZTVX0xR0zeBJ0gDOpSDj9NrGmUOjKs4dNF pfIrvuc04Q6hrecdD/fsw== Subject: Re: [Caml-list] Can one implement greedy/inline data structures in ocaml? Markus Weißmann writes: > Taking one step back, what you actually want is a data structure that: > > -is a container for elements of some type 'a > -some elements are tagged with a "state" tag 'b > -the elements have an ordering > -you can add elements > -you can tag elements with a "state" tag > -you can remove the current element > -you can remove the tag from the current element > -you can get the current element > -you can move the current element one step (forward&backward) > -you can get the tag of the current element > -you can move the current element one step to the next/prev tagged one No, that was just the simplest example I could think of. > And you want this structure to be fast, right? Or do you only care about > the concrete implementation? > You should think about the type of the elements and tags you want to be > able to use: Do they have a natural ordering? Are they hashable? > > I would advice you to 1st write the interface with the functions you > require, then think about the implementation. I'm under the impression > that you have a decent C implementation and want to transfer that to OCaml > at all costs. I want a set of standard containers that are combinable so that given an element from any one of the containers it can be removed from all of them efficiently. Efficient doesn't allways equal fast. What I don't want is an operation that should be O(1) to suddenly take O(log n). More generally given an element from any one of the containers all the normal operation of any other container should be possible. All containers should have a "remove this element" operation. Lists have a "next". Double linked lists have "next" and "prev". Priority queue should have "change priority". Queue might have "move to front" and "move to back". MfG Goswin