Composing orderings from (ordered) field members

On Sun, Jul 31, 2011 at 10:48, Patrick Roemer wrote:
> Hi,
>
> looks like whenever I experiment with Scala, I'm hitting the ceiling at the
> same spot: Collections containing items with heterogenous generic arguments.
> I've already asked for instances of this issue on this list before and have
> been pointed to existential types and type members, which solved these
> concrete problems.

Mind you, you hit this problem because that is the wrong approach --
for Scala, anyway. You should encapsulate the heterogenous data in an
ADT. Something like this:

sealed trait MyData
case class MyInt(n: Int) extends MyData
case class MyString(s: String) extends MyData

You do that, and all problems suddenly disappear. You can match on
them, you don't need existentials, etc.

>
> Now I'd like to specify an ordering for a "complex" type by just listing
> "extractor" functions for its (Ordered) fields, i.e.
>
> case class Item(id: Int, name : String)
> implicit val ord = ordering((_: Item).id, (_: Item).name)
> val sorted =
>  List(Item(42, "a"), Item(41, "b"), Item(1, "a"), Item(42, "b")).sorted
>
> should yield an ordering that sorts by id first, and then, for identical
> ids, by name:
>
> $> Item(1,a), Item(41,b), Item(42,a), Item(42,b)
>
> ...and for reverted order of extractors:
>
> implicit val ord = ordering((_: Item).name, (_: Item).id)
>
> $> Item(1,a), Item(42,a), Item(41,b), Item(42,b)
>
> So, naively speaking, I'm trying to process a collection of type
>
> T => Ordered[_]
>
> to create an Ordering[T].
>
> However, I couldn't get this to fly at all: Existential types didn't seem to
> match for invocations of the same extractor, and when introducing an
> Extractor type with a type member and a corresponding implicit conversion
> from extractor methods I failed to come up with a way to capture the
> predefined implicit conversions from the field types to Ordered.
>
> My current "solution" resolves to "sub orderings" through implicits before
> they even enter the #ordering factory method, avoiding the "heterogeneous"
> collection altogether:
>
> implicit def extractor2Ordering[T, M](extractor: T => M)
>      (implicit ordering: Ordering[M]) =
>  new Ordering[T]() {
>    override def compare(a: T, b: T) =
>      ordering.compare(extractor(a), extractor(b))
>    }
>
> def ordering[T](orderings: Ordering[T]*) = {
>  val baseOrdering = new Ordering[T]() {
>    override def compare(a: T, b: T) = 0
>  }
>  orderings.foldRight(baseOrdering)((ord, subOrd) => new Ordering[T]() {
>    override def compare(a: T, b: T) = {
>      val subRes = ord.compare(a, b)
>      if(subRes != 0) subRes else subOrd.compare(a, b)
>    }
>  })
> }
>
> This kind of works, but it feels awkward. So I'd like to know if there's a
> better way to achieve this - in particular: if there's any way to actually
> get this done involving a heterogeneous collection of extractor functions.
>
> Any input is appreciated. Thanks in advance!
>
> Best regards,
> Patrick
>
>

Responding to Daniel Sobral:
> On Sun, Jul 31, 2011 at 10:48, Patrick Roemer wrote:
>> looks like whenever I experiment with Scala, I'm hitting the ceiling at the
>> same spot: Collections containing items with heterogenous generic arguments.
>> I've already asked for instances of this issue on this list before and have
>> been pointed to existential types and type members, which solved these
>> concrete problems.
>
> Mind you, you hit this problem because that is the wrong approach --
> for Scala, anyway. You should encapsulate the heterogenous data in an
> ADT. Something like this:
>
> sealed trait MyData
> case class MyInt(n: Int) extends MyData
> case class MyString(s: String) extends MyData
>
> You do that, and all problems suddenly disappear. You can match on
> them, you don't need existentials, etc.

Thanks for the feedback! I'm not entirely sure I understand how this
advice applies to my concrete scenario. To start with, Ordered/Ordering
already looks like a proper ADT for this use case to me, it just happens
to be generic...?

If I understand correctly, you suggest something like this:

trait MyComparable {
def compare(other: MyComparable): Int
}

case class MyInt(i: Int) extends MyComparable {
override def compare(other: MyComparable) = {
other match {
case MyInt(ii) => i.compare(ii)
case _ => throw new IllegalArgumentException()
}
}
}

implicit def int2cmp(i: Int) = MyInt(i)

// (the same for any other ordered member type I expect to encounter)

def ordering[T](extractors: (T => MyComparable)*) = ...

