I just finished writing a solution to a programming contest problem from the 2011 ACM world finals. My solution involved maintaining a sequence of lines ordered by slope. I wanted to use a Map, where the key was the slope and the value was a point (x,y) that the line went through.

At one point the algorithm requires splitting this list at a particular slope, deleting some of the lines neighboring that slope, and then joining the two sorted lists back together.

I was unable to figure out how to do this efficiently using Map.

Let me be more specific. Suppose I create a create sets of integers with:

module Iset = Set.Make (struct type t = int let compare = compare end)

Now if I have two sets a and b, where all the integers in a are less than all the integers in b, I can join them together with:

Iset.union a b

And this runs in O(log n) time where n is the number of elements in a+b. (This fact is not stated in the documentation, but you can derive it from the code in set.ml. It's a beautiful implementation.)

However, there is apparently no way to do this with a Map. You can try to use "merge", but this traverses both of the trees, and runs in O(n) time instead of O(log n) time.

So I solved my problem, in a somewhat cumbersome way, using sets instead of maps. The maps module really ought to support this. So this is not really a question. It's an observation that there's something substantial missing in the maps module.

My solution is here:

http://www.cs.cmu.edu/~sleator/work/works.ml
The problems is problem F here:

http://cm.baylor.edu/digital/icpc2011.pdf
Danny Sleator

Carnegie Mellon University