Difference between revisions of "Reduce"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][checked revision]
m ({{C-class}})
m (add_together: change section header)
 
(2 intermediate revisions by one user not shown)
Line 1: Line 1:
 +
{{DISPLAYTITLE:reduce}}
 
{{C-class}}
 
{{C-class}}
'''Reduce''' is a [[higher-order function]] that is either a [https://docs.python.org/2/library/functions.html#reduce built-in function in Python 2.7] or can be [[import|imported]] from [https://docs.python.org/3.2/library/functools.html functools in Python 3.2+].
+
'''reduce''' is a [[higher-order function]] that is either built-in in Python 2 or can be [[import]]ed from <code>functools</code> in Python 3.
  
Given a ''two-argument'' [[function]], an iterable, and (optionally) an initalizer, <code>reduce</code> applies the function to each item pair in the sequence cumulatively, and returns a single value.  
+
Given a ''two-argument'' [[function]], an iterable, and optionally an initalizer, <code>reduce</code> applies the function to each item pair in the sequence cumulatively and returns a single value. More precisely, <code>reduce</code> will take the first two elements of the iterable, apply the function to them, and reach a result. It will then apply the function to this result and the third element, apply the function to the result of that and the fourth element, and so on, until it reaches the end of the iterable. The return value will be the final result.
 
+
<code>Reduce</code> will take the first two elements of the iterable, apply the function to them, and reach a result. It will then apply the function to this result and the third element, move on to the fourth element, and so on, until it reaches the end of the iterable. The final result will be the single return value.
+
  
 
==Form==
 
==Form==
The most general form of the <code>reduce</code> function is as follows:
+
The most general form of the <code>reduce</code> function is:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
 
reduce(func, iter)
 
reduce(func, iter)
 
</syntaxhighlight>
 
</syntaxhighlight>
 
+
where <code>func</code> is the 2-argument function and <code>iter</code> is the iterable being processed.
with <code>func</code> being the 2-argument function given, and <code>iter</code> being the iterable being processed.
+
  
 
==Examples==
 
==Examples==
===add_together===
+
===Sum===
For the most basic example, we will attempt to add all elements of a list together. We'll create a starter function, <code>add_together</code>, and the list <code>my_list</code> below.  
+
We can use <code>reduce</code> to sum all elements of a list. We define the following:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
def add_together(x, y):
+
def add(x, y):
   return x+y
+
   return x + y
my_list = [1, 2, 3, 4, 5]
+
lst = [1, 2, 3, 4, 5]
 
</syntaxhighlight>
 
</syntaxhighlight>
  
If we apply <code>reduce</code> to the above and apply them as arguments, we can expect:
+
Applying <code>reduce</code>:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
>>>reduce(add_together, my_list)
+
>>> reduce(add, lst)
 
15
 
15
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
Behind the scenes, <code>reduce</code> is actually computing <code>add(add(add(add(1, 2), 3), 4), 5)</code> or <code>((((1 + 2) + 3) + 4) + 5)</code>.
 +
 +
== Sources ==
 +
* https://docs.python.org/2/library/functions.html#reduce
 +
* https://docs.python.org/3.2/library/functools.html

Latest revision as of 14:23, 4 July 2014

reduce is a higher-order function that is either built-in in Python 2 or can be imported from functools in Python 3.

Given a two-argument function, an iterable, and optionally an initalizer, reduce applies the function to each item pair in the sequence cumulatively and returns a single value. More precisely, reduce will take the first two elements of the iterable, apply the function to them, and reach a result. It will then apply the function to this result and the third element, apply the function to the result of that and the fourth element, and so on, until it reaches the end of the iterable. The return value will be the final result.

Form

The most general form of the reduce function is:

reduce(func, iter)

where func is the 2-argument function and iter is the iterable being processed.

Examples

Sum

We can use reduce to sum all elements of a list. We define the following:

def add(x, y):
   return x + y
lst = [1, 2, 3, 4, 5]

Applying reduce:

>>> reduce(add, lst)
15

Behind the scenes, reduce is actually computing add(add(add(add(1, 2), 3), 4), 5) or ((((1 + 2) + 3) + 4) + 5).

Sources