bpo-32321: Add pure Python fallback for functools.reduce (GH-8548)
diff --git a/Lib/functools.py b/Lib/functools.py
index 51048f5..39a4af8 100644
--- a/Lib/functools.py
+++ b/Lib/functools.py
@@ -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()
@@ -227,6 +223,45 @@
################################################################################
+### reduce() sequence to a single item
+################################################################################
+
+_initial_missing = object()
+
+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
################################################################################
diff --git a/Lib/test/test_functools.py b/Lib/test/test_functools.py
index 200a5eb..ffbd0fc 100644
--- a/Lib/test/test_functools.py
+++ b/Lib/test/test_functools.py
@@ -746,11 +746,8 @@
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:
def test_reduce(self):
class Squares:
def __init__(self, max):
@@ -769,42 +766,42 @@
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):
@@ -818,15 +815,25 @@
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):
+ if c_functools:
+ reduce = c_functools.reduce
+
+
+class TestReducePy(TestReduce, unittest.TestCase):
+ reduce = staticmethod(py_functools.reduce)
class TestCmpToKey:
diff --git a/Misc/NEWS.d/next/Library/2018-07-29-13-50-32.bpo-32321.hDoNKC.rst b/Misc/NEWS.d/next/Library/2018-07-29-13-50-32.bpo-32321.hDoNKC.rst
new file mode 100644
index 0000000..82ee39f
--- /dev/null
+++ b/Misc/NEWS.d/next/Library/2018-07-29-13-50-32.bpo-32321.hDoNKC.rst
@@ -0,0 +1,2 @@
+Add pure Python fallback for functools.reduce.
+Patch by Robert Wright.