How do I write the equivalent of T extends Comparable<? super T>?

I think this works ..
scala> def sort[T <: Comparable[T]](a: Array[_ <: T]) =     |   a.reduce((x, y) => if (x.compareTo(y) > 0) x else y) sort: [T <: java.lang.Comparable[T]](a: Array[_ <: T])T  

On Wed, Aug 10, 2011 at 10:43 PM, Cay Horstmann <cay [dot] horstmann [at] gmail [dot] com> wrote:

In Java, I declare public static <T extends Comparable<? super T>> T
max(T[] a) . . . if I want a function that accepts an array of
comparables which may have picked up the comparability in a
superclass.

I can't figure out how to do this in Scala. I start with a max
function without that wrinkle:

def max[T <: Comparable[T]](a: Array[T]) = a.reduce((x, y) => if
(x.compareTo(y) > 0) x else y)

Now I add the wildcard like in Java:

def max[T <: Comparable[_ >: T]](a: Array[T]) = a.reduce((x, y) => if
(x.compareTo(y) > 0) x else y)
error: illegal cyclic reference involving type T

So I try the forSome notation:

def max[T forSome { type T <: Comparable[U] ; type U >: T }](a:
Array[T]) = a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
error: ']' expected but 'forSome' found

Ok, I guess that makes sense. T forSome { ... } is a type, not a type
variable. How about this:

def max(a: Array[T forSome { type T <: Comparable[U] ; type U >: T }])
= a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
error: type mismatch;
 found   : T where type T <: java.lang.Comparable[U]
 required: U where type U >: T

Anyway, I think that can't be right because the simpler version fails already:

def max(a: Array[T forSome { type T <: Comparable[T] }]) =
a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
 error: type mismatch;
 found   : y.type (with underlying type T forSome { type T <:
java.lang.Comparable[T] })
 required: T where type T <: java.lang.Comparable[T]

So, can this be done in Scala?

Thanks,

Cay

--
Debasish Ghosh
http://manning.com/ghosh

Twttr: @debasishg
Blog: http://debasishg.blogspot.com
Code: http://github.com/debasishg

also I think it becomes easier with List, the latter being covariant ..

On Wed, Aug 10, 2011 at 10:56 PM, Debasish Ghosh <ghosh [dot] debasish [at] gmail [dot] com> wrote:

I think this works ..
scala> def sort[T <: Comparable[T]](a: Array[_ <: T]) =      |   a.reduce((x, y) => if (x.compareTo(y) > 0) x else y) sort: [T <: java.lang.Comparable[T]](a: Array[_ <: T])T  

On Wed, Aug 10, 2011 at 10:43 PM, Cay Horstmann <cay [dot] horstmann [at] gmail [dot] com> wrote:

In Java, I declare public static <T extends Comparable<? super T>> T
max(T[] a) . . . if I want a function that accepts an array of
comparables which may have picked up the comparability in a
superclass.

I can't figure out how to do this in Scala. I start with a max
function without that wrinkle:

def max[T <: Comparable[T]](a: Array[T]) = a.reduce((x, y) => if
(x.compareTo(y) > 0) x else y)

Now I add the wildcard like in Java:

def max[T <: Comparable[_ >: T]](a: Array[T]) = a.reduce((x, y) => if
(x.compareTo(y) > 0) x else y)
error: illegal cyclic reference involving type T

So I try the forSome notation:

def max[T forSome { type T <: Comparable[U] ; type U >: T }](a:
Array[T]) = a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
error: ']' expected but 'forSome' found

Ok, I guess that makes sense. T forSome { ... } is a type, not a type
variable. How about this:

def max(a: Array[T forSome { type T <: Comparable[U] ; type U >: T }])
= a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
error: type mismatch;
 found   : T where type T <: java.lang.Comparable[U]
 required: U where type U >: T

Anyway, I think that can't be right because the simpler version fails already:

def max(a: Array[T forSome { type T <: Comparable[T] }]) =
a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
 error: type mismatch;
 found   : y.type (with underlying type T forSome { type T <:
java.lang.Comparable[T] })
 required: T where type T <: java.lang.Comparable[T]

So, can this be done in Scala?

Thanks,

Cay

--
Debasish Ghosh
http://manning.com/ghosh

Twttr: @debasishg
Blog: http://debasishg.blogspot.com
Code: http://github.com/debasishg

--
Debasish Ghosh
http://manning.com/ghosh

Twttr: @debasishg
Blog: http://debasishg.blogspot.com
Code: http://github.com/debasishg

No, that doesn't work. Try out

