{:check ["true"]}

Index

Reduce

A common pattern is to update some state value during the iteration of a list.
```
xs = [1,2,3,4,5]
total = 0
for x in xs:
    total = total + x
```
This is known as the reduce pattern, in which the list xs is reduced to total.

This can be visualized as follows:

    0    +   1   +   2   +   3 ...
   ---  ---  ---------------------
    |    |          |
    |    |          |
    |    |          +---- the sequence of elements
    |    | 
initial  +--- state update function
value         (known as the reducer)

So, the reduce pattern can be completely characterized by:
- the initial value of the state
- the reducer function
- the sequence of elements to be reduced.

Python provides a higher order function functools.reduce to perform reduce.

from functools import reduce

def reduce_fn(x, y):
    return x + y

total = reduce(reduce_fn, [1,2,3,4,5], 0)

Reduce without initial state value

Sometimes, we don't need to explicitly provide the initial state value as the first element in the sequence can be used as the initial state value.

     1    +   2   +   3   +   4 ...
    ---  ---          
    -|----|------------------------
     |    |          |
     |    |          |
     |    |          +---- the sequence of elements
     |    | 
 initial  +--- reducer
 value

The initial value for functools.reduce is optional.

from functools import reduce

def reduce_fn(x, y):
    return x + y

total = reduce(reduce_fn, [1,2,3,4,5])

Reduce

More advanced reducers

We can compute the sum of all positive elements in a list of numbers.

split=7

def f(state, x):
    return (state + x) if x > 0 else state

xs = [1, -1, 3, 2, -2, -10, 1]
reduce(f, xs)

xs = [1, -1, 3, 2, -2, -10, 1]
total = 0
for x in xs:
    if x > 0:
        total += x

We can compute the maximum value of a list of numbers.

xs = [1, -1, 3, 2, -2, -10, 1]
reduce(max, xs)

More advanced state data structure

Suppose that we are working with a list of dictionaries.

students = [
    {"name": "Jack", "age": 20, "grade": 90},
    {"name": "Jill", "age": 18, "grade": 89},
    {"name": "Joe", "age": 19, "grade": 83}
]

We might want to get the age range:
```
{
    min_age: 18,
    max_age: 20
}
```

We need to design the reducer function:

def f(state, student):
    if state is None:
        state = {
            'min_age': student['age'],
            'max_age': student['age']
        }
    else:
        state['min_age'] = min(state['min_age'], student['age'])
        state['max_age'] = max(state['max_age'], student['age'])
    return state

Viola, we can quickly get the range of students' age using reduce:
```
reduce(f, students, None)
```