On 29 April 2011 15:33, Luis Casillas wrote:

El abr 28, 2011, a las 9:16 p.m., Ivan Lazar Miljenovic escribió:

...

On 29 April 2011 14:08, Luis Casillas wrote:

...

2. Concern that Int-based indexing breaks the set abstraction by exposing a specific ordering (Trac comment by Malcolm Wallace).  My assumption when I decided to submit this patch was that if it's OK for Data.Map to have these operations, then it should also be ok for Data.Set to have them.  But Malcolm's concern makes me wonder if some people will find the original Data.Map functions objectionable and dislike the idea of "spreading the infection" to Data.Set.

I think I agree with Malcolm here; the internals of Data.Set shouldn't be revealed IMHO.

Would either of the following modifications make the proposal more palatable?

1. Stressing in the functions' documentation that the assignment of Ints does not have to reflect the order of the elements.  The examples would also be rewritten not to make any ordering assumptions.

2. Modifying the implementation to scramble the order of the indexes relative to the order of the set elements.  This would discourage people from implicitly coding to the element order.

I'm not at all committed to having the order of the indexes reflect the order of the set members or any specific internal property of the set implementation.  I'm happy with any one-to-one, reversible mapping between sets and Ints in the range [0..(size-1)].  I'm also happy if the mapping changes between library versions (or heck, even between different invocations of the same program).

Well, before we talk about modifications, etc.: is there a _need_ for this kind of indexing in a Set? -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

On 29 April 2011 16:08, Luis Casillas wrote:

El abr 28, 2011, a las 10:42 p.m., Ivan Lazar Miljenovic escribió:

...

Well, before we talk about modifications, etc.: is there a _need_ for this kind of indexing in a Set?

Well, to take a step back, the reasoning that led me to make this proposal is really no better than this:

1. Map already has analogues to the Set functions I'm proposing. 2. There is some good reason why Map should have those functions. 3. Whatever reason that is, it also applies to Set. 4. Ergo, Set should have these functions.

It looks to me like you disagree with (2) or (3), and you're the second person to do so (out of three who have responded so far).  If the majority of responses turn out like this, well, then the case for my proposal is just not as strong as I assumed it would be.

Actually, I primarily disagree with 2) ;-) Maybe we need an alternate proposal: remove index-based functions from Data.Map... -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

On Fri, Apr 29, 2011 at 11:34:33AM +0200, Balazs Komuves wrote:

Isn't for example "elemAt k someMapOrSet" equivalent (but much faster) to "(toList someMapOrSet) !! k",

+1 (If this specification (probably better with toAscList) is not documented, it should be.)

and similarly for all the other index functions? So how does it break any abstraction?

While I have to agree (referring to the old discussion) that the Map/Set API is far from perfect, I'm much more in favour of exposing efficient functionality than removing useful stuff...

+1 Wolfram

On Fri, Apr 29, 2011 at 1:42 AM, Ivan Lazar Miljenovic wrote:

On 29 April 2011 15:33, Luis Casillas wrote:

...

El abr 28, 2011, a las 9:16 p.m., Ivan Lazar Miljenovic escribió:

...

On 29 April 2011 14:08, Luis Casillas wrote:

...

2. Concern that Int-based indexing breaks the set abstraction by exposing a specific ordering (Trac comment by Malcolm Wallace).  My assumption when I decided to submit this patch was that if it's OK for Data.Map to have these operations, then it should also be ok for Data.Set to have them.  But Malcolm's concern makes me wonder if some people will find the original Data.Map functions objectionable and dislike the idea of "spreading the infection" to Data.Set.

I think I agree with Malcolm here; the internals of Data.Set shouldn't be revealed IMHO.

Would either of the following modifications make the proposal more palatable?

1. Stressing in the functions' documentation that the assignment of Ints does not have to reflect the order of the elements.  The examples would also be rewritten not to make any ordering assumptions.

2. Modifying the implementation to scramble the order of the indexes relative to the order of the set elements.  This would discourage people from implicitly coding to the element order. ...

Well, before we talk about modifications, etc.: is there a _need_ for this kind of indexing in a Set?

I believe there is not. Moreover, in order to realize efficient Int indexing, we need to commit a word of storage to hold subtree size on every interior tree node in Data.Map, Data.Set, Data.IntSet, and Data.IntMap. Without extra interior storage, these tree indexing and list indexing are comparably slow (O(n)). My understanding is these functions were included in Data.Map *because we could*: the implementation uses size-balanced trees, so the tree size had to be kept at each node for balancing purposes, and therefore it was easy to implement indexing. As a happy side effect, this also makes it easy to maintain O(1) size information. However, indexing precludes the use of implementations that *don't* cache subtree sizes on a large fraction of interior nodes (it is already a bad match for IntSet and IntMap). There are other techniques for making size O(1) without imposing per-node overhead, if that is desired. It would be a shame to rule out alternative implementations in order to support an API that nobody needs. I'd support removing these functions absent a compelling use case (ie one that would not be better expressed as indexing by key). Does anyone have one? -Jan-Willem Maessen

El abr 29, 2011, a las 8:05 a.m., Jan-Willem Maessen escribió:

I'd support removing these functions absent a compelling use case (ie one that would not be better expressed as indexing by key). Does anyone have one?

Well, I have a use case for these functions in the case of Set. I'm a bit wary of arguing for the inclusion on nothing but my personal use case, because as I mentioned in another message, I just assumed that desirability of such functions functions in Data.Map would be uncontroversial. I.e., when it comes to modifying the interface of a standard library, I think arguments like "make it uniform with Data.Map" are more persuasive than "I could use it for this." At this point, I'm slowly being convinced that the original Data.Map functions are extraneous. Still, I will mention my use case for the Data.Set functions, and let people make up their own minds. I'm working on a project where the most natural implementation is to use the members of runtime-constructed sets to index the elements of an array. The use of sets to represent the index sets is independently motivated, because I need to operate on these sets using operations like union, intersection, difference, mapping and filtering, while preserving the member uniqueness property. The lookupIndex, findIndex and elemAt functions would give me this set member/array index translation "for free." There are other ways to construct such a mapping, but I think they suffer in comparison: 1. I could construct a Map assigning an index to each element, but then the inverse mapping is linear time. 2. That could be solved by using a pair of maps (one from elem to Int, and an inverse map from Int to elem), but since I fundamentally just want to treat these maps as sets, I need to implement analogues of basic Set operations like union, intersection, difference, map, filter and so on, that would need to reconstruct the element <--> index mappings as needed. I realize that this is not difficult at all, but (a) it's presumably slower, (b) again, I mistakenly assumed that the Data.Map index functions were uncontroversial to start with. 3. An alternative would be to implement and use a data type that guaranteed uniqueness, ordering, Int indexing and the usual set operations. You might call such a type or class OrderedSet or IndexedSet; but to implement it, you might end up just copy-pasting Data.Set + the indexing functions as the implementation, because the implementation in Data.Set sure looks like a natural way of implementing an ordered, indexed set. I think this really distills the issue down to this. There is a family of three potential, related abstractions: plain set / \ / \ ordered set indexed set A plain set just provides uniqueness. An ordered set provides uniqueness and preserves some ordering predicate on the elements. An indexed set assigns a unique Int index in the range [0..size-1] to each element, and provides translation between members and indexes. The Set module provides an implementation of an efficient ordered set, that can easily be extended to also be an indexed set. But many people think that "plain set" should be the only contract that Data.Set is bound to implement. I can't say that I disagree with that--but I also just want indexed sets... A more ambitious proposal would be this: 1. Introduce classes to represent the three abstractions in question. 2. Have Data.Set be an instance of all three. 3. Don't expose the ordered an indexed operations directly from Data.Set; force the users to go through the appropriate class. This allows flexibility for Data.Set to later switch to an implementation that doesn't provide order or indexes; the original implementation would have to be kept as an alternative for people who want the extra features. This is a lot more ambitious of a proposal than I was hoping for my first time around, I will say.

On 4/29/11 12:30 PM, Luis Casillas wrote:

I think this really distills the issue down to this. There is a family of three potential, related abstractions:

plain set / \ / \ ordered set indexed set

A plain set just provides uniqueness. An ordered set provides uniqueness and preserves some ordering predicate on the elements. An indexed set assigns a unique Int index in the range [0..size-1] to each element, and provides translation between members and indexes.

The Set module provides an implementation of an efficient ordered set, that can easily be extended to also be an indexed set. But many people think that "plain set" should be the only contract that Data.Set is bound to implement. I can't say that I disagree with that--but I also just want indexed sets...

So why not just implement your "set" with a map from elements to their indices? Maps maintain uniqueness of keys, and Data.Map maintains ordering too. It wouldn't be as clean as the proposed functions, but from your description of the problem, it's not clear to me that using sets of proxies for array indices is really the cleanest approach in the first place. -- Live well, ~wren

On 4/29/11 1:33 AM, Luis Casillas wrote:

I'm not at all committed to having the order of the indexes reflect the order of the set members or any specific internal property of the set implementation. I'm happy with any one-to-one, reversible mapping between sets and Ints in the range [0..(size-1)]. I'm also happy if the mapping changes between library versions (or heck, even between different invocations of the same program).

