Why doesn't this higher-order function pass static type checking in mypy?

Question

I'm trying to get to grips with mypy. As an exercise, I'm trying to figure out the right type annotations for some common higher-order functions. But I don't quite understand why the following code doesn't type check.

test.py

from typing import Iterable, TypeVar, Callable

T1 = TypeVar('T1')
T2 = TypeVar('T2')

def chain(
        functions: Iterable[Callable[[T1], T1]]
    ) -> Callable[[T1], T1]:

    def compose(
            f: Callable[[T1], T1],
            g: Callable[[T1], T1]
        ) -> Callable[[T1], T1]:
        def h(x: T1) -> T1:
            return g(f(x))
        return h

    def identity(x: T1) -> T1:
        return x

    return reduce(functions, compose, identity)

def reduce(
        items: Iterable[T1], 
        op:    Callable[[T2, T1], T2],
        init:  T2
    ) -> T2:
    for item in items:
        init = op(init, item)
    return init

def add_one(x):
    return x + 1

def mul_two(x):
    return x * 2

assert chain([add_one, mul_two, mul_two, add_one])(7) == 33

The code runs correctly in python, but mypy test.py produces the following error message (I've formatted it slightly for readability):

test.py:21: error: Argument 2 to "reduce" has incompatible type
"Callable[
  [Arg(Callable[[T1], T1], 'f'), Arg(Callable[[T1], T1], 'g')],
  Callable[[T1], T1]
]"; 
expected 
"Callable[
  [Callable[[T1], T1], Callable[[T1], T1]], 
  Callable[[T1], T1]
]"

I'm not sure where Arg is coming from. I couldn't find anything about it in the documentation for typing, and the only reference to it in the mypy documentation says that it is a deprecated feature.

My only thought is that it might have something to do with the fact that compose produces a closure.

This is mypy version 0.720 and Python version 3.7.3.

---

Update

So it seems as if the error message might be misleading. After adding the following code, the error disappears:

from typing import overload

@overload
def reduce(
        items: Iterable[T1],
        op:    Callable[[T1, T1], T1],
        init:  T1
    ) -> T1: ...

@overload
def reduce(
        items: Iterable[T1],
        op:    Callable[[T2, T1], T2],
        init:  T2
    ) -> T2: ...

But it's still not clear to me what is going on here.

Answer 1

This is a strange issue, which seems to be a bug in mypy, because pytype and pyre correctly checks your code.

Mypy fails with your code but successfully checks the code if you change your identity function to:

def identity(x: T1, /) -> T1:
  return x

The only difference is that the function now only accepts positional arguments.

Note, I'd use functools.reduce instead, so that you can leverage typings from typeshed. In that case you would need to call return reduce(compose, functions, identity).

BONUS: There's also a strange pyre issue, if you move the identity function outside compose, then I get an error

 Mutually recursive type variables [36]: Solving type variables for call `reduce` led to infinite recursion.

But get fixed if you replace your reduce with functools.reduce.