why doesn't TraversableOnce have sortBy,sorted,sortWith

Sorting is less efficient if one does not know the length of the collection, and TraversableOnce doesn't know its length without traversing (and since it's TraversableOnce it can't do it again).

It would of course be possible to store the results internally, but since that's going to be essentially the same as doing a toSeq, it makes sense to me to alert the coder to the fact that they have to make a temporary copy before they can sort it.

Or, alternatively, one could implement a merge sort that consumed the data in a single pass.  Right now, the sorting is ultimately done by Java.  Writing a really highly optimized sort is hard work, which is why using Java is attractive.

  --Rex

On Thu, Oct 28, 2010 at 1:23 PM, Ittay Dror <ittay.dror@gmail.com> wrote:

It seems all required methods are there. This will allow Iterator and Iterable to have sorting without needig to first do toSeq

Rex Kerr wrote:

E_JKaW8R66xQS2xw [at] mail [dot] gmail [dot] com" type="cite">Sorting is less efficient if one does not know the length of the collection, and TraversableOnce doesn't know its length without traversing (and since it's TraversableOnce it can't do it again).

This is the current implementation:

  def sorted[B >: A](implicit ord: Ordering[B]): Repr = {
    val arr = new ArraySeq[A](this.length)
    var i = 0
    for (x <- this) {
      arr(i) = x
      i += 1
    }
    java.util.Arrays.sort(arr.array, ord.asInstanceOf[Ordering[Object]])
    val b = newBuilder
    b.sizeHint(this)
    for (x <- arr) b += x
    b.result
  }


so except of allocating the array at the right length at first, the length is not used

E_JKaW8R66xQS2xw [at] mail [dot] gmail [dot] com" type="cite">
It would of course be possible to store the results internally, but since that's going to be essentially the same as doing a toSeq, it makes sense to me to alert the coder to the fact that they have to make a temporary copy before they can sort it.

as you can see from the implementation, a copy is made anyways.

and why is a copy necessary? all there needs to be is to add elements to a sorted collection (SortedSeq or something like that) that sorts the elements as they are added and this is the collection that is returned

E_JKaW8R66xQS2xw [at] mail [dot] gmail [dot] com" type="cite">
Or, alternatively, one could implement a merge sort that consumed the data in a single pass.  Right now, the sorting is ultimately done by Java.  Writing a really highly optimized sort is hard work, which is why using Java is attractive.

  --Rex

On Thu, Oct 28, 2010 at 1:23 PM, Ittay Dror <ittay [dot] dror [at] gmail [dot] com" rel="nofollow">ittay.dror@gmail.com> wrote:

It seems all required methods are there. This will allow Iterator and Iterable to have sorting without needig to first do toSeq

A Set is a TraversableOnce. Is it meaningful to sort a set? So is a Map. Does it make sense to sort a Map? What about HashSet/HashMap, which are the default implementations?

There is one kind of collection where you can prepend or append an element, and _know_ that element will appear in that order: Seq and its descendants.

On Thu, Oct 28, 2010 at 15:23, Ittay Dror <ittay.dror@gmail.com> wrote:

It seems all required methods are there. This will allow Iterator and Iterable to have sorting without needig to first do toSeq

--
Daniel C. Sobral

I travel to the future all the time.

Daniel Sobral wrote:

AANLkTik9kuyaX-NaGeVVZoWXtjZ-bftkSez4-6i_eRcZ [at] mail [dot] gmail [dot] com" type="cite">A Set is a TraversableOnce. Is it meaningful to sort a set? So is a Map. Does it make sense to sort a Map? What about HashSet/HashMap, which are the default implementations?

sure. Set(2,3,1).sorted => Seq(1,2,3)

what's the problem with that?

I'm not saying that the return value be Set, just that the method will be available there

ittay

AANLkTik9kuyaX-NaGeVVZoWXtjZ-bftkSez4-6i_eRcZ [at] mail [dot] gmail [dot] com" type="cite">
There is one kind of collection where you can prepend or append an element, and _know_ that element will appear in that order: Seq and its descendants.

On Thu, Oct 28, 2010 at 15:23, Ittay Dror <ittay [dot] dror [at] gmail [dot] com" rel="nofollow">ittay.dror@gmail.com> wrote:

It seems all required methods are there. This will allow Iterator and Iterable to have sorting without needig to first do toSeq

--
Daniel C. Sobral

I travel to the future all the time.

There's no difference between those two sets.

On 29 Oct 2010 07:28, "Ittay Dror" <ittay.dror@gmail.com> wrote:
>
>
> Daniel Sobral wrote:
>> A Set is a TraversableOnce. Is it meaningful to sort a set? So is a Map. Does it make sense to sort a Map? What about HashSet/HashMap, which are the default implementations?
> sure. Set(2,3,1).sorted => Seq(1,2,3)
>
> what's the problem with that?
>
> I'm not saying that the return value be Set, just that the method will be available there
>
> ittay
>>
>> There is one kind of collection where you can prepend or append an element, and _know_ that element will appear in that order: Seq and its descendants.
>>
>> On Thu, Oct 28, 2010 at 15:23, Ittay Dror <ittay.dror@gmail.com <mailto:ittay.dror@gmail.com>> wrote:
>>
>>
>>
>> It seems all required methods are there. This will allow Iterator and Iterable to have sorting without needig to first do toSeq
>>
>>
>>
>>
>> --
>> Daniel C. Sobral
>>
>> I travel to the future all the time.

