[Caml-list] interface of sorted collections

[Caml-list] interface of sorted collections

[Christian Lindig]

I have noted that in sorted collections like the Map and Set modules
(but also in SML/NJ's ORD_SET and ORD_MAP) it is impossible to find the
previous or next element for a given element. This seems strange, given
that the keys in these collections are sorted.

In my particular application I like to store (nested) intervals in a
map, sorted by their starting points. Given a point in an interval, I'd
like to obtain it from a sorted collection. This requires either a
find_less_equal function, that returns the key for an element if it
exists or its predecessor, or a prev_key function, that returns a key's
predecessor such that I can use the regular find afterwards.

Is there a way to implement this in OCaml without making a copy of the
Map module?

-- Christian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] interface of sorted collections

[Florian Hars]

Christian Lindig wrote:
> I have noted that in sorted collections like the Map and Set modules

They are unsorted collections. If you observe some kind of sorting in these 
collections, it is just an implementation accident.

Yours, Florian Hars.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] interface of sorted collections

[Damien Doligez]

On Wednesday, October 15, 2003, at 09:23 AM, Florian Hars wrote:

> Christian Lindig wrote:
>> I have noted that in sorted collections like the Map and Set modules
>
> They are unsorted collections. If you observe some kind of sorting in 
> these collections, it is just an implementation accident.

Not quite.  Both Set and Map demand ordered types as arguments, and
that's no accident.

-- Damien

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners