On 7/4/2012 5:02 AM, Thomas Schilling wrote:

I'm surprised that these functions already exists in Data.Map. What are the use cases?

One can use the indexing functions to retrieve a random element from the container, or to random-shuffle a container in n log n time.

OK, that seems like a reasonable use case.

The existing documentation is lacking, though. For example, the above use case requires that: 0 <= index < Map.size map

Yes, that is the case. The documentation should definitely improve.

It's also not specified that the index refers to the index in the sorted sequence. Of course, that problem here is that "Ord" -- which is really an implementation detail -- becomes part of the specified properties of a Map/Set. E.g., the same function for HashMap probably wouldn't make that guarantee.

Agreed. These indexing methods work only for OrderededSet and OrderedMap, not for HashMap and HashSet. If the Data.Set and Data.Map modules were called Data.OrdSet and Data.OrdMap, then there would be no problem including the indexing API in them. Personally I consider Data.Set to be Data.OrdSet, not a generic Set API. If we every create a Set class, the indexing API will definitely _not_ be part of it. BTW, the indexing API is currently _not_ part of IntSet and IntMap. The reason is that the data structure does not allow efficient implementation of the indexing API.

I.e., what are the properties of these functions? Do we have:

- findIndex a set `compare` findIndex b set ==> a `compare` b

it is even true that - findIndex a set `compare` findIndex b set <==> a `compare` b because (flip findIndex set) is a bijection respecting ordering.

- findIndex a set == findIndex a (Set.toList set)

This one holds too. It could be considered a definition of Set.findIndex, but the Set.findIndex is more efficient than the list version. Cheers, Milan

On Thu, Jul 5, 2012 at 8:01 AM, Milan Straka wrote:

Agreed. These indexing methods work only for OrderededSet and OrderedMap, not for HashMap and HashSet.

If the Data.Set and Data.Map modules were called Data.OrdSet and Data.OrdMap, then there would be no problem including the indexing API in them. Personally I consider Data.Set to be Data.OrdSet, not a generic Set API. If we every create a Set class, the indexing API will definitely _not_ be part of it.

I've also considered Map and Set to be OrdMap and OrdSet for quite a while. If we ever add a type class to abstract over e.g. HashMap and Map we'd probably call it Data.Map.Class or something. A potential downside to adding these functions is that I don't know if we can support them efficiently with a different implementation of ordered trees than the size-balanced ones. I still think we should add them though. -- Johan

On Thu, Jul 5, 2012 at 8:01 AM, Milan Straka wrote:

Any balanced tree can support indexing API, as long as every subtree stores its size. That is obviously trivially true for size-balanced trees, as the subtree sizes are used for balancing. If for example AVL trees were used, sizes would have to be stored explicitly in every node for indexing API to work fast.

There might be some other benefits to adding the size as well. IIRC union is faster if the first set is smaller than the second set. If we can look up the sizes in O(1) time we can rearrange the arguments to make sure this is the case. -- Johan

Hi,

On Tue, Jul 10, 2012 at 1:59 AM, Johan Tibell wrote:

...

On Thu, Jul 5, 2012 at 8:01 AM, Milan Straka wrote:

...

Any balanced tree can support indexing API, as long as every subtree stores its size. That is obviously trivially true for size-balanced trees, as the subtree sizes are used for balancing. If for example AVL trees were used, sizes would have to be stored explicitly in every node for indexing API to work fast.

There might be some other benefits to adding the size as well. IIRC union is faster if the first set is smaller than the second set. If we can look up the sizes in O(1) time we can rearrange the arguments to make sure this is the case.

I've always wondered why Data.Map doesn't do this by default. E.g. I have:

-- | Map.union says it's more efficient with @big `union` small@, so this one -- flips the args to be more efficient. It's still left-biased. union2 :: (Ord k) => Map.Map k v -> Map.Map k v -> Map.Map k v union2 m1 m2 | Map.size m1 < Map.size m2 = m2 `right` m1 | otherwise = m1 `Map.union` m2 where right = Map.unionWith (\_ a -> a)

there are several problems with this. Most notably, it is not true that "set1 < set2" is always better than "set1 > set2" -- if you run the containers/benchmarks/SetOperations/bench-SetOperations-Map benchmark, you can see that for different input distributions, "set1 < set2" is sometimes faster and sometimes slower than "set1 > set2". For various input distributions, difference between "set1 < set2" and "set1 > set2" are -7.5%, -25%, -35%, -17%, +20%, +8%, -13%. Also union is more efficient than (unionWith const), because is preserves sharing of the nodes present in both sets. That could be solved by creating another implementation of right-biased unionR which also preserves sharing. Probably the best idea is just to remove the documentation comment about "bigset `union` smallset" being faster, as it is not true :) Cheers, Milan

...

I'd like to add the following indexing operations for Data.Set.Set, to complement the existing functions for Data.Map.Map:

findIndex :: Ord a => a -> Set a -> Int lookupIndex :: Ord a => a -> Set a -> Maybe Int elemAt :: Int -> Set a -> a deleteAt :: Int -> Set a -> Set a

I'm surprised that these functions already exists in Data.Map. What are the use cases?

For an ordered Set, it makes sense to be able to work with the elements using their ordering -- i.e., to work with "i-th least element of s", i.e. the element toAscList s !! i. If you have for example a set of words of some language, you might want to work with those not explicitly, but using "i-th word of the language". Of you might want to find the median of the elements in the set.

I assume the only sensible semantics is to behave as a slightly more efficient version of the same function working on "Set.toList set" which must be ordered.

Yes. But the "slightly" means exponentially -- getting the median of the set takes linear time using Set.toList, but only logarithmic time using Set.elemAt.

I don't think that breaks any abstractions, but they do seem like very weird functions to have. Something that I might consider potentially useful function would be a variant of splitAt, so that you could split a set using a fixed ratio (e.g., "splitAt (Set.size set `div` 2) set").

splitAt index set = split (elemAt index set) set would work reasonably well. It traverses the tree twice, but the first traversal is very fast. Cheers, Milan