A Comparable type?

[gvanrossum]

I (Guido) wondered how I would compare two arguments whose type is a type variable:

def cmp(a: T, b: T) -> int:
    if a < b: return -1
    if a > b: return 1
    return 0

Jukka wrote:
"""
This is a long-standing issue, and we've discussed this before in some detail (e.g., https://github.com/JukkaL/typing/issues/9). However, it wasn't discussed in typehinting, as far as I can tell. Currently we need to use a cast to use < instead of ==, which is pretty ugly.

We could define a Comparable ABC and support that as an "upper bound" for a type variable (bounded polymorphism). About the simplest useful implementation would be like this:

class Comparable(metaclass=ABCMeta):
    @abstractmethod
    def __gt__(self, other: Any) -> bool: pass
    ... # __lt__ etc. as well

...

CT = TypeVar('CT', bound=Comparable) # This is different from TypeVar('CT', Comparable)!

def min(x: CT, y: CT) -> CT:
    if x < y:
        return x
    else:
        return y

f(1, 2) # ok, return type int
f('x', 'y') # ok, return type str
f('x', 1) # probably ok, return type Comparable, which is not optimal
f(int, int)  # error, types aren't comparable

However, this doesn't verify whether the types can be compared to each other, only that they can be compared to something (because of the Any argument type). This feature would be easy to add to mypy.

The way Java etc. do this is to support a fancier language feature called "F-bounded polymorphism" or "F-bounded quantification". With it we can say that int can be compared with only int (Comparable[int]), etc. For example:

class Comparable(Generic[T]):
    @abstractmethod
    def __gt__(self, other: T) -> bool: pass
    ... # __lt__ etc. as well

...


CT = TypeVar('CT', bound=Comparable['CT'])   # Any type that is comparable with itself

def min(x: CT, y: CT) -> CT:
    if x < y:
        return x
    else:
        return y

f(1, 2) # ok, return type int
f('x', 'y') # ok, return type str
f('x', 1) # error, since these are not comparable to each other
f(int, int)  # error, types aren't comparable at all

This would be more involved to add to mypy. It would probably be one or two days of work for a minimal implementation. I'm not even quite sure that the above would be sufficiently general (Comparable should be contravariant, I think, so that Comparable[object] is a subtype of Comparable[int] :-/ ).

Comparable is probably the only common use case for this complex feature.
"""

[gvanrossum]

I think that for now the first solution is fine -- Python's rules for what can be compared to what are complex (every type gets to decide for itself) so even the F-bounded nonsense won't capture reality. It looks like we could still add a more complex version in the future since it would involve a new keyword arg to TypeVar().

[vlasovskikh]

Jukka, Mark, and myself believe that it's a good idea to have the generic type Comparable and not to introduce any bounded polymorphism for rare cases such as min(x, y):

def min(x: Comparable, y: Comparable) -> Any:
    ...

[JukkaL]

I was actually arguing for supporting bounds, but not using 'F-bounded polymorphism'. I.e., min could be written like this (we just need to figure out what to call bound):

from typing import TypeVar, Comparable

T = TypeVar('T', bound=Comparable)

def min(x: T, y: T) -> T:
    ...

[JukkaL]

And maybe define Comparable conceptually like this:

class Comparable(metaclass=ABCMeta):
    @abstractmethod
    def __lt__(self, other: Any) -> bool: pass
    @abstractmethod
    def __gt__(self, other: Any) -> bool: pass
    def __le__(self, other: Any) -> bool:
        return not self > other
    def __ge__(self, other: Any) -> bool:
        return not self < other

Equality would be inherited from object, so it doesn't need to specified explicitly.

[JukkaL]

Are we going to include Comparable and type variable bounds?

[gvanrossum]

I would like it yes.

[gvanrossum]

@JukkaL please tell me what syntax this would have (I'm blanking out on what we decided).

[JukkaL]

As far as I can remember, the only presented alternative has been this, and I'm okay with it:

T = TypeVar('T', bound=Comparable)

To make it more explicit (but also more verbose and a bit technical sounding), we could use upper_bound:

T = TypeVar('T', upper_bound=Comparable)

We could also have lower_bound for generality. It would probably be at least marginally useful. Example:

T = TypeVar('T', lower_bound=int)

def append_first(x: List[int], y: List[T]) -> None:
    y.append(x[0])

a = [1]
b = [...]  # type: List[Union[int, str]]

append_first(a, b)  # Okay, but only because of lower_bound

FWIW, Java uses this terminology (upper/lower bound): http://docs.oracle.com/javase/7/docs/api/javax/lang/model/type/TypeVariable.html

The example below would be invalid -- you can only have a bound or constraints (not sure if we should come up with a new term, since a bound is also a constraint?), but not both:

T = TypeVar('T', int, str, bound=Comparable)    # Error

[gvanrossum]

Hm, I would go with bound= and forget about the lower bound. Or if you
really want the latter we can make bound= a shortcut for upper_bound=.

On Wed, May 6, 2015 at 9:11 PM, Jukka Lehtosalo notifications@github.com
wrote:

As far as I can remember, the only presented alternative has been this,
and I'm okay with it:

T = TypeVar('T', bound=Comparable)

To make it more explicit (but also more verbose and a bit technical
sounding), we could use upper_bound:

T = TypeVar('T', upper_bound=Comparable)

We could also have lower_bound for generality. It would probably be at
least marginally useful. Example:

T = TypeVar('T', lower_bound=int)

def append_first(x: List[int], y: List[T]) -> None:
y.append(x[0])

a = [1]
b = [...] # type: List[Union[int, str]]

append_first(a, b) # Okay, but only because of lower_bound

FWIW, Java uses this terminology (upper/lower bound):
http://docs.oracle.com/javase/7/docs/api/javax/lang/model/type/TypeVariable.html

The example below would be invalid -- you can only have a bound or
constraints (not sure if we should come up with a new term, since a bound
is also a constraint?), but not both:

T = TypeVar('T', int, str, bound=Comparable) # Error

—
Reply to this email directly or view it on GitHub
#59 (comment).

--Guido van Rossum (python.org/~guido)

[JukkaL]

Okay, let's go with just bound=. We can revisit this discussion later if we see compelling use cases for lower bounds. My above example was very contrived.

[gvanrossum]

This needs text to be added to the PEP and an implementation for typing.py.