newbie question re polymorphic function with Ordered trait

Mark Dufrense just reminded me of the syntax for specifying that T
must be comparable:

def argsortArray[T <: Ordered[T] ](a: Array[T]): Array[Int] =  {  val
pairs = a.zipWithIndex  def cmp(u: Tuple2[T,Int], v: Tuple2[T,Int]) =
(u._1 < v._1)  val sortedPairs = pairs.toList.sort(cmp)  val
(sortedVals, ndx) = sortedPairs.unzip  ndx.toArray}
However, this does not help, since Int is not a subclass of Ordered.
scala> argsortArray(Array(3,1,2)):21: error: inferred type
arguments [Int] do not conform to method argsortArray's type parameter
bounds [T <: Ordered[T]]              argsortArray(Array(3,1,2))     
        ^

kevin

On Dec 12, 3:54 pm, Kevin Murphy wrote:
> Hi
>
> I want to write a function that sorts a container and returns the
> indices of the sort
> (in Matlab, this is written as [~, perm] = sort(foo, 'ascend'))
>
> For an array of Int's, I can write the solution quite easily, as shown
> below
> (I know, I should use IndexedSeq instead of Array; whatever, one
> battle at a time!)
>
> def argsortIntArray(a: Array[Int]): Array[Int] =  {
>   val pairs = a.zipWithIndex
>   def cmp(u: Tuple2[Int,Int], v: Tuple2[Int,Int]) = (u._1 < v._1)
>   val sortedPairs = pairs.toList.sort(cmp)
>   val (sortedVals, ndx) = sortedPairs.unzip
>   ndx.toArray
>
> }
>
> scala> argsortIntArray(Array(3,1,2))
> res50: Array[Int] = Array(1, 2, 0)
>
> Now I want to make this polymorphic. The obvious solution is shown
> below:
>
> def argsortArray[T](a: Array[T]): Array[Int] =  {
>   val pairs = a.zipWithIndex
>   def cmp(u: Tuple2[T,Int], v: Tuple2[T,Int]) = (u._1 < v._1)
>   val sortedPairs = pairs.toList.sort(cmp)
>   val (sortedVals, ndx) = sortedPairs.unzip
>   ndx.toArray
>
> }
>
> But this does not compile, because I need to specify that T is a type
> that can be compared. I read somewhere in the staircase book that I
> can specify that T is a subtype of
> Ordered (I forget the syntax). But I also recall reading this is a bad
> idea, since eg Int is not a subtype of Ordered.
> What should I do?
>
> Thanks
> Kevin
>
> PS. For shits and giggles, I've included the C++ version of this
> function I wrote a while back:
>
> template
> bool CmpPairAscending(const pair &a, const pair &b) {
>   return a.first < b.first;
>
> }
>
> template
> void ArgsortAscending(const vector &vals,
>                        vector *sorted_vals,
>                        vector *ndx) {
>   int n = vals.size();
>   vector > pairs(n);
>   for (int i = 0; i < n; i++) {
>     pair tmp;
>     tmp.first = vals[i];
>     tmp.second = i;
>     pairs[i] = tmp;
>   }
>   sort(pairs.begin(), pairs.end(), CmpPairAscending);
>   sorted_vals->resize(n);
>   ndx->resize(n);
>   for (int i = 0; i < n; i++) {
>     (*sorted_vals)[i] = pairs[i].first;
>     (*ndx)[i] = pairs[i].second;
>   }
>
>
>
>
>
>
>
> }

Sorry, here is a (hopefully) better-formatted version of my previous
post:

def argsortArray[T <: Ordered[T] ](a: Array[T]): Array[Int] = {
val pairs = a.zipWithIndex
def cmp(u: Tuple2[T,Int], v: Tuple2[T,Int]) = (u._1 < v._1)
val sortedPairs = pairs.toList.sort(cmp)
val (sortedVals, ndx) = sortedPairs.unzip
ndx.toArray
}

But here's the problem: Int is not a subtype of Ordered

scala> argsortArray(Array(3,1,2))
:21: error: inferred type arguments [Int] do not conform to
method argsortArray's type parameter bounds [T <: Ordered[T]]
argsortArray(Array(3,1,2))
^

