Apparent false positive when using reduce with dictionaries

[edwardcwang]

Python 3.6.3, mypy 0.521.

When using reduce on an Iterable/List of dictionaries, mypy seems to be confused about the signature of the function and seems to be unpacking the dictionary into an iterable of tuples. The following example appears to conform to the reduce function's parameters, so no errors should be appearing.

https://docs.python.org/3.6/library/functools.html#functools.reduce

test.py:14: error: Argument 1 to "reduce" has incompatible type Callable[[Dict[Any, Any], Dict[Any, Any]], Dict[Any, Any]]; expected Callable[[Iterable[Tuple[Any, Any]], Dict[Any, Any]], Iterable[Tuple[Any, Any]]]

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from functools import reduce

from typing import Iterable

def update(ccc: dict, meta: dict) -> dict:
    foo = dict(ccc)
    foo.update(meta)
    return foo

def reduce_func(configs: Iterable[dict]) -> dict:
    output = dict(reduce(update, configs, {})) # type: dict
    return output

print(reduce_func([{"a": 1}, {"b": 2}]))

[ethanhs]

Repro'd on master. A very similar and slightly smaller issue:

from functools import reduce
from typing import Iterable, Dict

def update(ccc: Dict[str, int], meta: Dict[str, int]) -> Dict[str, int]:
    ...

def reduce_func(configs: Iterable[Dict]) -> Dict:
    b: Dict[str, int] = {}
    output = dict(reduce(update, configs, b))
    return output

gives

error: Argument 1 to "reduce" has incompatible type "Callable[[Dict[str, int], Dict[str, int]], Dict[str, int]]"; expected "Callable[[Mapping[str, int], Dict[Any, Any]], Mapping[str, int]]"

Since Mapping[KT, VT] and Iterable[Tuple[KT,VT]] are both the types of dict()'s initializer, I can surmise that mypy is over-using context, or falling back to it, and using the type of dict()'s initializer.

@edwardcwang as a work around, you can change reduce_func to this:

def reduce_func(configs: Iterable[dict]) -> dict:
    output = reduce(update, configs, {}) # type: dict
    return dict(output)

[gvanrossum]

A reduced version, without depending on typeshed's definitions for dict or reduce:

from typing import *
T = TypeVar('T')
K = TypeVar('K')
V = TypeVar('V')
def r(func: Callable[[T], None]) -> T: ...  # reduce
def d(map: Mapping[K, V]) -> None: pass  # dict
A = Dict[str, int]
def f(a: A) -> None: ...  # update
def g() -> None:  # reduce_func
    d(r(f))  # <-- error here

This gives

__tmp__.py:10: error: Argument 1 to "r" has incompatible type "Callable[[Dict[str, int]], None]"; expected "Callable[[Mapping[str, int]], None]"

This rules out the use of overloads in the original examples -- it's purely a flaw in the solving of generics. IIRC this is a known weakness.

[edwardcwang]

Another possible example of the same problem, this time with List/Iterable:

from typing import *
from functools import reduce

_T = TypeVar('_T')
_S = TypeVar('_S')
def r(function: Callable[[_T, _S], _T], sequence: Iterable[_S], initial: _T) -> _T:
    return reduce(function, sequence, initial)

def func(a: List[str], b: List[str]) -> List[str]:
    return a + b

list_of_lists = [['1', '2', '3'], ['a', 'b']]  # type: List[List[str]]
empty = []  # type: List[str]
result = list(r(func, list_of_lists, empty))  # type: List[str]
# ^ Argument 1 to "r" has incompatible type "Callable[[List[str], List[str]], List[str]]"; expected "Callable[[Iterable[str], List[str]], Iterable[str]]"
# Incorrectly infers the type of _T to be Iterable[str] instead of List[str]

print(str(result))