mypy can't infer type for functools.reduce

[kamahen]

The attached program has three methods (C.m, C.m_bad1, C.m_bad2) that compute the same value; only one of them is accepted by mypy (and by sheer coincidence, C.m is the style that Guido prefers and the others are a style he doesn't). I looked at the typeshed definition of functools.reduce,and it appears to be correct.

Issue 4226 suggests that the lambda might be the problem; but that seems to only shift the problem (C.m_bad1 uses a lambda and C.m_bad2 has the lambda rewritten as a function.

The error messages go away when I change result = ... to result: List[B] = ..., but that type annotation shouldn't be necessary, from looking at the definition of reduce) (In my original program, I got additional error messages, so I might have over-simplified this example.)

Overloading of reduce in functools.pyi doesn't seem to be the problem -- I tried using my own definition of reduce but without the overloading, and got the same error messages.

(For background: this example is a simplified version of some code that converts objects of class C to objects of class B, with both classes having many subclasses.)

Here are the error messages I got (program is attached as a TXT file):

reduce_bug.py: note: In member "m_bad1" of class "C":
reduce_bug.py:37: error: Need type annotation for 'result'
reduce_bug.py:37: error: Unsupported operand types for + ("List[<nothing>]" and "List[B]")
reduce_bug.py: note: In member "m_bad2" of class "C":
reduce_bug.py:42: error: Need type annotation for 'result'
reduce_bug.py:42: error: Argument 1 to "reduce" has incompatible type "Callable[[List[B], C], List[B]]"; expected "Callable[[List[<nothing>], C], List[<nothing>]]"

This was run with mypy --python-version=3.6 --strict-optional --check-untyped-defs --warn-incomplete-stub --warn-no-return --no-incremental --disallow-any-unimported --show-error-context --implicit-optional --strict --disallow-incomplete-defs /tmp/reduce_bug

reduce_bug.py.txt

[gvanrossum]

I believe there's a bug related to lambda here. I expect that if you replace it with an explicitly typed def it might pass.

[kamahen]

I don't think it's entirely due to lambda ... if you look at m_bad2, you'll see that it doesn't use lambda (there might be two bugs here -- one for lambda and one for the type inferencing for functools.reduce).

Here are lines 37 through 49 ... you can see that both methods generate error messages, although they messages are different.

    def m_bad1(self) -> B:
        result = functools.reduce(lambda result, item: result + [item.m()],
                                  self.f_list, [])
        return B(result)

    def m_bad2(self) -> B:
        result = functools.reduce(_combine, self.f_list, [])
        return B(result)


def _combine(result: List[B], item: C) -> List[B]:
    # See https://github.com/python/mypy/issues/4226
    return result + [item.m()]

Here are the error messages:

reduce_bug.py: note: In member "m_bad1" of class "C":
reduce_bug.py:37: error: Need type annotation for 'result'
reduce_bug.py:37: error: Unsupported operand types for + ("List[<nothing>]" and "List[B]")
reduce_bug.py: note: In member "m_bad2" of class "C":
reduce_bug.py:42: error: Need type annotation for 'result'
reduce_bug.py:42: error: Argument 1 to "reduce" has incompatible type "Callable[[List[B], C], List[B]]"; expected "Callable[[List[<nothing>], C], List[<nothing>]]"

[gvanrossum]

For reference, here's the full example (I deleted code from the end that seems immaterial to mypy):

import functools
from typing import List, Sequence


class B:
    def __init__(self, x_list: Sequence['B']) -> None:
        self.x_list = x_list

    def __repr__(self) -> str:
        return '{}([{}])'.format(self.__class__.__name__, ', '.join(
            repr(x) for x in self.x_list))


class B1(B):
    def __init__(self, v: str) -> None:
        self.v = v

    def __repr__(self) -> str:
        return '{}({})'.format(self.__class__.__name__, repr(self.v))


class C:
    def __init__(self, f_list: Sequence['C']) -> None:
        self.f_list = f_list

    def __repr__(self) -> str:
        return '{}([{}])'.format(self.__class__.__name__, ', '.join(
            repr(f) for f in self.f_list))

    def m(self) -> B:
        result = []  # type: List[B]
        for item in self.f_list:
            result += [item.m()]
        return B(result)

    def m_bad1(self) -> B:
        result = functools.reduce(lambda result, item: result + [item.m()],  # Error here
                                  self.f_list, [])
        return B(result)

    def m_bad2(self) -> B:
        result = functools.reduce(_combine, self.f_list, [])  # Error here
        return B(result)


def _combine(result: List[B], item: C) -> List[B]:
    # See https://github.com/python/mypy/issues/4226
    return result + [item.m()]

[gvanrossum]

Hm, actually both errors go away when I replace the [] passed as the third arg to reduce() with

    init = []  # type: List[B]

[kamahen]

I could also make the error go away by adding # type: List[B] to the reduce() lines or by adding the var annotation List[B]. Or by wrapping the reduce() lines in a function that specified the return type (which I presume mypy treats the same as the type annotation).

[gvanrossum]

Can you find a more minimal example that doesn't depend on the builtin reduce? I've got a feeling it's got to do with Sequence vs. List and a generic Callable.

[kamahen]

This feels like it's related to needing the var annotation on result in this code, because mypy is not able to infer the type of []:

    def m(self) -> B:
        result = []  # type: List[B]
        for item in self.f_list:
            result += [item.m()]
        return B(result)

[kamahen]

I tried making my own version of reduce (with the same type annotation as in typeshed):

_T = TypeVar("_T")
_S = TypeVar("_S")
def my_reduce(function: Callable[[_T, _S], _T], sequence: Iterable[_S],
              initial: _T) -> _T:
    return functools.reduce(function, sequence, initial)

and then changing the Iterable[_S] to Sequence[_S] and List[_S] and that didn't help.

[kamahen]

This seems to be a simpler example (I removed the Callable and hard-coded it):

import functools
from typing import List, Sequence, TypeVar, Iterable

_S = TypeVar('_S')
_T = TypeVar('_T')
def my_reduce(sequence: List[_S], initial: _T) -> _T:
    return functools.reduce(_combine, sequence, initial)

def _combine(result: List[str], item: int) -> List[str]:
    return result + [str(item)]

# reveal_type(_combine) -
#   def (result: builtins.list[builtins.str], item: builtins.int) -> builtins.list[builtins.str]

def foo(items: List[int]) -> List[str]:
    return my_reduce(items, [])

print(foo([1,2,3,4]))

Which causes this message:

/tmp/z3.py:7: error: Argument 1 to "reduce" has incompatible type "Callable[[List[str], int], List[str]]"; expected "Callable[[_T, _S], _T]"

[gvanrossum]

What if you write your own reduce() that's not overloaded? (It doesn't have to be functional as long as it matches the stdlib signature.)

In any case it's clear that you've hit upon a case where the type solver gets its knickers in a knot. That's really old code and probably only @JukkaL knows it well enough to be able to make use of this bug report to fix something.

[kamahen]

Writing my own reduce got rid of the complain, although instead I got an error inside my reduce. ;)

