Re: [Caml-list] Can one implement greedy/inline data structures in ocaml?

[Goswin von Brederlow <goswin-v-b@web.de>]

Markus Weißmann <markus.weissmann@in.tum.de> 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