TypeVar's assumed to always be of different types

[ErikBjare]

Background

I was annoyed with the default behavior of itertools.groupby (requiring input to be sorted to work correctly, and returning iterators) so I implemented a helper function that presorts and computes result immediately.

It works fine, but something unexpected happened when I wanted to give a shot at annotating it with TypeVar.

Code

Modified version of igroupby.py in my QSlang repo

from typing import List, Dict, Callable, TypeVar
from itertools import groupby

T = TypeVar('T')
K = TypeVar('K')

def igroupby(l: List[T], key: Callable[[T], K]=lambda x: x) -> Dict[K, List[T]]:
    return {k: list(v) for k, v in groupby(sorted(l, key=key), key=key)}

result1: Dict[int, List[float]] = igroupby([1.2, 1.5, 2], key=lambda x: round(x))
result2: Dict[int, List[int]] = igroupby([1, 1, 2], key=lambda x: round(x))

What is the actual behavior/output?

igroupby.py:7: error: Incompatible default for argument "key" (default has type "Callable[[T], T]", argument has type "Callable[[T], K]")
igroupby.py:7: error: Incompatible return value type (got "T", expected "K")

What is the behavior/output you expect?

I expect it to not complain about the default key function, since T and K could be the same type.

Perhaps current behavior is expected behavior, but if it is then there's a gap in my knowledge I'd like to fill.

What are the versions of mypy and Python you are using?

$ python3 -V
Python 3.7.0
$ python3 -m mypy --version
mypy 0.620

Do you see the same issue after installing mypy from Git master?

Yes.

What are the mypy flags you are using? (For example --strict-optional)

None

[Michael0x2a]

This is by design. While K could sometimes be the same type as T, it could also sometimes not be. The signature needs to be safe for all possible types T and K could take on, not just one specific instance of it.

E.g. by your type signatures, the following invocation would be legal:

igroupby([1, 2, 3], key=lambda x: "foobar")

...but clearly, there's no way of grouping a list of ints using a string key.

Mypy is reporting an error with your igroupby definition for this exact reason.

(see below)

[ErikBjare]

@Michael0x2a Thanks for replying so quickly.

Grouping a list of ints using a string key should be perfectly legal, this is intentional. There are plenty of ways to group a list of ints using a string key, I'm not sure what you're trying to say by that example. Just consider grouping integers by their first digit (or sign):

igroupby([123, 12, -32], key=lambda x: str(x)[0])

Don't ask me why this would be useful, but it seems like a bad idea to constrain the type signature of the key function unnecessarily.

While K could sometimes be the same type as T, it could also sometimes not be. The signature needs to be safe for all possible types T and K could take on, not just one specific instance of it.

For my desired behavior, it seems like it would be safe for all possible types T and K could take on. The only constrains I wish to introduce is that the dictionary keys are of the type that is returned by the key function, and that the grouped values are of the same type as elements in the passed list.

Regardless, if this annotation is not correct, how can it be correctly annotated given my desired behavior?

[ErikBjare]

A similar annotation is used in typeshed for itertools.groupby, but the issue is sidestepped by using two seperate function definitions by using overloading (one without the key argument, and one with): https://github.com/python/typeshed/blob/29522f87c3e55de384495853fea68b3929a659c2/stdlib/3/itertools.pyi#L36-L40

[Michael0x2a]

@ErikBjare -- oh wow, I badly misread your example. My bad -- please disregard my previous post.

I vaguely remember reading about a similar issue before, but I don't seem to be able to find the relevant issue.

In the meantime, you could perhaps take a page from how typeshed types itertools.groupby and use an overload -- one for when the key is present, and another for when it isn't.

[ilevkivskyi]

I think this is a duplicate of #3737. See that issue for suggestions of workarounds.

[ErikBjare]

That did indeed work, see this commit: https://github.com/ErikBjare/QSlang/blob/01b12fdd5183b41779e27478c2317730ee2ea11b/igroupby.py

Thanks @Michael0x2a and @ilevkivskyi!