Wikibooks has a Scala implementation of a convex hull algorithm.
I was looking at it and it uses a curious idiom. distinctPoints.sorted.
But distinctPoints is an ArrayBuffer[(Int,Int)].
There is no natural order of points in 2-D space, although there are many application specific orders. Does this sort according to the x value, and if x values are the same, sorts according to the y value? Looking at the algorithm, it seems the author is really depending on the particular order that the .sorted method choses.
I would not depend on this sorting order in my programs, if I really wanted a particular order; rather I would use sortWith and specify my own compare function. I’d used the default order if I just needed a deterministic one, but not if I needed a particular one.
Can I call distinctPoints.sorted(...) passing an explicit Ordering object? Or must I create an implicit?
I have an object which is not a tuple, but which has the equivalent of an x and y inside it. It is an instance which has longitude and latitude instance variables.
Here is what I’ve tried, but it doesn’t work.
implicit def conv(w:WorldLocation):(Double,Double) = (w.lon,w.lat)
val sortedPoints = distinctPoints.sorted
I get an error:
No implicit Ordering defined for globe.WorldLocation.
val sortedPoints = distinctPoints.sorted
Question is whether one ought to depend on the seemingly arbitrary order the Scala standard library imposes on (Int,Int) especially in algorithms which are written supposing a particular ordering?
Can I call distinctPoints.sorted(...) passing an explicit Ordering object?
Yes.
Or must I create an implicit?
If you plan to use that in multiple parts it may be good to make it implicit and ensure it always in scope.
The typical approach to do that is by using a custom case class and put the implicit instance in the companion object.
Here is what I’ve tried, but it doesn’t work.
Providing an implicit conversion wont magically create a typeclass instance.
There is a default order for any tuple if all their components have an order and it will sort from left to right. If that doesn’t work for you, you can just provide your own explicit ordering or use sortBy or sortWith
So I want to use the same prioritization that the original algorithm is using, but I want to extract the x and y coord differently. What do I need to pass to .sorted(???) ?
If I use sortWith then I need to duplicate the prioritization code (correctly) which .sort is currently using. If I try to avoid the problem by simply using < with tuples, alas that doesn’t work either.
val sortedPoints = distinctPoints.sortBy(loc => loc.lon -> loc.lat)
Or you may do this so you only need to call distinctPoints.sorted
final case class WorldLocation(lon: Double, lat: Double)
object WorldLocation {
implicit final val WorldLocationOrdering: Ordering[WorldLocation] =
Ordering.by(loc => loc.lon -> loc.lat)
}
I can’t test the code, so I am sorry if it has some typos.
genial! Thanks. sortBy does the trick. It looks like it is calculating the correct thing.
These are the convex hulls of sets of city locations in various states in the United States.
It is supposed to vaguely look like state outlines, and it does.
I’m still fighting to understand the syntax and concept.
Here is the code the code that works.
val sortedPoints = distinctPoints.sortBy(c => (c.loc.lon, c.loc.lat))
It’s pretty simple, and is probably the best solution. However, I’d still like to understand how to pass an explicit parameter to .sorted. I tried the following, and it doesn’t work.
val sortedPoints = distinctPoints.sorted(Ordering.by(c => c.loc.lon -> c.loc.lat))
Am I almost there? Or completely on the wrong track?
I know @BalmungSan suggested to define an implicit variable elsewhere (in the WorldLocation object). But I’d like to understand how to make the choice more explicit. Why? because I think the way these objects need to be sorted is depends not on the class of the object begin sorted, but rather on the particular algorithm, i.e., on this implementation of convex-hull. A different algorithm might want to sort the objects in a different way.
I get the following error
missing parameter type
val sortedPoints = distinctPoints.sorted(Ordering.by(c => c.loc.lon -> c.loc.lat))
Perhaps this is a rabbit hole question, but doesn’t the compiler already know what the type of elements in distinctPoints is? Thus why doesn’t it know that the type of c is the same?
I tried already putting the type on Ordering[City], on .by[City] and on c:City => c.loc.lon -> c.loc.lat. Since none of these worked, I thought the problem must be more complicated. Turns out it’s just missing parens.
Recall that the following worked without explicit declarations
val sortedPoints = distinctPoints.sortBy(c => (c.loc.lon, c.loc.lat))
The thing is, that sorted expects an Ordering[T], but you are using an expression that evaluates to an Ordering[T].
Then, Ordering.by[X, Y] expects two type parameters and a function f: X -> Y as an argument, resulting in an Ordering[X]. The compiler would have to unify the type parameters T and X in this case which it does not do, AFAIK. (it works from the inside to the outer side, meaning it can infer X and Y if the lambda function has that information, and then go on to check whether X and T match up, according to the given constraint)
It isn’t (necessarily), it may be a specific supertype.
def sorted[B >: A](implicit ord: Ordering[B]): C
B needs to be introduced because Ordering is invariant and sticking to A would preclude using e.g. an Ordering[Animal] on a List[Cat].
Ordering (the companion object) doesn’t take type params. Ordering#by[T, S]() takes two type params - .by[City, (Double, Double)](...) should work. However, why not just declare an Ordering[City] as a val and use that - looks like the most readable and maintainable approach to me.
def sortBy[B](f: A => B)(implicit ord: Ordering[B]): C
Because here you pass an explicit conversion function where the “in” type (of c) is fixed and known and the “out” type can be inferred. There is no subtyping variation as there is for #sorted, and thus no ambiguity to what the B type is.