On Dec 12, 4:44 pm, Kevin Murphy wrote:
> Mark Dufrense just reminded me of the syntax for specifying that T
> must be comparable:
>
> def argsortArray[T <: Ordered[T] ](a: Array[T]): Array[Int] =  {  val
> pairs = a.zipWithIndex  def cmp(u: Tuple2[T,Int], v: Tuple2[T,Int]) =
> (u._1 < v._1)  val sortedPairs = pairs.toList.sort(cmp)  val
> (sortedVals, ndx) = sortedPairs.unzip  ndx.toArray}
> However, this does not help, since Int is not a subclass of Ordered.
> scala> argsortArray(Array(3,1,2)):21: error: inferred type
> arguments [Int] do not conform to method argsortArray's type parameter
> bounds [T <: Ordered[T]]              argsortArray(Array(3,1,2))
>         ^
>
> kevin
>
> On Dec 12, 3:54 pm, Kevin Murphy wrote:
>
>
>
>
>
>
>
> > Hi
>
> > I want to write a function that sorts a container and returns the
> > indices of the sort
> > (in Matlab, this is written as [~, perm] = sort(foo, 'ascend'))
>
> > For an array of Int's, I can write the solution quite easily, as shown
> > below
> > (I know, I should use IndexedSeq instead of Array; whatever, one
> > battle at a time!)
>
> > def argsortIntArray(a: Array[Int]): Array[Int] =  {
> >   val pairs = a.zipWithIndex
> >   def cmp(u: Tuple2[Int,Int], v: Tuple2[Int,Int]) = (u._1 < v._1)
> >   val sortedPairs = pairs.toList.sort(cmp)
> >   val (sortedVals, ndx) = sortedPairs.unzip
> >   ndx.toArray
>
> > }
>
> > scala> argsortIntArray(Array(3,1,2))
> > res50: Array[Int] = Array(1, 2, 0)
>
> > Now I want to make this polymorphic. The obvious solution is shown
> > below:
>
> > def argsortArray[T](a: Array[T]): Array[Int] =  {
> >   val pairs = a.zipWithIndex
> >   def cmp(u: Tuple2[T,Int], v: Tuple2[T,Int]) = (u._1 < v._1)
> >   val sortedPairs = pairs.toList.sort(cmp)
> >   val (sortedVals, ndx) = sortedPairs.unzip
> >   ndx.toArray
>
> > }
>
> > But this does not compile, because I need to specify that T is a type
> > that can be compared. I read somewhere in the staircase book that I
> > can specify that T is a subtype of
> > Ordered (I forget the syntax). But I also recall reading this is a bad
> > idea, since eg Int is not a subtype of Ordered.
> > What should I do?
>
> > Thanks
> > Kevin
>
> > PS. For shits and giggles, I've included the C++ version of this
> > function I wrote a while back:
>
> > template
> > bool CmpPairAscending(const pair &a, const pair &b) {
> >   return a.first < b.first;
>
> > }
>
> > template
> > void ArgsortAscending(const vector &vals,
> >                        vector *sorted_vals,
> >                        vector *ndx) {
> >   int n = vals.size();
> >   vector > pairs(n);
> >   for (int i = 0; i < n; i++) {
> >     pair tmp;
> >     tmp.first = vals[i];
> >     tmp.second = i;
> >     pairs[i] = tmp;
> >   }
> >   sort(pairs.begin(), pairs.end(), CmpPairAscending);
> >   sorted_vals->resize(n);
> >   ndx->resize(n);
> >   for (int i = 0; i < n; i++) {
> >     (*sorted_vals)[i] = pairs[i].first;
> >     (*ndx)[i] = pairs[i].second;
> >   }
>
> > }

What you want is to use Ordering[T]:

def argsortArray[T : Ordering[T]](a: Array[T]): Array[Int] = {
  Ordering[T] ordering = implicitly[Ordering[T]]
  ...
  }

An Ordering[T] is an externally-defined ordering of T, while T <: Ordered[T] indicates that T has a natural ordering defined as part of T. There is an implicit, low-priority conversion Ordered[T] => Ordering[T] that kicks in if no Ordering[T] is implicitly available: this ensures that both naturally-ordered classes, as well as externally-ordered classes (such as Int) both have an Ordering available.

Brian Maso

On Mon, Dec 12, 2011 at 4:52 PM, Kevin Murphy <murphyk2@gmail.com> wrote:

Sorry, here is a (hopefully) better-formatted version of my previous
post:


def argsortArray[T <: Ordered[T] ](a: Array[T]): Array[Int] =  {
 val pairs = a.zipWithIndex
 def cmp(u: Tuple2[T,Int], v: Tuple2[T,Int]) = (u._1 < v._1)
 val sortedPairs = pairs.toList.sort(cmp)
 val (sortedVals, ndx) = sortedPairs.unzip
 ndx.toArray
}


But here's the problem: Int is not a subtype of Ordered

scala> argsortArray(Array(3,1,2))
<console>:21: error: inferred type arguments [Int] do not conform to
method argsortArray's type parameter bounds [T <: Ordered[T]]
             argsortArray(Array(3,1,2))
             ^