import java.util._
max(Array(new GregorianCalendar(2000, Calendar.JANUARY, 1),
new GregorianCalendar(1900, Calendar.JANUARY, 1)))

The problem is that GregorianCalendar extends Comparable[Calendar], not
Comparable[GregorianCalendar].

That's why I am searching for a way to express T <: Comparable[_ >: T]

> On Wed, Aug 10, 2011 at 10:56 PM, Debasish Ghosh
> wrote:
>>
>> I think this works ..
>> scala> def max[T <: Comparable[T]](a: Array[_ <: T]) =
>>      |   a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
>> max: [T <: java.lang.Comparable[T]](a: Array[_ <: T])T
>>
>>
>> On Wed, Aug 10, 2011 at 10:43 PM, Cay Horstmann
>> wrote:
>>>
>>> In Java, I declare public static > T
>>> max(T[] a) . . . if I want a function that accepts an array of
>>> comparables which may have picked up the comparability in a
>>> superclass.
>>>
>>> I can't figure out how to do this in Scala. I start with a max
>>> function without that wrinkle:
>>>
>>> def max[T <: Comparable[T]](a: Array[T]) = a.reduce((x, y) => if
>>> (x.compareTo(y) > 0) x else y)
>>>
>>> Now I add the wildcard like in Java:
>>>
>>> def max[T <: Comparable[_ >: T]](a: Array[T]) = a.reduce((x, y) => if
>>> (x.compareTo(y) > 0) x else y)
>>> error: illegal cyclic reference involving type T
>>>
>>> So I try the forSome notation:
>>>
>>> def max[T forSome { type T <: Comparable[U] ; type U >: T }](a:
>>> Array[T]) = a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
>>> error: ']' expected but 'forSome' found
>>>
>>> Ok, I guess that makes sense. T forSome { ... } is a type, not a type
>>> variable. How about this:
>>>
>>> def max(a: Array[T forSome { type T <: Comparable[U] ; type U >: T }])
>>> = a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
>>> error: type mismatch;
>>>  found   : T where type T <: java.lang.Comparable[U]
>>>  required: U where type U >: T
>>>
>>> Anyway, I think that can't be right because the simpler version fails
>>> already:
>>>
>>> def max(a: Array[T forSome { type T <: Comparable[T] }]) =
>>> a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
>>>  error: type mismatch;
>>>  found   : y.type (with underlying type T forSome { type T <:
>>> java.lang.Comparable[T] })
>>>  required: T where type T <: java.lang.Comparable[T]
>>>
>>> So, can this be done in Scala?
>>>
>>> Thanks,
>>>
>>> Cay
>>
>>
>>
>> --
>> Debasish Ghosh
>> http://manning.com/ghosh
>>
>> Twttr: @debasishg
>> Blog: http://debasishg.blogspot.com
>> Code: http://github.com/debasishg
>
>
>
> --
> Debasish Ghosh
> http://manning.com/ghosh
>
> Twttr: @debasishg
> Blog: http://debasishg.blogspot.com
> Code: http://github.com/debasishg
>

Forgot to reply to list!

I got this to work.

scala> def max[T <: Comparable[U], U >: T](a: Array[T]): T = a.reduce((x, y) =>
if (x.compareTo(y) > 0) x else y)
max: [T <: java.lang.Comparable[U], U >: T](a: Array[T])T

Unfortunately, the compiler doesn't seem to infer the correct type
parameters, you'll have to supply them yourself:

