Add mypy type hints?

[Daenyth]

This would help people who'd like to use sortedcontainers in a project with mypy type checking.

https://github.com/python/mypy/wiki/Creating-Stubs-For-Python-Modules

[grantjenks]

I am open to it. Pull request welcome.

[Daenyth]

Fair enough. If I can get some time to devote to it I'll see what I can do.

[solomon-b]

If this is still desired, I would like to take this issue on.

[solomon-b]

I wrote a stubfile for SortedList and SortedListWithKeys. I've never written a type hints for someone else's project so I'm hoping to get some feedback before I continue with the remaining classes.

https://github.com/ssbothwell/sorted_containers/blob/master/sortedcontainers/sortedlist.pyi

Thanks!

[Daenyth]

Off the bat I think it's probably wrong to use the Orderable type that you've made there. As far as I know, it works for any type defining inequality protocols.

The class should probably extend Generic[_A] where _A = TypeVar('_A'). Unfortunately as far as I'm aware there's no way to restrict it to be orderable types, but the alternative is to say Iterable[Any] and throw out element safety.

[solomon-b]

Thanks for the feedback. The Orderable type alias seemed questionable to me but I went with it as an initial draft.

I'm assuming that in this type of situation the type hints are meant mainly for IDE support rather then static analysis. Given that, maybe Iterable[Any] is not a big problem. I could also alias Iterable[Any] to Orderable as a hint for developers that the method is actually taking an orderable object while still not breaking static analysis.

What do you think?

[solomon-b]

PEP484 has a solution using a Type Variable with an upper bound. Any type replacing the type variable must implement the __lt__ method.

This ensures only types with inequality are passed but not that they all can be compared to each other. It sounds like this is the best solution we are going to get for the time being. I updated my stub file to include this.

On another note, mypy throws some "incompatible with supertype" errors for methods in SortedListWithKey that overload those in SortedList. An example is key() which returns None in SortedList and returns the key function in SortedListWithKey. I think this is violating the covariance rule for return types.

I also get an error about MutableSequence (which SortedList inherits from) not being defined. Do I need to import the base class into the stubfile?

[grantjenks]

Sorry for the silence on this issue. I don't remember getting email updates.

I've been working on V2 which will adopt Python 3 semantics for some APIs while still being backwards-compatible with Python 2. I'm afraid I've changed some of the parameter names which will require updating in your pyi file.

I'm also not sure how to test your pyi file.

[bryanforbes]

If you're still open to this, I can work up a PR

[grantjenks]

I'm open to it.

Still prefer pyi over source changes. And I'm not sure how to test it.

It'll be a learning experience for me.

[Daenyth]

I'm not actively doing python at the moment but do feel free to ping me with any questions, I'd be happy to help you work through any issues you come across.

[Madoshakalaka]

@grantjenks Oh, I just saw this thread after I submitted #136 . What do you think of the pull request?

[nacitar]

I'd just like to express my interest in this feature. Has there been any more progress with the pull request?

[grantjenks]

I think the realistic timeline for me understanding type hints and merging these is still months away. Given that it's already been years, I'd suggest contributing them to the typeshed at https://github.com/python/typeshed/blob/master/CONTRIBUTING.md Is there anyone willing to pursue maintaining type hints there?

[SimpleArt]

Worth noting that the main problem with adding type hints to this is the dynamic structure of all the key= cases, which seems to have been the main cause for others to fail to add type hints which behave correctly.

The biggest problem here is the complicated methods involved in SortedSet.__init__, where different methods are added depending on the type.

It probably is possible to hack together some sort of solution together, but this is really not ideal. Doing so makes it harder for those using type hints to figure out what the expected type is trying to say, which arguably defeats much of the purpose.

Likewise, the use of __new__ to instantiate different classes is going to cause confusion with x: SortedKeyList = SortedList(...).

There are ways to redesign this package in such a way that adding type hints is more sensible.

• Make SortedKeySet to alleviate the problems with SortedSet.
• Use separate constructor functions entirely, such as sorted_list(iterable, key).

For the second point, the idea is that one would add the following:

# If key is None, which it is by default, then return a SortedList.
@overload
def sorted_list(
    iterable: Optional[Iterable[T]] = ..., key: None = ...
) -> SortedList[T]: ...

# Otherwise key should be a function accepting values and returning keys.
# If provided, the iterable should match the necessary values.
# This case returns a sorted key list with the appropriate key and value types.
@overload
def sorted_list(
    iterable: Optional[Iterable[VT]] = ..., key: Callable[[VT], KT]
) -> SortedKeyList[KT, VT]: ...

# The type hints above would be added to typeshed,
# while the below implementation would be added here.
def sorted_list(iterable=None, key=None):
    if key is None:
        return SortedList(iterable)
    else:
        return SortedKeyList(iterable, key)

These constructor functions can be added without removing the current approach with __init__ and __new__, which could become deprecated and slowly removed or simply fail to support accurate typing in some cases if users choose to use the old constructors instead of the new ones.

[Jeremiah-England]

For those looking for something to use today, see these: https://github.com/h4l/sortedcontainers-stubs

They work very well for me!

[jgarvin]

I ended up writing my own SortedSet and in the process came up with a workaround for the key type. The idea is to keep the type of the key function out of the sorted set type itself (so you have SortedSet[T], not SortedSet[T, KeyType] and assert in the default key function that the type is actually Comparable. This has the downside that if you use the constructor that doesn't take a key function and it's not comparable you don't find out until runtime the first time you add an element to the container, but the other aspects of type safety are preserved (you can only put T and take T out of the container). It would be possible to do better with overloads but there is a mypy bug https://github.com/python/mypy/issues/17614.

from typing import Protocol, Self, runtime_checkable, Generic, Callable

@runtime_checkable
class Comparable(Protocol):
    def __lt__(self, other: Self) -> bool: ...
    def __eq__(self, other: Any) -> bool: ...

T = TypeVar('T') # notice there is no Comparable bound!

class SortedSet(Generic[T]):
    def __init__(self, elements: Iterable[T] = [], key: Callable[[T], Comparable] | None = None) -> None:
        self.data: list[T] = []
        self._key: Callable[[T], Comparable]
        if key is None:
            def check_comparable(x: T) -> Comparable:
                assert isinstance(x, Comparable)
                return x
            self._key = check_comparable
        else:
            self._key = key
        self.update(elements)

[vtgn]

Hi!

What's new?! Still no typing from 2017?!... :/