On 07/01/2012 12:17, Christoph Breitkopf wrote:

Hello,

I wonder why Data.Map provides the indexed access functions:

http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-...

These functions seem rather out-of-place to me in the map api. The only use case I could think of so far would be to find the median, or in general n-th smallest key, but that does not seem sufficient reason (also, I think there are faster methods for that). Anything else?

I don't know the motivation in Data.Map, but here's some thoughts from a C++ home-rolled data structures perspective... Somewhere around a decade ago, I started an in-memory C++ multiway tree library, initially an experiment seeing if I could improve sequential access performance. This half-worked, but I still use the data structure primarily because it's a bit safer in some cases than the STL containers, and also has some extra functionality that makes it more convenient. Features include... 1. "cursor maintenance" (when I insert/delete, cursors/iterators are not invalidated except in the special case that the cursor references an item that is deleted. There are two tricks for this case - the cursor will at least know that the item is deleted, plus there are special cursors that can defer deletion (mainly for delete-the-current-item within loops). 2. Searching based on custom "comparisons" - mainly searching based on a partial key (certain fields), so you can find the first/last item equal to a partial key, ignoring less significant fields. 3. Finding the first key that is *not* in the container (for unsigned integer keys only). 4. Subscripted access - finding a given index, determining the index to an item referenced by a cursor, stepping forward/backward by a given number of items. The subscripted access isn't massively useful - it was implemented because I was curious how to handle it efficiently. However, cases do come up from time to time in strange places. For example, sometimes it's more convenient to store an index (into a container that won't change) than a cursor or a full key. And using an ordered container does tend to imply, after all, that you're interested somehow in the order (or else why not use a hash table?). One case, I guess, relates to DSL-generated data structures. The point there is that when the generated code runs, the map instance is long dead. Within the generated code, ranges etc tend to be identified by subscript - so the DSL needs to be able to translate from key to subscript, and (maybe) back again. OTOH, don't forget that laziness thing - if the code generator was working from a sorted array it would know the subscripts anyway. A particularly surprising side-effect - along with the map, multimap, set and multiset wrappers, I have a vector wrapper. When you have a huge array and do lots of inserts and deletes within that array, a multiway tree (with subscripted access) turns out to be a good trade-off. Some accesses are more awkward (because the items aren't all contiguous in memory), but the log-time inserts and deletes can be worth it. The first-key-not-in-the-container stuff was mostly a side-effect of the data structure augmentation I did for subscripted access. That is very convenient, but with costs. The no. 1 killer feature that keeps me using and maintaining this library is the partial-key search thing. This is so useful, I even added a feature to a DSL (used mainly for AST nodes and multiple dispatch - originally based on treecc) to make it more convenient to generate partial-key classes. The cursor maintenance makes it a lot easier to write algorithms that update the container, but it's perhaps surprising how rare that's necessary. The issue with all this is of course partly overhead, but also because I got lazy - keeping these things hanging around throughout whole program runs like cheap second-rate databases. They are quite convenient to work with, but for a long time I stopped even considering pulling all the data out into a flat array, processing it there, then rebuilding a new indexed data structure only if I really needed it, or keeping data mostly in an array and sorting it ready for binary searches just at the key point where that's needed. Some programs I've written using them are maybe an order of magnitude slower than they should be, and in quite a few cases there's an asymptotic difference, not just a constant factor - a lot of algorithms are O(n log n) where without the convenience containers they could be O(n). Very little of this would be relevant in a pure functional programming world, of course, but anyway - yes, subscripting can be (occasionally) useful. It's just hard to give specific examples, because they're buried in all the technicalities of quite large programs.