Skip to content

bpo-32321: Add pure Python fallback for functools.reduce #8548

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
vstinner merged 2 commits into from
Oct 25, 2018
Merged

bpo-32321: Add pure Python fallback for functools.reduce #8548

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
b00ddde
bpo-32321: Add pure Python fallback for functools.reduce
madman-bob Jul 29, 2018
b67584e
bpo-32321: Raise functools.reduce empty sequence type error in fresh …
madman-bob Jul 31, 2018
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
43 changes: 39 additions & 4 deletions Lib/functools.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -13,10 +13,6 @@
'total_ordering', 'cmp_to_key', 'lru_cache', 'reduce', 'partial',
'partialmethod', 'singledispatch', 'singledispatchmethod']

try:
from _functools import reduce
except ImportError:
pass
from abc import get_cache_token
from collections import namedtuple
# import types, weakref # Deferred to single_dispatch()
Expand Down Expand Up @@ -226,6 +222,45 @@ def __ge__(self, other):
pass


################################################################################
### reduce() sequence to a single item
################################################################################

_initial_missing = object()

@vstinner vstinner Oct 19, 2018

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

functools.py already has a sentinel singleton, _NOT_FOUND used by cached_property. Would it be possible to reuse it, instead of adding a second sentinel value?

@madman-bob madman-bob Oct 25, 2018

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Not sure how I feel about this suggestion. On the one hand, there would be a (slight) overhead reduction by reusing the same sentinel. On the other, semantically, this isn't really a _NOT_FOUND, so much as a "not given".

As these sentinels aren't part of the public interface, we could rename them into an object that semantically makes sense - but I'm loathe to touch another function, if I can help it.

@vstinner vstinner Oct 25, 2018

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ok, keep _initial_missing.


def reduce(function, sequence, initial=_initial_missing):
"""
reduce(function, sequence[, initial]) -> value

Apply a function of two arguments cumulatively to the items of a sequence,
from left to right, so as to reduce the sequence to a single value.
For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
((((1+2)+3)+4)+5). If initial is present, it is placed before the items
of the sequence in the calculation, and serves as a default when the
sequence is empty.
"""

it = iter(sequence)

if initial is _initial_missing:
try:
value = next(it)
except StopIteration:
raise TypeError("reduce() of empty sequence with no initial value") from None
else:
value = initial

for element in it:
value = function(value, element)

return value

try:
from _functools import reduce
except ImportError:
pass


################################################################################
### partial() argument application
################################################################################
Expand Down
71 changes: 39 additions & 32 deletions Lib/test/test_functools.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -746,11 +746,8 @@ def wrapper():
self.assertEqual(wrapper.attr, 'This is a different test')
self.assertEqual(wrapper.dict_attr, f.dict_attr)

@unittest.skipUnless(c_functools, 'requires the C _functools module')
class TestReduce(unittest.TestCase):
if c_functools:
func = c_functools.reduce

class TestReduce:

@vstinner vstinner Oct 19, 2018

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can you please rename it to BaseTestReduce to make it more obvious that it's not a regular test case?

@madman-bob madman-bob Oct 25, 2018

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Done this way to be consistent with the other tests.

I have no objection to this suggestion, but as it would also need to be done for TestPartial and TestCmpToKey, I feel it is out of scope for this change.