Sorry, disregard my response.

On 29 Oct 2010 07:50, "David Flemström" <david.flemstrom@gmail.com> wrote:
> There's no difference between those two sets.
> On 29 Oct 2010 07:28, "Ittay Dror" <ittay.dror@gmail.com> wrote:
>>
>>
>> Daniel Sobral wrote:
>>> A Set is a TraversableOnce. Is it meaningful to sort a set? So is a Map.
> Does it make sense to sort a Map? What about HashSet/HashMap, which are the
> default implementations?
>> sure. Set(2,3,1).sorted => Seq(1,2,3)
>>
>> what's the problem with that?
>>
>> I'm not saying that the return value be Set, just that the method will be
> available there
>>
>> ittay
>>>
>>> There is one kind of collection where you can prepend or append an
> element, and _know_ that element will appear in that order: Seq and its
> descendants.
>>>
>>> On Thu, Oct 28, 2010 at 15:23, Ittay Dror <ittay.dror@gmail.com <mailto:
> ittay.dror@gmail.com>> wrote:
>>>
>>>
>>>
>>> It seems all required methods are there. This will allow Iterator and
> Iterable to have sorting without needig to first do toSeq
>>>
>>>
>>>
>>>
>>> --
>>> Daniel C. Sobral
>>>
>>> I travel to the future all the time.

On Fri, Oct 29, 2010 at 07:17:22AM +0200, Ittay Dror wrote:
> sure. Set(2,3,1).sorted => Seq(1,2,3)
>
> what's the problem with that?

All of the collections can be converted to one another. Why don't we
put all the methods in all of them? If you can answer that, you can
answer this. Converting a set to a sequence and sorting a sequence
involves two distinct operations. There are many, many ways to make two
operations feel like one on your end. (In fact you can put all the
collections methods on all the collections with a tiny handful of
implicits if that is your wont.)

If you are not persuaded that the collections should try to keep
distinct operations distinct and leave you to do the blending, there is
also a technical problem.

def sorted[B >: A](implicit ord: Ordering[B]): Repr

Like many other collections methods, it returns a collection of the same
type. That makes it rather hostile to types which are unordered. You
don't want to start proposing workarounds to this without implementing
them and discovering how the moving parts grind against one another.

Paul Phillips wrote:
> On Fri, Oct 29, 2010 at 07:17:22AM +0200, Ittay Dror wrote:
>> sure. Set(2,3,1).sorted => Seq(1,2,3)
>>
>> what's the problem with that?
> All of the collections can be converted to one another. Why don't we
> put all the methods in all of them? If you can answer that, you can
> answer this. Converting a set to a sequence and sorting a sequence
> involves two distinct operations. There are many, many ways to make two
> operations feel like one on your end. (In fact you can put all the
> collections methods on all the collections with a tiny handful of
> implicits if that is your wont.)

here's the pseudo code for an efficient sort:

def sorted(...) {
var sortedSeq = new SortedSeq
for (x <- this)
sortedSeq += x

sortedSeq
}

of course one can also create a mechanism similar to CanBuildFrom so sorting a List will return a List.

notice one collection is created.

my option today is
iterator.toSeq.sorted

which creates two collections: first conversion of the iterator to Seq, then sorting the seq, returning a new collection.

> If you are not persuaded that the collections should try to keep
> distinct operations distinct and leave you to do the blending, there is
> also a technical problem.
>
> def sorted[B>: A](implicit ord: Ordering[B]): Repr
>
> Like many other collections methods, it returns a collection of the same
> type. That makes it rather hostile to types which are unordered. You
> don't want to start proposing workarounds to this without implementing
> them and discovering how the moving parts grind against one another.
Of course, it will require something like CanBuildSortedFrom kind of mechanism.

I understand this is not a "move method from here to there" kind of effort. And of course I'm not demanding anyone to do it. Rather the opposite, I assumed that there were deeper reasons and wanted to understand why

Sorry if it created bad feelings. I'm at awe of what was accomplished by the Scala team and enjoy every time I use its collections.

Ittay

On Fri, Oct 29, 2010 at 5:35 PM, Ittay Dror wrote:
> here's the pseudo code for an efficient sort:
>
> def sorted(...) {
>   var sortedSeq = new SortedSeq
>   for (x <- this)
>     sortedSeq += x
>
>  sortedSeq
> }

That is not the recipe for an efficient sort. Sorted collections are
generally less efficient than if you do a one-time sort (using a good
sort algorithm) on an array.

Best,
Ismael