scala> max(Array(new GregorianCalendar(2000, Calendar.JANUARY, 1),
| new GregorianCalendar(1900, Calendar.JANUARY, 1)))
:12: error: inferred type arguments
[java.util.GregorianCalendar,java.util.GregorianCalendar] do not
conform to method max's type parameter bounds [T <
: java.lang.Comparable[U],U >: T]
max(Array(new GregorianCalendar(2000, Calendar.JANUARY, 1),
^

scala> max[GregorianCalendar, Calendar](Array(new
GregorianCalendar(2000, Calendar.JANUARY, 1),
| new GregorianCalendar(1900, Calendar.JANUARY, 1)))
res3: java.util.GregorianCalendar = //.. success!

This also works:

scala> def max[U >: T <: Calendar, T <: Comparable[U]](a: Array[U]) =
a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
max: [U >: T <: java.util.Calendar, T <: java.lang.Comparable[U]](a:
Array[U])U

Calling with:

scala> max(Array(new GregorianCalendar(2000, Calendar.JANUARY, 1),new
GregorianCalendar(1900, Calendar.JANUARY, 1)))

I was hoping for a solution that does not make the user supply the types.

As I look at this more, I really want to be able to use

def max[T <: Comparable[_ >: T]](a: Array[T]) = a.reduce((x, y) => if
(x.compareTo(y) > 0) x else y)

I hunted around for a Java method with that type parameter. The
following method in j.u.Collections will do nicely.

static > void sort(List list)

So, let's see how Scala looks at this type:

Collections.sort _
:12: error: ambiguous reference to overloaded definition,
both method sort in object Collections of type [T](x$1:
java.util.List[T], x$2: java.util.Comparator[_ >: T])Unit
and method sort in object Collections of type [T <:
java.lang.Comparable[_ >: T]](x$1: java.util.List[T])Unit
match expected type ?

Never mind the ambiguity. The second one is ours. And look at the type
parameter: T <: java.lang.Comparable[_ >: T]

So, why can't I write that parameter in my Scala code? A cyclic
reference is ok when it comes from Java but not when I write it in
Scala?

On Wed, Aug 10, 2011 at 1:06 PM, Garrett Rowe wrote:
> Forgot to reply to list!
>
> I got this to work.
>
> scala> def max[T <: Comparable[U], U >: T](a: Array[T]): T = a.reduce((x, y) =>
> if (x.compareTo(y) > 0) x else y)
> max: [T <: java.lang.Comparable[U], U >: T](a: Array[T])T
>
>
> Unfortunately, the compiler doesn't seem to infer the correct type
> parameters, you'll have to supply them yourself:
>
> scala> max(Array(new GregorianCalendar(2000, Calendar.JANUARY, 1),
>    |     new GregorianCalendar(1900, Calendar.JANUARY, 1)))
> :12: error: inferred type arguments
> [java.util.GregorianCalendar,java.util.GregorianCalendar] do not
> conform to method max's type parameter bounds [T <
> : java.lang.Comparable[U],U >: T]
>      max(Array(new GregorianCalendar(2000, Calendar.JANUARY, 1),
>      ^
>
> scala> max[GregorianCalendar, Calendar](Array(new
> GregorianCalendar(2000, Calendar.JANUARY, 1),
>    |     new GregorianCalendar(1900, Calendar.JANUARY, 1)))
> res3: java.util.GregorianCalendar = //.. success!
>

I am looking for a generic way of writing max so that it will work
with any class that is a subtype of Comparable[SomeSuperclass].
GregorianCalendar/Calendar is just an example from the standard Java
library, to show that such things exist in the wild. If I make

class Person(val name: String) extends Comparable[Person] {
override def compareTo(other: Person) = name.compareTo(other.name)
}

class Student(name: String, val major: String) extends Person(name)

I'd like to use the same max function to process an Array[Student].

On Wed, Aug 10, 2011 at 2:01 PM, Dave wrote:
> This also works:
>
> scala> def max[U >: T <: Calendar, T <: Comparable[U]](a: Array[U]) =
> a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
> max: [U >: T <: java.util.Calendar, T <: java.lang.Comparable[U]](a:
> Array[U])U
>
> Calling with:
>
> scala> max(Array(new GregorianCalendar(2000, Calendar.JANUARY, 1),new
> GregorianCalendar(1900, Calendar.JANUARY, 1)))
>
>

On Wed, Aug 10, 2011 at 6:13 PM, Cay Horstmann wrote:
> I can't figure out how to do this in Scala. I start with a max
> function without that wrinkle:
>
> def max[T <: Comparable[T]](a: Array[T]) = a.reduce((x, y) => if
> (x.compareTo(y) > 0) x else y)
>
> Now I add the wildcard like in Java:
>
> def max[T <: Comparable[_ >: T]](a: Array[T]) = a.reduce((x, y) => if
> (x.compareTo(y) > 0) x else y)
> error: illegal cyclic reference involving type T

You can make this work by using a type constraint rather than a bound,

scala> def max[T](a : Array[T])(implicit ev : T <:< Comparable[_ >: T]) =
a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
max: [T](a: Array[T])(implicit ev: <:<[T,java.lang.Comparable[_ >: T]])T

scala> max(Array("foo", "bar", "baz"))
res0: java.lang.String = foo

scala> max(Array(new GregorianCalendar(2000, Calendar.JANUARY, 1),
| new GregorianCalendar(1900, Calendar.JANUARY, 1)))
res1: java.util.GregorianCalendar = java.util.GregorianCalendar[ ...

This feels a little unsatisfactory however: if this can be expressed
directly as a type bound in Java we really ought to be able to match
that in Scala.

Cheers,

Miles

For reasons I don't yet fully understand, I also got it to work using
a view bound:

object CPTest {
import java.util._

case class P(n: Int) extends Comparable[Object] {
def compareTo(o: Object): Int = toString.compareTo(o.toString)
}

def max[T <% Comparable[_ >: T]](ts: Array[T]): T = ts.reduce { (x, y) =>
if (x.compareTo(y) > 0) x else y
}

def main(args: Array[String]): Unit = {
val m = max(Array(new GregorianCalendar(2000, Calendar.JANUARY, 1),
new GregorianCalendar(1900, Calendar.JANUARY, 1)))

println(m)
}
}

On Wed, Aug 10, 2011 at 11:23 PM, Garrett Rowe wrote:
> For reasons I don't yet fully understand, I also got it to work using
> a view bound:

If you desugar you'll see that's pretty much equivalent to the version
with the type constraint.

Cheers,

Miles

On Wed, Aug 10, 2011 at 18:58, Miles Sabin wrote:
> On Wed, Aug 10, 2011 at 6:13 PM, Cay Horstmann wrote:
>> I can't figure out how to do this in Scala. I start with a max
>> function without that wrinkle:
>>
>> def max[T <: Comparable[T]](a: Array[T]) = a.reduce((x, y) => if
>> (x.compareTo(y) > 0) x else y)
>>
>> Now I add the wildcard like in Java:
>>
>> def max[T <: Comparable[_ >: T]](a: Array[T]) = a.reduce((x, y) => if
>> (x.compareTo(y) > 0) x else y)
>> error: illegal cyclic reference involving type T
>
> You can make this work by using a type constraint rather than a bound,
>
> scala> def max[T](a : Array[T])(implicit ev : T <:< Comparable[_ >: T]) =
>  a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
> max: [T](a: Array[T])(implicit ev: <:<[T,java.lang.Comparable[_ >: T]])T
>
> scala> max(Array("foo", "bar", "baz"))
> res0: java.lang.String = foo
>
> scala> max(Array(new GregorianCalendar(2000, Calendar.JANUARY, 1),
>     |     new GregorianCalendar(1900, Calendar.JANUARY, 1)))
> res1: java.util.GregorianCalendar = java.util.GregorianCalendar[ ...
>
> This feels a little unsatisfactory however: if this can be expressed
> directly as a type bound in Java we really ought to be able to match
> that in Scala.

I saw this problem before. The only place it doesn't seem to work is
as a type parameter. See here for example:
http://stackoverflow.com/questions/6702524/how-do-you-explicitly-specify...

That might have worked here as well:

def max[CC <: Array[T] forSome { type T <: Comparable[T]}](a: CC)

The problem is that Array does not implement reduce, and the view is
not available. Anyway, I agree. It feels very strange that this type
can be inferred, that you can write it like above, that you can
express it in a "type" declaration, as an implicit constraint, but not
as a type parameter.

On Thu, Aug 11, 2011 at 5:18 AM, Daniel Sobral wrote:
> That might have worked here as well:
>
> def max[CC <: Array[T] forSome { type T <: Comparable[T]}](a: CC)
>
> The problem is that Array does not implement reduce, and the view is
> not available.

That's an interesting twist that I hadn't considered. But if you
replace Array[T] with ArrayBuffer[T]

def max[CC <: ArrayBuffer[T] forSome { type T <: Comparable[T]}](a:
CC) = a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
value compareTo is not a member of type parameter A

Weirdly enough, using Buffer[T] works.

But it isn't capturing that T should be a subtype of Comparable[U] for
some U :> T.

So, I tried adding that:

def max[CC <: scala.collection.mutable.Buffer[T] forSome { type T <:
Comparable[U] forSome { type U >: T } }]

And I was back at the illegal cyclic reference.

Cheers,

Cay

On Wed, Aug 10, 2011 at 10:58 PM, Miles Sabin wrote:
> This feels a little unsatisfactory however: if this can be expressed
> directly as a type bound in Java we really ought to be able to match
> that in Scala.

Just to emphasize how unsatisfactory this is, a type alias solves the
problem too,

scala> type SuperComparable[T] = Comparable[_ >: T]
defined type alias SuperComparable

scala> def max[T <: SuperComparable[T]](a: Array[T]) =
| a.reduce((x, y) => if (x.compareTo(y) > 0) x else y)
max: [T <: SuperComparable[T]](a: Array[T])T

scala> max(Array("foo", "bar", "baz"))
res0: java.lang.String = foo

scala> import java.util._
import java.util._

scala> max(Array(new GregorianCalendar(2000, Calendar.JANUARY, 1),
| new GregorianCalendar(1900, Calendar.JANUARY, 1)))
res1: java.util.GregorianCalendar = java.util.GregorianCalendar[ ...

Cheers,

Miles