tag:blogger.com,1999:blog-7045524330253482541.post4405639477394559084..comments2024-01-04T22:19:45.990-08:00Comments on Jim McBeath: My Misperception of Scala's Ordered TraitJim McBeathhttp://www.blogger.com/profile/10541190774989580614noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-7045524330253482541.post-9392986485360432332010-05-31T12:16:12.229-07:002010-05-31T12:16:12.229-07:00"Chris: You can't do this because type er..."Chris: You can't do this because type erasure makes both Ordered traits look the same...."<br /><br />You're right. I had thought that this would work in Java with Comparable, but it has the same limitation of course (and for the same reason). It's a pity because the methods being implemented are not ambiguous.Anonymoushttps://www.blogger.com/profile/09718897309693652777noreply@blogger.comtag:blogger.com,1999:blog-7045524330253482541.post-82872406709368088082010-05-31T11:23:13.171-07:002010-05-31T11:23:13.171-07:00gambistics: Thanks, your comment raises a lot of g...gambistics: Thanks, your comment raises a lot of good points.<br /><br />Agreed, our implementation is not as general as it could be. As it happens, the application was an experiment to see if we could implement a Scala version of an application that deals with arrays that can run as quickly as a reference Java version. We had been having problems with too many objects being created by implicit conversions, so we were avoiding using them inside loops and with arrays.<br /><br />Regarding working around the type system: again, this is an attempt to improve performance. It would be nice if there were a more efficient way to represent that we can accept <a href="http://cleverlytitled.blogspot.com/2009/03/so-i-read-both-jim-mcbeath-and-michids.html" rel="nofollow">one of two disjoint types</a>, and only those types. Perhaps after the compiler gets <a href="http://infoscience.epfl.ch/record/128135/files/paper.pdf" rel="nofollow">more optimizations</a>.<br /><br />James: Thanks for the link, I like that example. I found the accompanying comments to be interesting as well.<br /><br />Chris: You can't do this because type erasure makes both Ordered traits <a href="http://jim-mcbeath.blogspot.com/2008/10/polymorphism-using-implicit-conversions.html" rel="nofollow">look the same</a>. I am still hoping that Kevin Wright's <a href="http://www.scala-lang.org/node/3325" rel="nofollow">dynamic mixins</a> will allow this.Jim McBeathhttps://www.blogger.com/profile/10541190774989580614noreply@blogger.comtag:blogger.com,1999:blog-7045524330253482541.post-28457952166499372212010-05-30T20:06:39.487-07:002010-05-30T20:06:39.487-07:00This comment has been removed by a blog administrator.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7045524330253482541.post-55302724078695676202010-05-29T10:07:08.455-07:002010-05-29T10:07:08.455-07:00Hmm. It seems like what you want is: case class Th...Hmm. It seems like what you want is: case class Thing(val n: Int) extends Ordered[Thing] with Ordered[Int] {...} instead of using Ordered[Any]<br /><br />I'm not sure why that doesn't work, actually. In that way, Ordered is different from Java's Comparable.Anonymoushttps://www.blogger.com/profile/09718897309693652777noreply@blogger.comtag:blogger.com,1999:blog-7045524330253482541.post-47095746041226740012010-05-29T06:45:41.489-07:002010-05-29T06:45:41.489-07:00Have fun with this one: http://lambda-the-ultimate...Have fun with this one: http://lambda-the-ultimate.org/node/3942#comment-59763James Iryhttps://www.blogger.com/profile/02835376424060382389noreply@blogger.comtag:blogger.com,1999:blog-7045524330253482541.post-32810537277786070312010-05-29T00:15:37.620-07:002010-05-29T00:15:37.620-07:00A <% Ordered means even a different thing, than...A <% Ordered means even a different thing, than you described.<br /><br />The original signature <br /><br />def binarySearch[A <% Ordered[A]](a: IndexedSeq[A], v: A)<br /><br />is short for<br /><br />def binarySearch[A](a: IndexedSeq[A], v: A)(implicit evidence: A => Ordered[A])<br /><br />and this means that you can pass into binarySearch any sequence of elements, as long as there is an implicit value in scope which converts any value of type A into an Ordered[A]. This provides a much greater flexibility how and where to implement the order of elements of a type than the simple way you showed by implementing Ordered directly by its elements.<br /><br />So you could provide a order for our elements by defining<br /><br />implicit val orderedThing: Thing => Ordered[Thing] = x => new Ordered { /* implementation as before */ }<br /><br />somewhere outside of Thing.<br /><br />Of course, it should work as well in the case where Thing just extends Ordered[Thing]. And indeed it does, because of the implicit identity being always defined.<br /><br />The problems which occurred in your code (or your co-worker's) had another problem: Ordered[A] is invariant in A. This means an Ordered[Thing] is not an Ordered[Any] and vice versa. And furthermore, differently to Java, where an array of Strings, String[], actually is an array of Objects, Object[], this is not the case in Scala.<br /><br />And that's the cause of the error message. In <br /><br />binarySearch(a,3)<br /><br />Scala infers type Any for A. But 'a' is no Array[Any] and there is no ordering available which can compare any values of type Any.<br /><br />The root cause of your problems here is that you are working around the type-system - and that's the misconception: you are using Ordered[X] as a mechanism for complete polymorphic comparison. But by extending Ordered[X] you are, in fact, signing a contract: My class can compare to all values of type X. But: Scala makes it easy to break such contracts by casting (hidden in match/case) and by throwing exceptions. In your example you have no static type safety any more, because things like that compile, too:<br /><br />binarySearch(a, "test") // throws a runtime exception<br /><br />There are two more type-aware solutions:<br /><br />1. Use your first version and when searching always create an example object for which you know how to compare. I.e. always use 'binarySearch(a, Thing(4)' instead of 'binarySearch(a, 4)'. <br /><br />2. Use implicits to your advantage.<br /><br /><a href="http://gist.github.com/418099" rel="nofollow">Here's</a> a version which tries to respect types:<br /><br />def binarySearch[B, A <% Ordered[B]](a: Array[A], v: B) = {<br /> def recurse(low: Int, high: Int): Option[Int] = (low + high) / 2 match {<br /> case _ if high < low => None<br /> case mid if a(mid) > v => recurse(low, mid - 1)<br /> case mid if a(mid) < v => recurse(mid + 1, high)<br /> case mid => Some(mid)<br /> }<br /> recurse(0, a.size - 1)<br />}<br /><br />case class Thing(val n:Int)<br /><br />implicit val compThingToThing: Thing => Ordered[Thing] =<br /> t => new Ordered[Thing] {<br /> def compare(that: Thing): Int = { t.n - that.n }<br /> }<br /> <br />implicit val compThingToInt: Thing => Ordered[Int] =<br /> t => new Ordered[Int] {<br /> def compare(that: Int): Int = { t.n - that }<br /> }<br /> <br /> <br />val a:Array[Thing] = Array(Thing(1), Thing(3), Thing(5), Thing(6))<br /><br />binarySearch(a, Thing(5)) // compiles, compThingToThing is available<br />binarySearch(a, 5) // compiles, compThingToInt is available<br />binarySearch(a, "test") // doesn't compile, it isn't known how to compare Things to strings<br /><br />The implicit values are here evidence (and implementation) of the fact that we can compare Things to other things of a specific type. Using this design, you can add other comparators later by type without having to fall back to casting and throwing exceptions and don't lose type-safety either.Johanneshttps://www.blogger.com/profile/17243632157564129686noreply@blogger.com