Ismael Juma wrote:
> On Fri, Oct 29, 2010 at 5:35 PM, Ittay Dror wrote:
>> here's the pseudo code for an efficient sort:
>>
>> def sorted(...) {
>> var sortedSeq = new SortedSeq
>> for (x<- this)
>> sortedSeq += x
>>
>> sortedSeq
>> }
> That is not the recipe for an efficient sort. Sorted collections are
> generally less efficient than if you do a one-time sort (using a good
> sort algorithm) on an array.
sure. you'd still need to create the array regardless of whether the underlying container is a Seq or just Traversable.
> Best,
> Ismael

Why? It is entirely correct.
Set(2, 1, 3) == Set(1, 2, 3) // trueList(2, 1, 3) == List(1, 2, 3) // false

On Fri, Oct 29, 2010 at 03:51, David Flemström <david.flemstrom@gmail.com> wrote:

Sorry, disregard my response.

On 29 Oct 2010 07:50, "David Flemström" <david.flemstrom@gmail.com> wrote:
> There's no difference between those two sets.
> On 29 Oct 2010 07:28, "Ittay Dror" <ittay.dror@gmail.com> wrote:
>>
>>
>> Daniel Sobral wrote:
>>> A Set is a TraversableOnce. Is it meaningful to sort a set? So is a Map.
> Does it make sense to sort a Map? What about HashSet/HashMap, which are the
> default implementations?
>> sure. Set(2,3,1).sorted => Seq(1,2,3)
>>
>> what's the problem with that?
>>
>> I'm not saying that the return value be Set, just that the method will be
> available there
>>
>> ittay
>>>
>>> There is one kind of collection where you can prepend or append an
> element, and _know_ that element will appear in that order: Seq and its
> descendants.
>>>
>>> On Thu, Oct 28, 2010 at 15:23, Ittay Dror <ittay.dror@gmail.com <mailto:
> ittay.dror@gmail.com>> wrote:
>>>
>>>
>>>
>>> It seems all required methods are there. This will allow Iterator and
> Iterable to have sorting without needig to first do toSeq
>>>
>>>
>>>
>>>
>>> --
>>> Daniel C. Sobral
>>>
>>> I travel to the future all the time.

--
Daniel C. Sobral

I travel to the future all the time.

On Fri, Oct 29, 2010 at 03:17, Ittay Dror <ittay.dror@gmail.com> wrote:

Daniel Sobral wrote:

A Set is a TraversableOnce. Is it meaningful to sort a set? So is a Map. Does it make sense to sort a Map? What about HashSet/HashMap, which are the default implementations?

sure. Set(2,3,1).sorted => Seq(1,2,3)

what's the problem with that?

Shouldn't it return a SortedSet instead? That method is inherently less flexible. But you can always use an implicit to get what you want:
implicit def toSorted[T](coll: Traversable[T]) = t.toSeq.sorted
What's the problem with doing that? 

I'm not saying that the return value be Set, just that the method will be available there

ittay

There is one kind of collection where you can prepend or append an element, and _know_ that element will appear in that order: Seq and its descendants.

On Thu, Oct 28, 2010 at 15:23, Ittay Dror <ittay.dror@gmail.com> wrote:

It seems all required methods are there. This will allow Iterator and Iterable to have sorting without needig to first do toSeq

--
Daniel C. Sobral

I travel to the future all the time.

--
Daniel C. Sobral

I travel to the future all the time.

Daniel Sobral wrote:

fhmviAYKc+o77xmQk3bLKiTWUgJ0__TrUqq1z [at] mail [dot] gmail [dot] com" type="cite"> On Fri, Oct 29, 2010 at 03:17, Ittay Dror <ittay [dot] dror [at] gmail [dot] com" rel="nofollow">ittay.dror@gmail.com> wrote:

Daniel Sobral wrote:

A Set is a TraversableOnce. Is it meaningful to sort a set? So is a Map. Does it make sense to sort a Map? What about HashSet/HashMap, which are the default implementations?

sure. Set(2,3,1).sorted => Seq(1,2,3)

what's the problem with that?

Shouldn't it return a SortedSet instead? That method is inherently less flexible. But you can always use an implicit to get what you want:
implicit def toSorted[T](coll: Traversable[T]) = t.toSeq.sorted
What's the problem with doing that?

it is creating a new collection and populating it just to sort on it. (I'm aware that sorting is O(nlogn) while creating and populating is O(n), but still, why pay O(n) time?)

fhmviAYKc+o77xmQk3bLKiTWUgJ0__TrUqq1z [at] mail [dot] gmail [dot] com" type="cite">  

I'm not saying that the return value be Set, just that the method will be available there

ittay

There is one kind of collection where you can prepend or append an element, and _know_ that element will appear in that order: Seq and its descendants.

On Thu, Oct 28, 2010 at 15:23, Ittay Dror <ittay [dot] dror [at] gmail [dot] com" target="_blank" rel="nofollow">ittay.dror@gmail.com> wrote:

It seems all required methods are there. This will allow Iterator and Iterable to have sorting without needig to first do toSeq

--
Daniel C. Sobral

I travel to the future all the time.

--
Daniel C. Sobral

I travel to the future all the time.