3

I'm wondering why there is no sortBy method on Scala Set as there is for Seq or List since it extends Iterable as well...

Simon
  • 6,025
  • 7
  • 46
  • 98
  • 1
    Please note that `Iterable` doesn't imply order, just that one can go through all elements. – Josep Prat Jan 20 '17 at 11:11
  • 1
    @JosepPrat There is a difference between ordered and sorted: http://stackoverflow.com/questions/1084146/what-is-the-difference-between-an-ordered-and-a-sorted-collection – Pablo Lozano Jan 20 '17 at 11:13
  • 1
    Well, as the answer you are linking says, sorted can only happen if there is order, so the comment is perfectly valid – Josep Prat Jan 20 '17 at 11:22

1 Answers1

4

A Set is a somewhat ordered (that's why it is Iterable) but not-sorted collection of elements. If you want the elements to be sorted, you must use a SortedSet implementation (TreeSet), where you can provide the ordering when creating a new instance

Update: The difference between ordered and sorted is not really clear: You can say a List is ordered but may be not sorted and a Map is unordered and unsorted, but the implementation of a Map requires to keep its elements in memory (RAM, disk, whatever support you want) and that memory is always ordered, so it gives some order to any Collection (for example the insertion order or the storage order).

An example of this undefinition can be seen in the Scala API: When defining a SortedSet, the constructor is:

new TreeSet()(implicit ordering: Ordering[A])

So the word "ordering" is used instead of "sorting"

Pablo Lozano
  • 10,122
  • 2
  • 38
  • 59
  • Any reason why it not sorted? – Simon Jan 20 '17 at 11:19
  • Hash tables are not ordered by their nature. And being iterable doesn't mean that it's ordered (since order in which you add elements can make difference in order in which it's iterated). – adamwy Jan 20 '17 at 11:25
  • @Simon I guess because the mathematical concept of Set is not sorted, the elements within have no hierarchy – Pablo Lozano Jan 20 '17 at 11:28
  • @adamwy You can see a Map as a Set of Key-Value pairs (entries), that's why you can iterate on them – Pablo Lozano Jan 20 '17 at 11:31
  • @Pablo How do you define the order of a Map? – adamwy Jan 20 '17 at 11:33
  • 2
    Also it's the other way around - Set is a kind of Map (you can define it as `type Set[T] = Map[T, Unit]`). Map guarantees that there are no two values associated with the same key (which is possible for multimaps), but in a set of tuples you can have two pairs with the same key. – adamwy Jan 20 '17 at 11:37
  • 1
    You could say that hash table is ordered by both order in which elements are added and their hash codes, so indeed order in which it will be iterated is deterministic, but its not a very useful information, since it's extremely hard to predict this order. Usually saying that something is ordered is meant to have some practical meaning like how you will iterate its elements later. – adamwy Jan 20 '17 at 11:49