What isn't possible with Finite Maps, and should be.

George Russell ger@tzi.de
Thu, 08 Nov 2001 23:48:44 +0100

Once again I find myself wanting something like the following function with
finite maps:

   fmToListByRange :: Ord key => FiniteMap key elt -> (key,key) -> [(key,elt)]

fmToListByRange map (k1,k2)

is supposed to return all elements in the map with keys from k1 to k2 (inclusive).

Although this isn't as common as looking up an element by a key, it nevertheless is
sometimes useful, and shouldn't be too hard to implement, given that FiniteMaps
are going to be implemented (given the Ord constraint) as some sort of tree-like
query structure, so it's just a question of scanning down the tree splitting the
interval as you go.

Of course this can be generalised.  A general range would have type (Maybe key,Maybe key,Bool)
where Nothing instead of a key would mean starting at one of the ends, and the Bool would
indicate whether you gave the elements in increasing or decreasing order of key.

In any case it looks fairly simple to write.  If only I were set up to be able
to compile GHC I could write the necessary code myself . . .