It sounds like what you want is an intern table. That's a pretty common need, though not something I think ought to be pushed onto Data.{Set,Map}. In part because the needs for intern tables can vary by application, so there's no single implementation for everyone. A simple intern table can be done by: module Intern (Intern(), empty, intern, extern) where import qualified Data.Map as M import qualified Data.IntMap as IM data Intern a = Intern { int2elem :: IM.IntMap a , elem2int :: M.Map a Int , nextInt :: !Int } empty = Intern IM.empty M.empty minBound intern a self@(Intern i2a a2i n) = case M.lookup a a2i of Just i -> Just (i, self) Nothing | n == maxBound -> Nothing | otherwise -> Just (n, Intern (IM.insert n a i2a) (M.insert a n a2i) (n+1)) extern i (Intern i2a a2i n) = IM.lookup i i2a Though it should be easy to see the room for variation. E.g., * sometimes you want to store the highest used key, other times the lowest unused key is more useful. * sometimes you want to allow for invalidating old keys. * sometimes you want to allow for recycling old keys ala garbage collection. * generally the key type should be abstract instead of an Int; but how abstract is "abstract"? * sometimes it's helpful to know whether the key returned by 'intern' is freshly allocated or not. * sometimes you'd be better off using Data.HashMap instead of Data.Map; sometimes you'd be better off with a hash-consing trie. ... -- Live well, ~wren

On Fri, Apr 29, 2011 at 10:44 AM, Antoine Latter wrote:

...

Hi everybody. First time proposer here, so bear with me.

While I was looking at the Haddock documentation for Data.Map, I noticed

On Thu, Apr 28, 2011 at 11:08 PM, Luis Casillas wrote: that it has a section with "Indexed" operations that address the map with Int indexes:

...

http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Map.ht...

...

The relevant functions' signatures are these:

lookupIndex :: Ord k => k -> Map k a -> Maybe Int findIndex :: Ord k => k -> Map k a -> Int elemAt :: Int -> Map k a -> (k, a) updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a deleteAt :: Int -> Map k a -> Map k a

Now, the Data.Set module, which is a near carbon-copy of Data.Map, does

not have any counterparts to these functions. My proposal is to add such counterparts to Data.Set (I'm writing some code that could benefit from them). The proposed functions' signatures:

...

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

I attach a patch to add these to Data.Set. Note that the implementation

of the Set functions is basically a copy-paste-and-edit of their counterparts in Data.Map. That seems to be the convention in those two modules; Data.Set is really just like Data.Map but with no "value" field in the datatype's constructor.

...

Since I am a noob, I mistakenly created a Trac ticket before figuring out

the correct library proposal process (#5162, which promptly got closed; my apologies). There have been a couple of responses there, which I will summarize here:

...

1. Concern over the efficiency of the code in my patch (Trac comment by

tibbe). At my present skill level with Haskell, frankly, the most intelligent response I can give to this is that I'm copying the Data.Map implementation from darcs to the best of my ability, and that the most I hope is to make the Set versions no worse than the Map versions.

...

2. Concern that Int-based indexing breaks the set abstraction by exposing

a specific ordering (Trac comment by Malcolm Wallace). My assumption when I decided to submit this patch was that if it's OK for Data.Map to have these operations, then it should also be ok for Data.Set to have them. But Malcolm's concern makes me wonder if some people will find the original Data.Map functions objectionable and dislike the idea of "spreading the infection" to Data.Set.

...

Discussion period: 2 weeks.

These functions are also missing from IntSet and IntMap.

Assuming that there is a use case for such a family of indexing functions, it seems like they should be added to these as well.

However if we don't have folks that want to use these functions for sets or IntMaps, I don't think we should add them.

IntMap and IntSet do not provide efficient size operations -- they have very different asymptotics than Map and Set in this regard, O(n) vs O(1). This makes the requested operations quite uselessly expensive there. While I don't like the existence of the Int indexed Map operations in the first place, I'm hardly swayed by an argument that boils down to claiming that because nobody seems to want to port them to a largely unrelated but unsuitable data structure, we shouldn't implement them on another data structure where they _can_ be efficiently implemented. -Edward

On Apr 29, 2011, at 11:53 AM, Gwern Branwen wrote:

On Fri, Apr 29, 2011 at 12:08 AM, Luis Casillas wrote:

...

updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a

I took a look at all my local repos (c.h.o, Patch-tag, misc repos, and GitHub since I recently re-ran http://www.gwern.net/haskell/Archiving%20GitHub.html ).

A grep* for updateAt (randomly picked one whose name looked like it'd be fairly unique) turned up what seems to be very few actual uses of updateAt, and mostly similarly named functions and various implementations of updateAt.

Thanks Gwern. For the record, though, my patch doesn't add a Set.updateAt operation, because it just didn't make sense. Map.updateAt is about updating the *value* that a key is mapped to, but the elements of a set correspond to the keys of a map.