Maybe it's wrong expectations/missing Scala idiom familiarity on my
side, but this feels rather javaesque to me: It seems to require almost
identical boilerplate code for any type I'd like to support, it's losing
type information and introduces the potential for runtime "type
failures" (the default match), and it basically duplicates functionality
I should get from Ordered/Ordering for free. Have I misunderstood your
suggestion?

As for the general use of existential types/type members for
"collections with heterogeneous generics" (type members being
preferred), I got the impression that there's a not-too-frequent but
still existent range of valid use cases from discussions like this:

http://thread.gmane.org/gmane.comp.lang.scala/10876

Is that impression wrong or outdated?

Thanks and best regards,
Patrick

On Sun, Jul 31, 2011 at 3:48 PM, Patrick Roemer wrote:
> implicit def extractor2Ordering[T, M](extractor: T => M)
>      (implicit ordering: Ordering[M]) =
>  new Ordering[T]() {
>    override def compare(a: T, b: T) =
>      ordering.compare(extractor(a), extractor(b))
>    }

This is in the standard library as "Ordering.by", however, it is not implicit.

> def ordering[T](orderings: Ordering[T]*) = {
>  val baseOrdering = new Ordering[T]() {
>    override def compare(a: T, b: T) = 0
>  }
>  orderings.foldRight(baseOrdering)((ord, subOrd) => new Ordering[T]() {
>    override def compare(a: T, b: T) = {
>      val subRes = ord.compare(a, b)
>      if(subRes != 0) subRes else subOrd.compare(a, b)
>    }
>  })
> }
>
> This kind of works, but it feels awkward.

I don't think that's particular bad.

Here's a simple solution if you wanted to create an Ordering from all
fields of a case class:

object Test extends App {
case class Person(id: Int, name: String)

def ordering[T1: Ordering, T2: Ordering, R](unapply: R =>
Option[(T1, T2)]): Ordering[R] =
Ordering.by((r: R) => unapply(r).get)

val personOrdering = ordering(Person.unapply)
val p1 = Person(1, "Test1")
val p2 = Person(2, "Test2")
val p1b = Person(1, "Test0")

println(personOrdering.compare(p1, p2))
println(personOrdering.compare(p1, p1b))
println(personOrdering.compare(p2, p1b))
}

However, you'd have to adapt it to every possible arity of case classes.

Responding to Johannes Rudolph:
> On Sun, Jul 31, 2011 at 3:48 PM, Patrick Roemer wrote:
>> implicit def extractor2Ordering[T, M](extractor: T => M)
>> (implicit ordering: Ordering[M]) =
>> new Ordering[T]() {
>> override def compare(a: T, b: T) =
>> ordering.compare(extractor(a), extractor(b))
>> }
>
> This is in the standard library as "Ordering.by", however, it is not implicit.

Ah, hadn't seen that. Re-considering, I think I like an explicit "by"
more than my implicit variant. But that may just be because I still feel
kind of uncomfortable with implicits - too much magic behind the scenes. ;)

>> def ordering[T](orderings: Ordering[T]*) = {
>> val baseOrdering = new Ordering[T]() {
>> override def compare(a: T, b: T) = 0
>> }
>> orderings.foldRight(baseOrdering)((ord, subOrd) => new Ordering[T]() {
>> override def compare(a: T, b: T) = {
>> val subRes = ord.compare(a, b)
>> if(subRes != 0) subRes else subOrd.compare(a, b)
>> }
>> })
>> }
>>
>> This kind of works, but it feels awkward.
>
> I don't think that's particular bad.

Ok, thanks. If the Ordering API already takes a similar approach, as
indicated by this #by() method, I guess I'll stick with my existing
solution then. I was just wondering whether I had overlooked some
"better" way.

> case class Person(id: Int, name: String)
>
> def ordering[T1: Ordering, T2: Ordering, R](unapply: R =>
> Option[(T1, T2)]): Ordering[R] =
> Ordering.by((r: R) => unapply(r).get)
>
> val personOrdering = ordering(Person.unapply)
> val p1 = Person(1, "Test1")
> val p2 = Person(2, "Test2")
> val p1b = Person(1, "Test0")
>
> println(personOrdering.compare(p1, p2))
> println(personOrdering.compare(p1, p1b))
> println(personOrdering.compare(p2, p1b))

Nice. :) I wasn't aware of the #unapply() method on case classes nor the
"automagic" ordering for tuples. It's not applicable to my use case,
however, since I explicitly want to specify the order/"priority" of fields.

Thanks and best regards,
Patrick