No way to retrieve the base of a Set or Map in O(1)

Hello, there seems to be no way to retrieve the base of a Set or Map in O(1), since there is no relevant function in the respective libraries and the constructors Bin and Tip are not exported in any module. I think retrieving any one element from a Set or Map might be useful sometimes, so I modestly ask for an implementation. I see that there is splitRoot, but the docs advice, not to rely on the current form of the resulting list, since it might be subject to change. Having this function, with its current result, it might be interesting to be able to efficiently build the union of the lower and the upper parts by simply connecting the trees at their bases. What do you think? Kind regards, André

On 18 June 2015 at 20:27, André van Delden
Hello,
there seems to be no way to retrieve the base of a Set or Map in O(1), since there is no relevant function in the respective libraries and the constructors Bin and Tip are not exported in any module. I think retrieving any one element from a Set or Map might be useful sometimes, so I modestly ask for an implementation.
For Set there's minView and maxView. For Map there's both {min,max}View (which returns only the value) and also {min,max}ViewWithKey which also returns the key. These are admittedly all O(log n) though. I suppose the reason for there being no way to obtain the root value is that it would be both implementation and creation (as in how the Set/Map was created, due to there being no balancing IIRC) dependent, and thus difficult to use in any reliable/reproducible fashion. -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

Hi André,
-----Original message----- From: André van Delden
Sent: 18 Jun 2015, 12:27 there seems to be no way to retrieve the base of a Set or Map in O(1), since there is no relevant function in the respective libraries and the constructors Bin and Tip are not exported in any module. I think retrieving any one element from a Set or Map might be useful sometimes, so I modestly ask for an implementation.
do you have any use-case where such function is useful? I am having troubles imagining one. Also note that for IntMap and IntSet you cannot provide such function. To me, this seems more like accessing the internal representation. There have been some discussions about exporting the internal representations in an Unsafe module, which would have no API guarantees (i.e., have Data.Set.Unsafe exporting the Set constructor). Do you really want the proposed function, or would you be more interested in accessing the internal representation? Cheers, Milan

On 18 June 2015 at 21:01, Milan Straka
do you have any use-case where such function is useful? I am having troubles imagining one.
In fgl we need to be able to obtain a "random" value for the matchAny function, which currently uses minView. I wouldn't mind an O(1) variant for both both Map and IntMap, but minView works well enough. -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

Hello,
do you have any use-case where such function is useful?
I am trying to generalize some combinatorial functions to a class of types containing any sort of element. For many combinatorial functions it is useful to split the elements at some element and recombine them after a recursion over the parts. That's what I was thinking of. But others seem to be interested aswell (although it is a beginner asking, so there might be a better solution to his problem): http://osdir.com/ml/beginners@haskell.org/2015-03/msg00091.html Kind regards, André

On 18 June 2015 at 22:53, André van Delden
Hello,
do you have any use-case where such function is useful?
I am trying to generalize some combinatorial functions to a class of types containing any sort of element. For many combinatorial functions it is useful to split the elements at some element and recombine them after a recursion over the parts. That's what I was thinking of.
But others seem to be interested aswell (although it is a beginner asking, so there might be a better solution to his problem):
http://osdir.com/ml/beginners@haskell.org/2015-03/msg00091.html
minView applies to that one as well. -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com
participants (3)
-
André van Delden
-
Ivan Lazar Miljenovic
-
Milan Straka