/tmp/z3.py: note: In function "my_reduce":
/tmp/z3.py:10: error: Incompatible types in assignment (expression has type "List[str]", variable has type "_T")
/tmp/z3.py:10: error: Argument 1 to "_combine" has incompatible type "_T"; expected "List[str]"
/tmp/z3.py:10: error: Argument 2 to "_combine" has incompatible type "_S"; expected "int"

Here's the full code (line 10 is marked with a comment):

import functools
from typing import List, Sequence, TypeVar, Iterable

_S = TypeVar('_S')
_T = TypeVar('_T')
def my_reduce(sequence: List[_S], initial: _T) -> _T:
    # return functools.reduce(_combine, sequence, initial)
    result = initial
    for item in sequence:
        result = _combine(result, item)  # <==== Line 10
    return result

def _combine(result: List[str], item: int) -> List[str]:
    return result + [str(item)]

# reveal_type(_combine) -
#   def (result: builtins.list[builtins.str], item: builtins.int) -> builtins.list[builtins.str]

def foo(items: List[int]) -> List[str]:
    return my_reduce(items, [])

print(foo([1,2,3,4]))

[gvanrossum]

The problem on line 10 in your last example is because _combine() isn't generic.

Looking back, the same is the case in the previous example.

These two errors look justified to me.

But the original error is more complicated, and here's a repro:

from typing import *

T = TypeVar('T')
S = TypeVar('S')

def reduce(func: Callable[[T, S], T], seq: Iterable[S], init: T) -> T: ...

def combine(res: List[str], item: int) -> List[str]: ...

def error(items: Sequence[int]) -> None:
    result = reduce(combine, items, [])  # <-- errors here

The errors are closer to your original:

_.py:11: error: Need type annotation for 'result'
_.py:11: error: Argument 1 to "reduce" has incompatible type "Callable[[List[str], int], List[str]]"; expected "Callable[[List[<nothing>], int], List[<nothing>]]"

[kamahen]

I can also get this error (unless I've made another mistake with type annotations):

/tmp/z4.py: note: In function "my_reduce":
/tmp/z4.py:10: error: Incompatible types in assignment (expression has type "List[<nothing>]", variable has type "_T")
/tmp/z4.py:10: error: Argument 1 to "_combine" has incompatible type "_T"; expected "List[<nothing>]"

with this source:

from typing import *
_S = TypeVar('_S')
_T = TypeVar('_T')

def my_reduce(sequence: List[_S], initial: _T) -> _T:
# def my_reduce(sequence: List[int], initial: List[str]) -> List[str]:
    result = initial
    for item in sequence:
        result = _combine(result, item)  # <==== Line 10
    return result

def _combine(result: List[_T], item: _S) -> List[_T]:
# def _combine(result: List[str], item: int) -> List[str]:
    # return result + [str(item)]
    return result

[kamahen]

Is this a correct summary? -- mypy has a bug(s) that's exposed by the code examples in this thread, and @JukkaL might eventually dig into the grungy old code and figure out the problem.

[gvanrossum]

Yes.

[kamahen]

Can this be marked as a bug, please? (I don't seem to have the authority to add a label)

[ghost]

Is this related ?
I just started learning python today & found this problem :(

[imthejungler]

Hi team!
I have a similar problem. When I try to use a derived UserDict, it tells me:
Argument "destination" to "_generate" of "DictMapper" has incompatible type "Mapping[str, Any]"; expected "_RecursiveDictMap"

this is the signature of me _generate method

def _generate(source: _RecursiveDict, destination: _RecursiveDictMap, mapping: AttrMapping) -> _RecursiveDictMap:

And here is the place where I'm having problems(where it says # type: ignore :

return dict(
            reduce(function=lambda destination, mapping: DictMapper._generate(source=source,
                                                                              destination=destination,  # type: ignore
                                                                              mapping=mapping),
                   sequence=self._mappings,
                   initial=_RecursiveDictMap())
        )

Thx!

[tigerjack]

I still have this issue. MWE

import functools
import operator
tup1 = [(1, 2), (3, 4)]
functools.reduce(operator.concat, tup1)  

returns

error Argument 1 to "reduce" has incompatible type "Callable[[Sequence[_T], Sequence[_T]],
Sequence[_T]]"; expected "Callable[[Tuple[int, int], Tuple[int, int]], Tuple[int, int]]"

[mluscon]

Still present in mypy 1.8.0