On Dec 12, 4:44 pm, Kevin Murphy <murph...@gmail.com> wrote:
> Mark Dufrense just reminded me of the syntax for specifying that T
> must be comparable:
>
> def argsortArray[T <: Ordered[T] ](a: Array[T]): Array[Int] =  {  val
> pairs = a.zipWithIndex  def cmp(u: Tuple2[T,Int], v: Tuple2[T,Int]) =
> (u._1 < v._1)  val sortedPairs = pairs.toList.sort(cmp)  val
> (sortedVals, ndx) = sortedPairs.unzip  ndx.toArray}
> However, this does not help, since Int is not a subclass of Ordered.
> scala> argsortArray(Array(3,1,2))<console>:21: error: inferred type
> arguments [Int] do not conform to method argsortArray's type parameter
> bounds [T <: Ordered[T]]              argsortArray(Array(3,1,2))
>         ^
>
> kevin
>
> On Dec 12, 3:54 pm, Kevin Murphy <murph...@gmail.com> wrote:
>
>
>
>
>
>
>
> > Hi
>
> > I want to write a function that sorts a container and returns the
> > indices of the sort
> > (in Matlab, this is written as [~, perm] = sort(foo, 'ascend'))
>
> > For an array of Int's, I can write the solution quite easily, as shown
> > below
> > (I know, I should use IndexedSeq instead of Array; whatever, one
> > battle at a time!)
>
> > def argsortIntArray(a: Array[Int]): Array[Int] =  {
> >   val pairs = a.zipWithIndex
> >   def cmp(u: Tuple2[Int,Int], v: Tuple2[Int,Int]) = (u._1 < v._1)
> >   val sortedPairs = pairs.toList.sort(cmp)
> >   val (sortedVals, ndx) = sortedPairs.unzip
> >   ndx.toArray
>
> > }
>
> > scala> argsortIntArray(Array(3,1,2))
> > res50: Array[Int] = Array(1, 2, 0)
>
> > Now I want to make this polymorphic. The obvious solution is shown
> > below:
>
> > def argsortArray[T](a: Array[T]): Array[Int] =  {
> >   val pairs = a.zipWithIndex
> >   def cmp(u: Tuple2[T,Int], v: Tuple2[T,Int]) = (u._1 < v._1)
> >   val sortedPairs = pairs.toList.sort(cmp)
> >   val (sortedVals, ndx) = sortedPairs.unzip
> >   ndx.toArray
>
> > }
>
> > But this does not compile, because I need to specify that T is a type
> > that can be compared. I read somewhere in the staircase book that I
> > can specify that T is a subtype of
> > Ordered (I forget the syntax). But I also recall reading this is a bad
> > idea, since eg Int is not a subtype of Ordered.
> > What should I do?
>
> > Thanks
> > Kevin
>
> > PS. For shits and giggles, I've included the C++ version of this
> > function I wrote a while back:
>
> > template <class T>
> > bool CmpPairAscending(const pair<T, int> &a, const pair<T, int> &b) {
> >   return a.first < b.first;
>
> > }
>
> > template <class T>
> > void ArgsortAscending(const vector<T> &vals,
> >                        vector<T> *sorted_vals,
> >                        vector<int> *ndx) {
> >   int n = vals.size();
> >   vector<pair<T, int> > pairs(n);
> >   for (int i = 0; i < n; i++) {
> >     pair<T, int> tmp;
> >     tmp.first = vals[i];
> >     tmp.second = i;
> >     pairs[i] = tmp;
> >   }
> >   sort(pairs.begin(), pairs.end(), CmpPairAscending<T>);
> >   sorted_vals->resize(n);
> >   ndx->resize(n);
> >   for (int i = 0; i < n; i++) {
> >     (*sorted_vals)[i] = pairs[i].first;
> >     (*ndx)[i] = pairs[i].second;
> >   }
>
> > }

On Mon, Dec 12, 2011 at 4:57 PM, Brian Maso wrote:
> What you want is to use Ordering[T]:
>
> def argsortArray[T : Ordering[T]](a: Array[T]): Array[Int] = {
>   Ordering[T] ordering = implicitly[Ordering[T]]
>   ...
>   }
>
> An Ordering[T] is an externally-defined ordering of T, while T <: Ordered[T]
> indicates that T has a natural ordering defined as part of T. There is an
> implicit, low-priority conversion Ordered[T] => Ordering[T] that kicks in if
> no Ordering[T] is implicitly available: this ensures that both
> naturally-ordered classes, as well as externally-ordered classes (such as
> Int) both have an Ordering available.
>
> Brian Maso
>

