Re: sorted-set-by drops elements
Here's the source for sorted-set-by:
(defn sorted-set-by
Returns a new sorted set with supplied keys, using the supplied
comparator.
([comparator keys]
(clojure.lang.PersistentTreeSet/create comparator keys)))
This is because your comparator is saying that everything is equal.
PersistentTreeSet delegates a lot of work to PersistentTreeMap, so the
object is happily replacing every element when the comparator is zero.
I'm not sure if this is a bug or the intended behavior... I'm leaning
toward the latter, even though it's confusing.
Sean
On Apr 16, 8:25 am, Razvan gigi.clan...@gmail.com wrote:
Hi,
Is this the intended behavior?
(sorted-set-by (constantly 0) 1 2 3 4) returns #{1}.
I would expect the set to contain all the elements, and the comparator
to only affect sort order.
Razvan
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group
athttp://groups.google.com/group/clojure?hl=en
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
Re: sorted-set-by drops elements
It doesn't seem confusing to me. You are taking complete control of
the set's local notion of ordering and equality. This is what I'd
expect.
Here's an example. First, a handy little function from Haskell:
(defn on [key f]
#(apply f (map key %)))
Then:
user (sorted-set-by (on :id compare)
{:id 42 :name Per :age 28}
{:id 0 :name Methuselah :age 9000}
{:id 42 :name Rep :age 82})
#{{:id 0, :name Methuselah, :age 9000} {:id 42, :name Per, :age 28}}
That is, it's eliminating entries with duplicate primary keys in favor
of earlier occurrences.
-Per
On Fri, Apr 16, 2010 at 9:38 PM, Sean Devlin francoisdev...@gmail.com wrote:
Here's the source for sorted-set-by:
(defn sorted-set-by
Returns a new sorted set with supplied keys, using the supplied
comparator.
([comparator keys]
(clojure.lang.PersistentTreeSet/create comparator keys)))
This is because your comparator is saying that everything is equal.
PersistentTreeSet delegates a lot of work to PersistentTreeMap, so the
object is happily replacing every element when the comparator is zero.
I'm not sure if this is a bug or the intended behavior... I'm leaning
toward the latter, even though it's confusing.
Sean
On Apr 16, 8:25 am, Razvan gigi.clan...@gmail.com wrote:
Hi,
Is this the intended behavior?
(sorted-set-by (constantly 0) 1 2 3 4) returns #{1}.
I would expect the set to contain all the elements, and the comparator
to only affect sort order.
Razvan
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group
athttp://groups.google.com/group/clojure?hl=en
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
Re: sorted-set-by drops elements
Why should sorting be related to the primary key? You should be able to sort on any attribute. If you wanted to sort a set of people by age would it make sense to only retain one person of each age? Sort order and identity should be orthogonal. Besides, if you need a collection based on primary keys then a map or a sorted map is more appropriate, and if you chose a set instead you probably expect operations on that set to take into account the entire element. Raz -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: sorted-set-by drops elements
Maybe the example was poorly picked but the point stands: if you're asking for a sorted set based on a comparator, you should expect duplicate elements as dictated by comparator to be eliminated. If you wanted to sort a set of people by age, you wouldn't use a sorted set but a sorted sequence. That is what sort/sort-by provides. -Per On Fri, Apr 16, 2010 at 10:45 PM, Razvan gigi.clan...@gmail.com wrote: Why should sorting be related to the primary key? You should be able to sort on any attribute. If you wanted to sort a set of people by age would it make sense to only retain one person of each age? Sort order and identity should be orthogonal. Besides, if you need a collection based on primary keys then a map or a sorted map is more appropriate, and if you chose a set instead you probably expect operations on that set to take into account the entire element. Raz -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: sorted-set-by drops elements
I think the fns you're interested in are sort and sort-by, not sorted- set-by. I know you might not like it, but there is a convention in JavaLand that a comparator value of 0 is identical in a sorted collection. This causes orthogonal concepts of order identity to be entwined. Sean On Apr 16, 11:45 am, Razvan gigi.clan...@gmail.com wrote: Why should sorting be related to the primary key? You should be able to sort on any attribute. If you wanted to sort a set of people by age would it make sense to only retain one person of each age? Sort order and identity should be orthogonal. Besides, if you need a collection based on primary keys then a map or a sorted map is more appropriate, and if you chose a set instead you probably expect operations on that set to take into account the entire element. Raz -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group athttp://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: sorted-set-by drops elements
CORRECTION, DON'T SHOOT!! I should have order value, not order identity. On Apr 16, 1:01 pm, Sean Devlin francoisdev...@gmail.com wrote: I think the fns you're interested in are sort and sort-by, not sorted- set-by. I know you might not like it, but there is a convention in JavaLand that a comparator value of 0 is identical in a sorted collection. This causes orthogonal concepts of order identity to be entwined. Sean On Apr 16, 11:45 am, Razvan gigi.clan...@gmail.com wrote: Why should sorting be related to the primary key? You should be able to sort on any attribute. If you wanted to sort a set of people by age would it make sense to only retain one person of each age? Sort order and identity should be orthogonal. Besides, if you need a collection based on primary keys then a map or a sorted map is more appropriate, and if you chose a set instead you probably expect operations on that set to take into account the entire element. Raz -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group athttp://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group athttp://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: sorted-set-by drops elements
On Sat, Apr 17, 2010 at 12:01 AM, Sean Devlin francoisdev...@gmail.com wrote: I know you might not like it, but there is a convention in JavaLand that a comparator value of 0 is identical in a sorted collection. It's not a Java convention. It's intrinsic to the business of sorting. For sorting to give well-defined results, it must be based on an ordering that respects the trichotomy law, which says that, for all x and y, exactly one of the following three conditions must hold: x y, x = y, x y. If you define the and based on a custom comparator but use the default equality implementation for the = then you cannot expect this to hold. Packaging all three relations together lets the implementor of the comparator guarantee trichotomy. -Per -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: sorted-set-by drops elements
The problem is you're unnecessarily conflating the value by which to base a sort (x and y in your example) with the elements of the set. Equality and ordinality are not the same thing. It should be perfectly reasonable to hand someone a set of unique objects sorted by some non-unique attribute of the elements of the set. On Apr 16, 10:13 am, Per Vognsen per.vogn...@gmail.com wrote: On Sat, Apr 17, 2010 at 12:01 AM, Sean Devlin francoisdev...@gmail.com wrote: I know you might not like it, but there is a convention in JavaLand that a comparator value of 0 is identical in a sorted collection. It's not a Java convention. It's intrinsic to the business of sorting. For sorting to give well-defined results, it must be based on an ordering that respects the trichotomy law, which says that, for all x and y, exactly one of the following three conditions must hold: x y, x = y, x y. If you define the and based on a custom comparator but use the default equality implementation for the = then you cannot expect this to hold. Packaging all three relations together lets the implementor of the comparator guarantee trichotomy. -Per -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group athttp://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: sorted-set-by drops elements
Equality and ordinality are not the same thing. It should be perfectly reasonable to hand someone a set of unique objects sorted by some non-unique attribute of the elements of the set. Sure, it's perfectly reasonable but it implies a different data structure. It sounds like you want a data structure that is both a set with respect to its default notion of equality (and hashing) and a sorted sequence with respect to some custom ordering. That implies two data structures, not one. If your tree is constructed based on the custom ordering, then you cannot use the same tree for fast lookups based on the default notion of equality. You can only do slow linear-time lookups by traversing the tree's nodes exhaustively. -Per -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: sorted-set-by drops elements
On Sat, Apr 17, 2010 at 1:05 AM, Per Vognsen per.vogn...@gmail.com wrote: You can only do slow linear-time lookups by traversing the tree's nodes exhaustively. Correction: You do not have to do a linear search on the whole tree but only on the subset of the tree for which the comparator returns 0 with your queried value. That is the whole tree in the worst case and a significant fraction of the whole tree in many practical cases. Let's say the tree is constructed based on age and you're searching a university database for some specific person aged 18. The span of ages among university students is small, so a logarithmic search of the age-based tree probably only reduces the total search space by a fourth. Even with the help of the tree, you're still left to linear search n/4 elements. -Per -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: sorted-set-by drops elements
On Apr 16, 8:25 am, Razvan gigi.clan...@gmail.com wrote:
Hi,
Is this the intended behavior?
(sorted-set-by (constantly 0) 1 2 3 4) returns #{1}.
I would expect the set to contain all the elements, and the comparator
to only affect sort order.
I expected the same thing at first, but the behavior appears to be
consistent with Java collections, so it's probably intended:
user= (def s (java.util.TreeSet. (proxy [java.util.Comparator] []
(compare [a b] 0
#'user/s
user= s
#TreeSet []
user= (seq s)
nil
user= (.add s 1)
true
user= s
#TreeSet [1]
user= (.add s 2)
false
user= s
#TreeSet [1]
- Chris Perkins
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