def test_reduce(self):
class Squares:
def __init__(self, max):
Expand All @@ -769,42 +766,42 @@ def __getitem__(self, i):
return self.sofar[i]
def add(x, y):
return x + y
self.assertEqual(self.func(add, ['a', 'b', 'c'], ''), 'abc')
self.assertEqual(self.reduce(add, ['a', 'b', 'c'], ''), 'abc')
self.assertEqual(
self.func(add, [['a', 'c'], [], ['d', 'w']], []),
self.reduce(add, [['a', 'c'], [], ['d', 'w']], []),
['a','c','d','w']
)
self.assertEqual(self.func(lambda x, y: x*y, range(2,8), 1), 5040)
self.assertEqual(self.reduce(lambda x, y: x*y, range(2,8), 1), 5040)
self.assertEqual(
self.func(lambda x, y: x*y, range(2,21), 1),
self.reduce(lambda x, y: x*y, range(2,21), 1),
2432902008176640000
)
self.assertEqual(self.func(add, Squares(10)), 285)
self.assertEqual(self.func(add, Squares(10), 0), 285)
self.assertEqual(self.func(add, Squares(0), 0), 0)
self.assertRaises(TypeError, self.func)
self.assertRaises(TypeError, self.func, 42, 42)
self.assertRaises(TypeError, self.func, 42, 42, 42)
self.assertEqual(self.func(42, "1"), "1") # func is never called with one item
self.assertEqual(self.func(42, "", "1"), "1") # func is never called with one item
self.assertRaises(TypeError, self.func, 42, (42, 42))
self.assertRaises(TypeError, self.func, add, []) # arg 2 must not be empty sequence with no initial value
self.assertRaises(TypeError, self.func, add, "")
self.assertRaises(TypeError, self.func, add, ())
self.assertRaises(TypeError, self.func, add, object())
self.assertEqual(self.reduce(add, Squares(10)), 285)
self.assertEqual(self.reduce(add, Squares(10), 0), 285)
self.assertEqual(self.reduce(add, Squares(0), 0), 0)
self.assertRaises(TypeError, self.reduce)
self.assertRaises(TypeError, self.reduce, 42, 42)
self.assertRaises(TypeError, self.reduce, 42, 42, 42)
self.assertEqual(self.reduce(42, "1"), "1") # func is never called with one item
self.assertEqual(self.reduce(42, "", "1"), "1") # func is never called with one item
self.assertRaises(TypeError, self.reduce, 42, (42, 42))
self.assertRaises(TypeError, self.reduce, add, []) # arg 2 must not be empty sequence with no initial value
self.assertRaises(TypeError, self.reduce, add, "")
self.assertRaises(TypeError, self.reduce, add, ())
self.assertRaises(TypeError, self.reduce, add, object())

class TestFailingIter:
def __iter__(self):
raise RuntimeError
self.assertRaises(RuntimeError, self.func, add, TestFailingIter())
self.assertRaises(RuntimeError, self.reduce, add, TestFailingIter())

self.assertEqual(self.func(add, [], None), None)
self.assertEqual(self.func(add, [], 42), 42)
self.assertEqual(self.reduce(add, [], None), None)
self.assertEqual(self.reduce(add, [], 42), 42)

class BadSeq:
def __getitem__(self, index):
raise ValueError
self.assertRaises(ValueError, self.func, 42, BadSeq())
self.assertRaises(ValueError, self.reduce, 42, BadSeq())

# Test reduce()'s use of iterators.
def test_iterator_usage(self):
Expand All @@ -818,15 +815,25 @@ def __getitem__(self, i):
raise IndexError

from operator import add
self.assertEqual(self.func(add, SequenceClass(5)), 10)
self.assertEqual(self.func(add, SequenceClass(5), 42), 52)
self.assertRaises(TypeError, self.func, add, SequenceClass(0))
self.assertEqual(self.func(add, SequenceClass(0), 42), 42)
self.assertEqual(self.func(add, SequenceClass(1)), 0)
self.assertEqual(self.func(add, SequenceClass(1), 42), 42)
self.assertEqual(self.reduce(add, SequenceClass(5)), 10)
self.assertEqual(self.reduce(add, SequenceClass(5), 42), 52)
self.assertRaises(TypeError, self.reduce, add, SequenceClass(0))
self.assertEqual(self.reduce(add, SequenceClass(0), 42), 42)
self.assertEqual(self.reduce(add, SequenceClass(1)), 0)
self.assertEqual(self.reduce(add, SequenceClass(1), 42), 42)

d = {"one": 1, "two": 2, "three": 3}
self.assertEqual(self.func(add, d), "".join(d.keys()))
self.assertEqual(self.reduce(add, d), "".join(d.keys()))


@unittest.skipUnless(c_functools, 'requires the C _functools module')
class TestReduceC(TestReduce, unittest.TestCase):

@vstinner vstinner Oct 19, 2018

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

nitpick: I suggest to move the C implementation after the Python implementation, since the Python impl is always present, whereas the other one is optional :-)

@madman-bob madman-bob Oct 25, 2018

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

As with my other comment, I have no objection to this suggestion, but as it would also need to be done for TestPartial and TestCmpToKey, I feel it is out of scope for this change.

if c_functools:
reduce = c_functools.reduce


class TestReducePy(TestReduce, unittest.TestCase):
reduce = staticmethod(py_functools.reduce)


class TestCmpToKey:
Expand Down
2 changes: 2 additions & 0 deletions Misc/NEWS.d/next/Library/2018-07-29-13-50-32.bpo-32321.hDoNKC.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,2 @@
Add pure Python fallback for functools.reduce.
Patch by Robert Wright.