This does not compile

def argsortArray[T : Ordering[T] ](a: Array[T]): Array[Int] = {
//Ordering[T] ordering = implicitly[Ordering[T]] // ??
val pairs = a.zipWithIndex
def cmp(u: Tuple2[T,Int], v: Tuple2[T,Int]) = (u._1 < v._1)
val sortedPairs = pairs.toList.sort(cmp)
val (sortedVals, ndx) = sortedPairs.unzip
ndx.toArray
}

:19: error: Ordering[T] does not take type parameters
def argsortArray[T : Ordering[T] ](a: Array[T]): Array[Int] = {
^
:22: error: value < is not a member of type parameter T
def cmp(u: Tuple2[T,Int], v: Tuple2[T,Int]) = (u._1 < v._1)
^

Uncommenting the line marked ?? produces the following additional error:

:20: error: No implicit Ordering defined for T.

K.

On Mon, Dec 12, 2011 at 6:23 PM, Kevin Murphy <murphyk2@gmail.com> wrote:

This does not compile

 Try this:
def argsortArray[T : Ordering](a: Array[T]): Array[Int] =  {
 val ord = implicitly[Ordering[T]]
 val pairs = a.zipWithIndex
 def cmp(u: Tuple2[T,Int], v: Tuple2[T,Int]) = (ord.lt(u._1, v._1))
 val sortedPairs = pairs.toList.sort(cmp)
 val (sortedVals, ndx) = sortedPairs.unzip
 ndx.toArray
}

You could also do it like this, so you don't have to use 'implicitly' to get the ordering:
def argsortArray[T](a: Array[T])(implicit ord: Ordering[T]): Array[Int] =  {

--
Derek Williams

On Mon, Dec 12, 2011 at 16:52, Kevin Murphy <murphyk2@gmail.com> wrote:

Sorry, here is a (hopefully) better-formatted version of my previous
post:


def argsortArray[T <: Ordered[T] ](a: Array[T]): Array[Int] =  {
 val pairs = a.zipWithIndex
 def cmp(u: Tuple2[T,Int], v: Tuple2[T,Int]) = (u._1 < v._1)
 val sortedPairs = pairs.toList.sort(cmp)
 val (sortedVals, ndx) = sortedPairs.unzip
 ndx.toArray
}


But here's the problem: Int is not a subtype of Ordered

If you don't want to use Ordering, i.e. you can use the numerical types implicit ordering, just change [T <: Ordered[T] ] to [T <% Ordered[T] ] as below:  def argsortArray[T <% Ordered[T]](a: Array[T]): Array[Int] =  {       //Ordering[T] ordering = implicitly[Ordering[T]] // ??       val pairs = a.zipWithIndex       def cmp(u: Tuple2[T,Int], v: Tuple2[T,Int]) = (u._1 < v._1)        val sortedPairs = pairs.toList.sort(cmp)       val (sortedVals, ndx) = sortedPairs.unzip       ndx.toArray      } 
This will give you a Matlab-like behavior. e.g. 
scala> val b = Array(1D, 2D, 3D, 5D, 4D, 6D)b: Array[Double] = Array(1.0, 2.0, 3.0, 5.0, 4.0, 6.0)
scala> val c = argsortArray(b)c: Array[Int] = Array(0, 1, 2, 4, 3, 5)
Cheers--
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Brian Schlining
bschlining@gmail.com

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am 13.12.2011 00:54, schrieb Kevin Murphy:
> def argsortArray[T](a: Array[T]): Array[Int] = {
> val pairs = a.zipWithIndex
> def cmp(u: Tuple2[T,Int], v: Tuple2[T,Int]) = (u._1 < v._1)
> val sortedPairs = pairs.toList.sort(cmp)
> val (sortedVals, ndx) = sortedPairs.unzip
> ndx.toArray
> }
>
> But this does not compile, because I need to specify that T is a type
> that can be compared.

I came up with

def argSort [T <% Ordered [T]] (a: Array [T]): Array [Int] =
a.zipWithIndex.sortWith (_._1 < _._1).map (e => e._2)

scala> argSort (Array (1, 2, 3))
res2: Array[Int] = Array(0, 1, 2)

> I came up with
>
> def argSort [T <% Ordered [T]] (a: Array [T]): Array [Int] =
>   a.zipWithIndex.sortWith (_._1 < _._1).map (e => e._2)
>

Nice! (And now that I've finished reading ch 21 of the stairway book
(on implicits and view bounds),
I actually understand the <% symbol :)

Thanks
Kevin