Using the functional paradigm

In a functional sense, the sum of the multiples of three and five can be defined in two parts:

• The sum of a sequence of numbers
• A sequence of values that pass a simple test condition, for example, being multiples of three and five

The sum of a sequence has a simple, recursive definition:

def sumr(seq): 
    if len(seq) == 0: return 0 
    return seq[0] + sumr(seq[1:]) 

We've defined the sum of a sequence in two cases: the base case states that the sum of a zero length sequence is 0, while the recursive case states that the sum of a sequence is the first value plus the sum of the rest of the sequence. Since the recursive definition depends on a shorter sequence, we can be sure that it will (eventually) devolve to the base case.

Here are some examples of how this function works:

>>> sumr([7, 11])
18
>>> 7+sumr([11])
18
>>> 18+sumr([])
0

The first example computes the sum of a list with multiple items. The second example shows how the recursion rule works by adding the first item, seq[0], to the sum of the remaining items, sumr(seq[1:]). Eventually, the computation of the result involves the sum of an empty list, which is defined as zero.

The + operator on the last line of the preceding example and the initial value of 0 in the base case characterize the equation as a sum. If we change the operator to * and the initial value to 1, it would just as easily compute a product. We'll return to this simple idea of generalization in the following chapters.

Similarly, a sequence of values can have a simple, recursive definition, as follows:

def until(n, filter_func, v): 
    if v == n: return [] 
    if filter_func(v): return [v] + until(n, filter_func, v+1) 
    else: return until(n, filter_func, v+1) 

In this function, we've compared a given value, v, against the upper bound, n. If v reaches the upper bound, the resulting list must be empty. This is the base case for the given recursion.

There are two more cases defined by the given filter_func() function. If the value of v is passed by the filter_func() function, we'll create a very small list, containing one element, and append the remaining values of the until() function to this list. If the value of v is rejected by the filter_func() function, this value is ignored and the result is simply defined by the remaining values of the until() function.

We can see that the value of v will increase from an initial value until it reaches n, assuring us that we'll reach the base case soon.

Here's how we can use the until() function to generate the multiples of three and five. First, we'll define a handy lambda object to filter values:

mult_3_5 = lambda x: x%3==0 or x%5==0 

(We will use lambdas to emphasize succinct definitions of simple functions. Anything more complex than a one-line expression requires the def statement.)

We can see how this lambda works from Command Prompt in the following example:

>>> mult_3_5(3)
True
>>> mult_3_5(4)
False
>>> mult_3_5(5)
True

This function can be used with the until() function to generate a sequence of values, which are multiples of three and five.

The until() function for generating a sequence of values works as follows:

>>> until(10, lambda x: x%3==0 or x%5==0, 0)
[0, 3, 5, 6, 9]

We can use our recursive sum() function to compute the sum of this sequence of values. The various functions such as sum(), until(), and mult_3_5() are defined as simple recursive functions. The values are computed without resorting to using intermediate variables to store the state.

We'll return to the ideas behind this purely functional, recursive definition in several places. It's important to note here that many functional programming language compilers can optimize these kinds of simple recursive functions. Python can't do the same optimizations.