|
 Fwd: Some suggestions for Ordering and PartialOrdering
Hello all
Wasn't sure which list to post this on, but: a few small suggestions
from a relative newbie who's been playing eagerly with the new 2.8
collections library. Mostly relating to Orderings.
1. sortWith and Orderings
Currently in SeqLike it's:
def sortWith(lt : (A, A) => Boolean) : Repr
but would it not be good to have:
def sortWith[B >: A](implicit cmp : Ordering[B]) : Repr
especially for consistency given that 'min' and 'max' already take an
implicit Ordering:
def min[B >: A](implicit cmp : Ordering[B]) : A
but also just because 'sort' seems like one of the most important use
cases for an 'Ordering' abstraction.
2. Ordering and Function (PartialOrdering and PartialFunction)
As an alternative solution to (1), perhaps both approaches could be
allowed by having:
Ordering[A] extends (A, A) => Boolean
rather like we have Set[A] extends (A) => Boolean.
note that, then,
PartialOrdering[A] extends PartialFunction[(A,A),Boolean]
would also make a lot of sense, were it not for the fact that Ordering
extends PartialOrdering (seems right), but PartialFunction extends
Function (seems wrong way round, at least according to the
mathematical definition of function and partial function). I suppose
you would have to use PartialFunction for Ordering too, then, to do
this, but with isDefinedAt overridden to be constant true.
3. Sets PartiallyOrdered on subsetOf
Another suggestion would be to make SetLike extend PartiallyOrdered,
using the partial order on sets given by 'subsetOf'.
Motivation being:
* 'subsetOf' on sets is one of the most common and useful examples of
a partial order.
* There's no other partial order on sets (which i can think of) which
is as natural as this one
* As a side-effect you'd get a more concise syntax for the set subset
operation (<=) and the corresponding <, >, >= for free.
Failing that, an (implicit?) PartialOrdering instance for Sets would
be nice, eg:
implicit def partialOrdering[A, This <: SetLike[A, This] with Set
[A]] : PartialOrdering[SetLike[A,This] with Set[A]] =
new PartialOrdering[SetLike[A,This] with Set[A]] {
def tryCompare(x : SetLike[A,This] with Set[A], y : SetLike[A,This]
with Set[A]) = {
if (x subsetOf y)
if (y subsetOf x) Some(0) else Some(-1)
else
if (y subsetOf x) Some(1) else None
}
def lteq(x : SetLike[A,This] with Set[A], y : SetLike[A,This] with
Set[A]) = x subsetOf y
}
and while we're at it, could PartialOrdering not supply a default
implementation of tryCompare in terms of lteq, or vice-versa?
4. Consistency of inheritance relationships between (Partial)Ordering
and (Partially)Ordered
I thought it was weird that:
Ordering[A] extends PartialOrdering[A]
but
Ordered[A] does not extend PartiallyOrdered[A]
I was wondering why, and noticed that PartiallyOrdered[+A] is
covariant in A, whereas Ordered[A] isn't ("since version 2006-07-24
this trait is no longer covariant in A"), so I guess this may have
something to do with it. Does anyone remember the rationale here?
perhaps it should be made consistent between Ordered and
PartiallyOrdered, with Ordered then extending PartiallyOrdered?
5. Implicit Orderings for Ordereds
I was wondering why scala was unable to infer an implicit Ordering[A]
for my Ordered[A] in order to get the max of a list, and I noticed
Ordering.ordered:
def ordered[A <: Ordered[A]]: Ordering[A] = new Ordering[A] {
def compare(x: A, y: A) = x.compare(y)
}
is there a reason why this isn't declared as an implicit?
If I declare something similar as an implicit, it does seem to work
nicely, generating an implicit Ordering[A] whenever I need one for an
Ordered[A], without any boilerplate required. Which would be nice to
have in general if it's possible to do. But maybe I'm inadvertently
messing something else up by doing this. Note something similar
applies to PartialOrderings for PartiallyOrdereds too.
(In general, it would be nice if there was clearer documentation about
exactly which implicits you need to provide, to get your classes
working with various bits of the standard library, as implicits are
one of the most deep / confusing areas of scala IMO. But realise 2.8's
not released yet :)
-Matt
|
|
Re: Fwd: Some suggestions for Ordering and PartialOrdering
On Mon, Oct 19, 2009 at 01:25:37AM +0100, Matthew Willson wrote:
> def sortWith(lt : (A, A) => Boolean) : Repr
Sorting has been a moving target ever since sort was deprecated and
sortWith turned up; I've not yet figured out what martin has in mind for
sortWith or whether we're losing the name sort entirely, which makes me
sad if so. Anyway, your points are valid and I've just not gotten
around to asking what's supposed to be done.
In some abandoned branch I did some more tricks with implicits and
conversions to Ordering, but I seem to have lost it all in a culling.
> but would it not be good to have:
>
> def sortWith[B >: A](implicit cmp : Ordering[B]) : Repr
Yes, this is what it should be I think, and I had this done with an
implicit conversion from (A, A) => Boolean => Ordering[A] (and that
conversion is in the Ordering object, but not marked implicit.) As I
recall there were some issues with impaired type inference, as compared
to it taking the lt function.
> but PartialFunction extends Function (seems wrong way round, at least
> according to the mathematical definition of function and partial
> function).
http://lampsvn.epfl.ch/trac/scala/ticket/85"equate PartialFunction with Function ?"
After lengthy discussion, this ticket is suddenly closed as invalid with
the transparency classic "After lots of discussion at EPFL, the group
has decided to keep things how they are." It comes up a lot. Partials
are unnecessarily clumsy to use, and it's a bummer because they're so
freaking useful.
> def ordered[A <: Ordered[A]]: Ordering[A] = new Ordering[A] {
> def compare(x: A, y: A) = x.compare(y)
> }
>
> is there a reason why this isn't declared as an implicit?
http://lampsvn.epfl.ch/trac/scala/ticket/2260"Ordering doesn't provide default implementation for Ordered"
"[...] However I can't just mark it implicit because this breaks the
coexistence of Ordering and Ordered by creating ambiguities with all the
other implicits in Ordering. As yet I don't have an idea how to address
this."
--
Paul Phillips | It's better to have gloved and tossed than never to
Apatheist | have played baseball.
Empiricist |
pp: i haul pills |----------* http://www.improving.org/paulp/ *----------
|
|
Re: Fwd: Some suggestions for Ordering and PartialOrdering
Oh, but that was before the arrival of LowPriorityImplicits, maybe I can
fix it that way now...
--
Paul Phillips | Simplicity and elegance are unpopular because
Apatheist | they require hard work and discipline to achieve
Empiricist | and education to be appreciated.
up hill, pi pals! | -- Dijkstra
|
|
Re: Fwd: Some suggestions for Ordering and PartialOrdering
Having sortWith take an Ordering is very natural, of course. I'll add
an overloaded variant of it to SeqLike. We should maybe think whether
we ant to deprecate the other sortWith, or whether we want to leave it
in (right now I see no harm leaving it in).
The other suggestions take some more thought.
Cheers
-- Martin
On Mon, Oct 19, 2009 at 6:06 AM, Paul Phillips < paulp@...> wrote:
> On Mon, Oct 19, 2009 at 01:25:37AM +0100, Matthew Willson wrote:
>> def sortWith(lt : (A, A) => Boolean) : Repr
>
> Sorting has been a moving target ever since sort was deprecated and
> sortWith turned up; I've not yet figured out what martin has in mind for
> sortWith or whether we're losing the name sort entirely, which makes me
> sad if so. Anyway, your points are valid and I've just not gotten
> around to asking what's supposed to be done.
>
> In some abandoned branch I did some more tricks with implicits and
> conversions to Ordering, but I seem to have lost it all in a culling.
>
>> but would it not be good to have:
>>
>> def sortWith[B >: A](implicit cmp : Ordering[B]) : Repr
>
> Yes, this is what it should be I think, and I had this done with an
> implicit conversion from (A, A) => Boolean => Ordering[A] (and that
> conversion is in the Ordering object, but not marked implicit.) As I
> recall there were some issues with impaired type inference, as compared
> to it taking the lt function.
>
>> but PartialFunction extends Function (seems wrong way round, at least
>> according to the mathematical definition of function and partial
>> function).
>
> http://lampsvn.epfl.ch/trac/scala/ticket/85> "equate PartialFunction with Function ?"
>
> After lengthy discussion, this ticket is suddenly closed as invalid with
> the transparency classic "After lots of discussion at EPFL, the group
> has decided to keep things how they are." It comes up a lot. Partials
> are unnecessarily clumsy to use, and it's a bummer because they're so
> freaking useful.
>
>> def ordered[A <: Ordered[A]]: Ordering[A] = new Ordering[A] {
>> def compare(x: A, y: A) = x.compare(y)
>> }
>>
>> is there a reason why this isn't declared as an implicit?
>
> http://lampsvn.epfl.ch/trac/scala/ticket/2260> "Ordering doesn't provide default implementation for Ordered"
>
> "[...] However I can't just mark it implicit because this breaks the
> coexistence of Ordering and Ordered by creating ambiguities with all the
> other implicits in Ordering. As yet I don't have an idea how to address
> this."
>
> --
> Paul Phillips | It's better to have gloved and tossed than never to
> Apatheist | have played baseball.
> Empiricist |
> pp: i haul pills |----------* http://www.improving.org/paulp/ *----------
>
|
|
Re: Fwd: Some suggestions for Ordering and PartialOrdering
While on the subject of Ordering... it'd also be nice to have a sortBy method:
def sortBy[B](f: A => B)(implicit o: Ordering[B]): Repr
such that:
val words = "The quick brown fox jumped over the lazy dog".split(' ').toList
words.sortBy(_.length) == List(The, fox, the, dog, over, lazy, quick, brown, jumped)
It makes a nice complement to:
words.groupBy(_.length) == Map(3 -> List(The, fox, the, dog), 5 -> List(quick, brown), 6 -> List(jumped), 4 -> List(over, lazy))
--j
On Mon, Oct 19, 2009 at 2:37 AM, martin odersky <martin.odersky@...> wrote:
Having sortWith take an Ordering is very natural, of course. I'll add
an overloaded variant of it to SeqLike. We should maybe think whether
we ant to deprecate the other sortWith, or whether we want to leave it
in (right now I see no harm leaving it in).
The other suggestions take some more thought.
Cheers
-- Martin
On Mon, Oct 19, 2009 at 6:06 AM, Paul Phillips < paulp@...> wrote:
> On Mon, Oct 19, 2009 at 01:25:37AM +0100, Matthew Willson wrote:
>> def sortWith(lt : (A, A) => Boolean) : Repr
>
> Sorting has been a moving target ever since sort was deprecated and
> sortWith turned up; I've not yet figured out what martin has in mind for
> sortWith or whether we're losing the name sort entirely, which makes me
> sad if so. Anyway, your points are valid and I've just not gotten
> around to asking what's supposed to be done.
>
> In some abandoned branch I did some more tricks with implicits and
> conversions to Ordering, but I seem to have lost it all in a culling.
>
>> but would it not be good to have:
>>
>> def sortWith[B >: A](implicit cmp : Ordering[B]) : Repr
>
> Yes, this is what it should be I think, and I had this done with an
> implicit conversion from (A, A) => Boolean => Ordering[A] (and that
> conversion is in the Ordering object, but not marked implicit.) As I
> recall there were some issues with impaired type inference, as compared
> to it taking the lt function.
>
>> but PartialFunction extends Function (seems wrong way round, at least
>> according to the mathematical definition of function and partial
>> function).
>
> http://lampsvn.epfl.ch/trac/scala/ticket/85
> "equate PartialFunction with Function ?"
>
> After lengthy discussion, this ticket is suddenly closed as invalid with
> the transparency classic "After lots of discussion at EPFL, the group
> has decided to keep things how they are." It comes up a lot. Partials
> are unnecessarily clumsy to use, and it's a bummer because they're so
> freaking useful.
>
>> def ordered[A <: Ordered[A]]: Ordering[A] = new Ordering[A] {
>> def compare(x: A, y: A) = x.compare(y)
>> }
>>
>> is there a reason why this isn't declared as an implicit?
>
> http://lampsvn.epfl.ch/trac/scala/ticket/2260
> "Ordering doesn't provide default implementation for Ordered"
>
> "[...] However I can't just mark it implicit because this breaks the
> coexistence of Ordering and Ordered by creating ambiguities with all the
> other implicits in Ordering. As yet I don't have an idea how to address
> this."
>
> --
> Paul Phillips | It's better to have gloved and tossed than never to
> Apatheist | have played baseball.
> Empiricist |
> pp: i haul pills |----------* http://www.improving.org/paulp/ *----------
>
|
|
Re: Fwd: Some suggestions for Ordering and PartialOrdering
On Tuesday 20 October 2009 12:06:27 Jorge Ortiz wrote:
> While on the subject of Ordering... it'd also be nice to have a sortBy
> method:
> def sortBy[B](f: A => B)(implicit o: Ordering[B]): Repr
>
> such that:
>
> val words = "The quick brown fox jumped over the lazy dog".split('
> ').toList
>
> words.sortBy(_.length) == List(The, fox, the, dog, over, lazy, quick,
> brown, jumped)
>
> It makes a nice complement to:
>
> words.groupBy(_.length) == Map(3 -> List(The, fox, the, dog), 5 ->
> List(quick, brown), 6 -> List(jumped), 4 -> List(over, lazy))
>
> Patch submitted: http://lampsvn.epfl.ch/trac/scala/ticket/2496>
> --j
Jorge, thanks! I have grepped my code and found million places to replace
'sortWith' with 'sortBy' (and reduce code noise). So, I'm in impatience now
the patch be applied (I hope it will).
|
|
Re: Fwd: Some suggestions for Ordering and PartialOrdering
It also nicely generalises to sort on multiple criteria, given the Ordering instances for TupleN val words = "The quick brown fox jumped over the lazy dog".split(' ').toList words.sortBy((_.length, _.firstOption)) == List(dog, fox, the, The, lazy, over, brown, quick, jumped)
On Tue, Oct 20, 2009 at 3:35 AM, Andrew Gaydenko <a@...> wrote:
On Tuesday 20 October 2009 12:06:27 Jorge Ortiz wrote:
> While on the subject of Ordering... it'd also be nice to have a sortBy
> method:
> def sortBy[B](f: A => B)(implicit o: Ordering[B]): Repr
>
> such that:
>
> val words = "The quick brown fox jumped over the lazy dog".split('
> ').toList
>
> words.sortBy(_.length) == List(The, fox, the, dog, over, lazy, quick,
> brown, jumped)
>
> It makes a nice complement to:
>
> words.groupBy(_.length) == Map(3 -> List(The, fox, the, dog), 5 ->
> List(quick, brown), 6 -> List(jumped), 4 -> List(over, lazy))
>
> Patch submitted: http://lampsvn.epfl.ch/trac/scala/ticket/2496
>
> --j
'sortWith' with 'sortBy' (and reduce code noise). So, I'm in impatience now
the patch be applied (I hope it will).
|
|
Re: Fwd: Some suggestions for Ordering and PartialOrdering
I completely agree. I have always wondered why such option wasn't available. I have vague recollections of this being discussed before, though.
On Tue, Oct 20, 2009 at 6:06 AM, Jorge Ortiz <jorge.ortiz@...> wrote:
While on the subject of Ordering... it'd also be nice to have a sortBy method:
def sortBy[B](f: A => B)(implicit o: Ordering[B]): Repr
such that:
val words = "The quick brown fox jumped over the lazy dog".split(' ').toList
words.sortBy(_.length) == List(The, fox, the, dog, over, lazy, quick, brown, jumped)
It makes a nice complement to:
words.groupBy(_.length) == Map(3 -> List(The, fox, the, dog), 5 -> List(quick, brown), 6 -> List(jumped), 4 -> List(over, lazy))
--j
On Mon, Oct 19, 2009 at 2:37 AM, martin odersky <martin.odersky@...> wrote:
Having sortWith take an Ordering is very natural, of course. I'll add
an overloaded variant of it to SeqLike. We should maybe think whether
we ant to deprecate the other sortWith, or whether we want to leave it
in (right now I see no harm leaving it in).
The other suggestions take some more thought.
Cheers
-- Martin
On Mon, Oct 19, 2009 at 6:06 AM, Paul Phillips < paulp@...> wrote: > On Mon, Oct 19, 2009 at 01:25:37AM +0100, Matthew Willson wrote:
>> def sortWith(lt : (A, A) => Boolean) : Repr > > Sorting has been a moving target ever since sort was deprecated and > sortWith turned up; I've not yet figured out what martin has in mind for
> sortWith or whether we're losing the name sort entirely, which makes me > sad if so. Anyway, your points are valid and I've just not gotten > around to asking what's supposed to be done.
>
> In some abandoned branch I did some more tricks with implicits and > conversions to Ordering, but I seem to have lost it all in a culling. > >> but would it not be good to have: >> >> def sortWith[B >: A](implicit cmp : Ordering[B]) : Repr
> > Yes, this is what it should be I think, and I had this done with an > implicit conversion from (A, A) => Boolean => Ordering[A] (and that > conversion is in the Ordering object, but not marked implicit.) As I
> recall there were some issues with impaired type inference, as compared > to it taking the lt function. > >> but PartialFunction extends Function (seems wrong way round, at least >> according to the mathematical definition of function and partial
>> function). > > http://lampsvn.epfl.ch/trac/scala/ticket/85> "equate PartialFunction with Function ?" >
> After lengthy discussion, this ticket is suddenly closed as invalid with > the transparency classic "After lots of discussion at EPFL, the group > has decided to keep things how they are." It comes up a lot. Partials
> are unnecessarily clumsy to use, and it's a bummer because they're so > freaking useful. > >> def ordered[A <: Ordered[A]]: Ordering[A] = new Ordering[A] { >> def compare(x: A, y: A) = x.compare(y)
>> } >> >> is there a reason why this isn't declared as an implicit? > > http://lampsvn.epfl.ch/trac/scala/ticket/2260
> "Ordering doesn't provide default implementation for Ordered" > > "[...] However I can't just mark it implicit because this breaks the > coexistence of Ordering and Ordered by creating ambiguities with all the
> other implicits in Ordering. As yet I don't have an idea how to address > this." > > -- > Paul Phillips | It's better to have gloved and tossed than never to > Apatheist | have played baseball.
> Empiricist | > pp: i haul pills |----------* http://www.improving.org/paulp/ *---------- >
-- Daniel C. Sobral Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.
|
|
Re: Fwd: Some suggestions for Ordering and PartialOrdering
On 19 Oct 2009, at 10:37, martin odersky wrote:
> Having sortWith take an Ordering is very natural, of course. I'll add
> an overloaded variant of it to SeqLike. We should maybe think whether
> we ant to deprecate the other sortWith, or whether we want to leave it
> in (right now I see no harm leaving it in).
Thanks!
Yeah seems no harm in leaving both versions...
> The other suggestions take some more thought.
Fair enough, would welcome any thoughts (even if it's just a "it needs
to stay this way because...") on those other issues.
I'd say "Implicit Orderings for Ordereds" is the most important one,
as otherwise it requires a boilerplate implicit every time you
implement Ordered.
But also would be nice if PartialOrdering and PartiallyOrdered became
fully consistent in their design when taken together with Ordering and
Ordered.
-Matt
|
|
Re: Fwd: Some suggestions for Ordering and PartialOrdering
On 19 Oct 2009, at 05:11, Paul Phillips wrote:
> Oh, but that was before the arrival of LowPriorityImplicits, maybe I
> can
> fix it that way now...
Were you talking about the implicit Orderings for Ordereds issue here?
If so that would be awesome.
Does anyone has an example of the ambiguity problems in question by
the way? ("breaks the coexistence of Ordering and Ordered by creating
ambiguities with all the other implicits in Ordering")
It seems like a pattern that could potentially crop up a lot:
- You have a trait with methods for a type which "is" a particular
kind of mathematical structure
- It's possible for there to be more than one of the same kind of
structure on a particular type, so you want the ability to pass around
these structures on a particular type as objects too
- You want the structure object for the default structure
implemented via the trait to be implicit without any additional
boilerplate
-Matt
|
|
Re: Fwd: Some suggestions for Ordering and PartialOrdering
On Tue, Oct 20, 2009 at 08:04:27PM +0100, Matthew Willson wrote:
> >Oh, but that was before the arrival of LowPriorityImplicits, maybe
> >I can
> >fix it that way now...
>
> Were you talking about the implicit Orderings for Ordereds issue here?
>
> If so that would be awesome.
I was and it is.
https://lampsvn.epfl.ch/trac/scala/changeset/19167 trait LowPriorityOrderingImplicits { ... }
Looks like problem solved, unless it isn't.
> Does anyone has an example of the ambiguity problems in question by
> the way?
Try marking that method implicit before I made it low priority and
rebuild the compiler, you'll see plenty.
--
Paul Phillips | Atheists dig the best foxholes.
Imperfectionist |
Empiricist |
i pull his palp! |----------* http://www.improving.org/paulp/ *----------
|
