Functional programming

Function is a kind of encapsulation supported by Python built-in. We can decompose complex tasks into simple tasks by disassembling large pieces of code into functions and calling functions layer by layer. This decomposition can be called process oriented programming. Function is the basic unit of process oriented programming.

Functional Programming (please note that there is another word * * "formula") - Functional Programming, although it can also be attributed to process oriented programming, its idea is closer to mathematical calculation * *.

We must first understand the concepts of * * Computer and Compute * *.

• At the computer level, the CPU executes the instruction code of addition, subtraction, multiplication and division, as well as various condition judgment and jump instructions, so the assembly language is the language closest to the computer.

• Calculation refers to the calculation in the mathematical sense. The more abstract the calculation is, the farther it is from the computer hardware.

Corresponding to the programming language, the lower the language, the closer it is to the computer, the lower the degree of abstraction and the higher the execution efficiency, such as C language; The more advanced the language is, the closer it is to computing. It has a high degree of abstraction and low execution efficiency, such as Lisp language.

To sum up:

	Low level language	high-level language
characteristic	Close to computer	Close calculation (in mathematical sense)
Degree of abstraction	low	high
Execution efficiency	high	low
example	Compilation and C	Lisp

Functional programming is a programming paradigm with a high degree of abstraction. The functions written in pure functional programming language have no variables. Therefore, as long as the input of any function is determined, the output is determined. This pure function is called no side effects. In the programming language that allows the use of variables, because the variable state inside the function is uncertain, the same input may get different outputs. Therefore, this function has side effects.

A feature of functional programming is that it allows the function itself to be passed into another function as a parameter and return a function!

Python provides only partial support for functional programming. Because Python allows variables, Python is not a purely functional programming language.

catalogue

• Three characteristics of functional programming
• Several programming techniques
• Several benefits of functional programming
  • Simple example
• Higher order function
  • Variables can point to functions
  • The function name is also a variable
  • Incoming function
  • map/reduce
  • filter
  • sorted
• Return function
  • Function as return value
  • closure
• Anonymous function
• Decorator
  • decorator with parameters
  • Attribute replication
  • practice
• Partial function

Three characteristics of functional programming

1. immutable data
   
   Variables are immutable, or there are no variables, only constants. When the input of functional programming is determined, the output is determined. The variables inside the function have nothing to do with those outside the function and will not be affected by external operations.

2. first class functions
   
   The first type of function (also known as high-order function) means that functions can be used like variables, and can be created, modified, passed and returned like variables. This allows us to break a large piece of code into functions and call them layer by layer. This process oriented writing method is more intuitive than loop.

3. Tail recursive optimization
   
   As mentioned in the recursive function in the previous chapter, it returns the function itself rather than the expression. Unfortunately, this feature is not available in Python.

Several techniques of functional programming

1. map & reduce
   
   The most common technology of functional programming is to do Map and Reduce operations on a set. Compared with the traditional process oriented writing method, it is easier to read the code (instead of using a pile of for and while loops to toss data, more abstract Map functions and Reduce functions are used).

2. pipeline
   
   The meaning of this technology is to turn function instances into actions one by one, then put a group of actions into an array or list to form an action list, and then transfer the data to the action list. The data is operated by each function in sequence like a pipeline, and finally get the desired result.

3. recursing
   
   The biggest advantage of recursion is to simplify the code. It can describe a complex problem with very simple code. Note: the essence of recursion is to describe problems, which is the essence of functional programming.

4. currying
   
   Decompose multiple parameters of a function into multiple functions, and then encapsulate the function in multiple layers. Each layer of function returns a function to receive the next parameter. In this way, multiple parameters of the function can be simplified (reduce the number of parameters of the function).

5. higher order function
   
   High order function: the so-called high-order function is to encapsulate the incoming function when the function is a parameter, and then return the encapsulated function. The phenomenon is that functions pass in and out.

A little supplement to currying, for example:

def pow(i, j):
    return i**j

def square(i):
    return pow(i, 2)

Here we decompose the parameter j of the original square function, which returns the power function pow function and encapsulates the power in it, so as to reduce the parameters required for square calculation.

Some concepts of functional programming can be understood Fool functional programming Or the original English version Functional Programming For The Rest of Us.

Several benefits of functional programming

1. parallelization
   
   In the parallel environment, there is no need for synchronization or mutual exclusion between threads (variables are internal and do not need to be shared).

2. lazy evaluation
   
   An expression does not evaluate immediately after it is bound to a variable, but when the value is taken.

3. Determinism determinism
   
   The input is determined and the output is determined.

Simple example

In the past, procedural oriented programming required the introduction of additional logic variables and the use of loops:

upname =['HAO', 'CHEN', 'COOLSHELL']
lowname =[]
for i in range(len(upname)):
    lowname.append( upname[i].lower() )

Functional programming is very simple and easy to understand:

def toUpper(item):
  return item.upper()

upper_name = map(toUpper, ["hao", "chen", "coolshell"])
print upper_name

Let's take another example of calculating the average of all positive numbers in a list:

num =[2, -5, 9, 7, -2, 5, 3, 1, 0, -3, 8]
positive_num_cnt = 0
positive_num_sum = 0
for i in range(len(num)):
    if num[i] > 0:
        positive_num_cnt += 1
        positive_num_sum += num[i]

if positive_num_cnt > 0:
    average = positive_num_sum / positive_num_cnt

print average

If functional programming is used:

positive_num = filter(lambda x: x>0, num)
average = reduce(lambda x,y: x+y, positive_num) / len( positive_num )

It can be seen that functional programming reduces the use of variables, reduces the possibility of bugs, and makes maintenance more convenient. Higher readability and simpler code.

For more examples and analysis, see Functional programming.

Higher order function

The high-order function features in functional programming have been mentioned earlier. This section will describe in more detail how to use them in Python.

Variables can point to functions

>>> abs
<built-in function abs>
>>> f = abs
>>> f
<built-in function abs>
>>> f(-10)
10

This example shows that in Python, variables can point to functions, and such assigned variables can be used as aliases of functions.

The function name is also a variable

>>> abs = 10
>>> abs(-10)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'int' object is not callable

Here, the abs function is assigned a value of 10. After this assignment, the abs becomes an integer variable, pointing to the int object 10 instead of the original function. So it can no longer be used as a function.

To restore the abs function, restart the Python interactive environment. abs function definition__ builtin__ In the module, to make the modification of the direction of abs variable effective in other modules, use__ builtin__.abs = 10 is OK. Of course, actually writing code should never do this

Incoming function

Functions can be passed as parameters, and the function receiving such parameters is called high-order function. Simple example:

def add(x, y, f):
    return f(x) + f(y)

>>> add(-5, 6, abs)
11

Here, the abs function can be passed as a parameter into the add function we write. The add function is a high-order function.

map/reduce

The map() function and the reduce() function are two built-in functions (BIFS) of Python.

map function

The map() function receives two parameters, one is a function and the other is an iteratable object. Map applies the incoming function to each element of the sequence in turn, and returns the result as an Iterator object (inert sequence, which can be converted into list output by list). For example:

>>> def f(x):
...     return x * x
...
>>> r = map(f, [1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> list(r)
[1, 4, 9, 16, 25, 36, 49, 64, 81]

Here, the iterator object is directly converted into a list using the list() function.

The write loop can achieve the same effect, but it is obviously not as intuitive as the map() function. As a high-order function, map() function greatly simplifies the code and is easier to understand.

>>> list(map(str, [1, 2, 3, 4, 5, 6, 7, 8, 9]))
['1', '2', '3', '4', '5', '6', '7', '8', '9']

Converting a list of integers to a list of characters requires only one line of code.

reduce function

Reduce receives two parameters, one is a function (assuming the function is called f) and the other is an iteratable object (assuming L). Function f must receive two parameters. The reduce function will pass the value returned by function f last time and the next element of l into f every time. Until all elements in l have participated in the operation, it will return the last value returned by function f (the first two elements of l will be passed in the first time).

>>> from functools import reduce
>>> def add(x, y):
...     return x + y
...
>>> reduce(add, [1, 3, 5, 7, 9])
25

Here is an example of the simplest sequence summation (of course, it is more convenient for us to directly use the sum() function, which is just for example). Here, the reduce function applies add to the first two elements of the sequence each time and returns the result to the head of the sequence until there is only one element left in the sequence (this understanding may be more intuitive).

>>> from functools import reduce
>>> def fn(x, y):
...     return x * 10 + y
...
>>> def char2num(s):
...     return {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}[s] #The dict of the character corresponding to the integer returns the integer corresponding to the incoming character
...
>>> reduce(fn, map(char2num, '13579'))
13579

You can sort out the str2int function as a whole:

def str2int(s):
    def fn(x, y):
        return x * 10 + y
    def char2num(s):
        return {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}[s]
    return reduce(fn, map(char2num, s))

Using lambda anonymous functions can further simplify:

def char2num(s):
    return {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}[s]

def str2int(s):
    return reduce(lambda x, y: x * 10 + y, map(char2num, s))

practice

1. Use the map() function to change the non-standard English name into the standard name with the first letter uppercase and other letters lowercase.

Hint:

• The string supports slicing operation, and the plus sign can be used for string splicing.
• The upper function is used to convert uppercase and the lower function is used to convert lowercase.

def normalize(name):
    return name[0].upper()+name[1:].lower()

L1 = ['adam', 'LISA', 'barT']
L2 = list(map(normalize, L1))
print(L2)

2. Write a prod() function, which can accept a list and use reduce() to quadrature.

Hint:

• Multiply two numbers with anonymous functions
• Use the reduce function for reduction to obtain the product of the continuous multiplication of list elements.

from functools import reduce
def prod(L):
    return reduce(lambda x,y: x*y,L)

print('3 * 5 * 7 * 9 =', prod([3, 5, 7, 9]))

3. Use map and reduce to write a str2float function to convert the string '123.456' into floating point number 123.45.

Hint:

• The idea of this problem is to find the position i of the decimal point (after counting i numbers from one place), and then divide the converted integer by the i power of 10.
• Another idea is to change the conversion method from num*10 + current number to num + current number / point after the decimal point is encountered during conversion. Point is initially 1, divided by 10 before adding a new number each time.

from functools import reduce
from math import pow

def chr2num(s):
    return {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}[s]

def str2float(s):
    return reduce(lambda x,y:x*10+y,map(chr2num,s.replace('.',''))) / pow(10,len(s)-s.find('.')-1)

print(str2float('985.64785'))

filter

The filter() function is also a built-in function for filtering sequences. filter() receives a function and an iteratable object. Unlike map(), filter() applies the incoming function to each element in turn, and then decides whether to keep or discard the element according to whether the return value of the function is True or False.

Simple odd filter example:

def is_odd(n):
    return n % 2 == 1

list(filter(is_odd, [1, 2, 4, 5, 6, 9, 10, 15]))
# Results: [1, 5, 9, 15]

Filter out the empty string of the list:

def not_empty(s):
    return s and s.strip()

list(filter(not_empty, ['A', '', 'B', None, 'C', '  ']))
# Result: ['a ',' B ',' C ']

Among them, the strip function is used to delete specific characters in the string. The format is s.strip(rm), and delete the characters contained in the rm deletion sequence at the beginning and end of the s string. When rm is empty, whitespace characters (including '\ n', '\ r', '\ t', ') are deleted by default.

Note that the filter() function returns an Iterator object, that is, an inert sequence, so to force filter() to complete the calculation results, you need to use the list() function to obtain all the results and return list.

The most important point of filter function is to correctly define a filter function (that is, the function that passes filter as a parameter).

practice

1. Filter prime numbers with filter

Here, the Elsevier sieve method is used.

First, list all natural numbers starting from 2 and construct a sequence:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...

Take the first number 2 of the sequence, which must be a prime number, and then use 2 to screen out the multiples of 2 of the sequence:

3, 5, 7, 9, 11, 13, 15, 17, 19, ...

Take the first number 3 of the new sequence, which must be a prime number, and then use 3 to screen out the multiples of 3 of the sequence:

5, 7, 11, 13, 17, 19, ...

And so on

First, construct a generator to output the odd sequence starting from 3:

def _odd_iter():
    n = 1
    while True:
        n = n + 2
        yield n

Then define a filter function and pass in n to judge whether x can divide all N:

def _not_divisible(n):
    return lambda x: x % n > 0

Here x is the parameter of the anonymous function, which is provided externally.

Then there is the generator that defines the return prime.

• First, the prime number 2 is output, and then the odd number queue is initialized. Each time, the head of the queue is output (it must be a prime number, because the previous round of filtering has excluded the number that is smaller than the current head of the queue and is not prime).

• Construct a new queue. Each time, use the smallest number of the current sequence as the divisor to check whether the following number is a prime number.

It is defined as follows:

def primes():
    yield 2
    it = _odd_iter() # Initial sequence
    while True:
        n = next(it) # Returns the first number of the sequence
        yield n
        it = filter(_not_divisible(n), it) # Construct new sequence

Here, because it is an iterator, you can get the next element of the queue every time you use next. In fact, it is similar to the dequeue operation of the queue, squeezing out the head of the queue without worrying about repetition.

Then, the principle of filter here is to put each number of the current it queue into_ not_ Check in divisible (n). Note that it is not passed in as parameter n, but as parameter x of anonymous function!

_ not_divisible(n) is actually viewed as a whole. It returns a function with its own parameter n (that is, the anonymous function), and then filter passes each element of the list one by one to the returned anonymous function. We must make this clear.

• Finally, because primes also produces an infinite inert sequence, we generally don't need to ask so much. Just write a loop to exit:

# Print prime numbers within 1000:
for n in primes():
    if n < 1000:
        print(n)
    else:
        break

2. Filter the number of palindromes with filter

Hint:

• str can convert integers to strings
• [:: - 1] you can get a list in reverse order.

def is_palindrome(n):
    return str(n) == str(n)[::-1]

print(list(filter(is_palindrome, range(0,1001))))

sorted

Python's built-in sorted() function can sort the list:

>>> sorted([36, 5, -12, 9, -21])
[-21, -12, 5, 9, 36]

As a high-order function, sorted() can also accept a key function for user-defined sorting, for example:

>>> sorted([36, 5, -12, 9, -21], key=abs)
[5, 9, -12, -21, 36]

The function specified by key will act on each element of the list, sort according to the results returned (mapped) by the key function, and finally output the corresponding elements in the list.

Let's take another example of string sorting:

>>> sorted(['bob', 'about', 'Zoo', 'Credit'])
['Credit', 'Zoo', 'about', 'bob']

By default, it is sorted by ASCII code, but we often want to arrange it in dictionary order. The idea is to change the string to all lowercase / all uppercase and then arrange it:

>>> sorted(['bob', 'about', 'Zoo', 'Credit'], key=str.lower)
['about', 'bob', 'Credit', 'Zoo']

The default sorting is from small to large. To reverse sorting, just set the reverse parameter to True. Review the previous knowledge. Here, the reverse parameter is a named keyword parameter.

>>> sorted(['bob', 'about', 'Zoo', 'Credit'], key=str.lower, reverse=True)
['Zoo', 'Credit', 'bob', 'about']

The key to using sorted function well is to define a mapping function.

practice

Give the score sheet and sort it by name and score respectively.

>>> L = [('Bob', 75), ('Adam', 92), ('Bart', 66), ('Lisa', 88)]
>>> L2 = sorted(L, key = lambda x:x[0])    #Sort by name
>>> L2
[('Adam', 92), ('Bart', 66), ('Bob', 75), ('Lisa', 88)]
>>> L3 = sorted(L, key = lambda x:x[1])    #Sort by grade
>>> L3
[('Bart', 66), ('Bob', 75), ('Lisa', 88), ('Adam', 92)]

Return function

Function as return value

In addition to accepting functions as parameters, higher-order functions can also return functions as result values.

For example, we want to implement a function for summing variable parameters, which can be written as follows:

def calc_sum(*args):
    ax = 0
    for n in args:
        ax = ax + n
    return ax

When calling, you can pass in any number and get the sum of these numbers. If we don't need to sum immediately, we can do it later as needed. It can be written in the form of return summation function:

def lazy_sum(*args):
    def sum():
        ax = 0
        for n in args:
            ax = ax + n
        return ax
    return sum

Calling lazy_ During sum, a sum function is returned, but the summation code inside the sum function is not executed:

>>> f = lazy_sum(1, 3, 5, 7, 9)
>>> f
<function lazy_sum.<locals>.sum at 0x101c6ed90>

When we call the returned sum function again, we can get the sum value:

>>> f()
25

be careful! Every call to lazy_ The functions returned by sum are different! Even if the same parameter is passed in, the return function is different! for instance:

>>> f1 = lazy_sum(1, 3, 5, 7, 9)
>>> f2 = lazy_sum(1, 3, 5, 7, 9)
>>> f1==f2
False

f1 and f2 are two different functions. Although calling them yields the same result, they do not affect each other.

closure

In Python, in terms of expression, closure can be defined as: if an internal function references variables in an external scope (non global scope), then the internal function is considered as a closure. For example, f in the above example is a closure, which calls variable i, which belongs to the outer loop body rather than the global variable.

Take an example:

def count():

    fs = []
    for i in range(1, 4):
        def f():
             return i*i
        fs.append(f)

    return fs

f1, f2, f3 = count()

The call results of the three return functions are:

>>> f1()
9
>>> f2()
9
>>> f3()
9

To analyze, the count function here is a function that returns three functions, in which a loop body is used to generate the three functions to be returned. From i is 1 to i is equal to 3, a function f is generated each time, which returns the square value of i. If you follow the usual way of thinking, you may feel that the three returned functions f1, f2 and f3 should output 1, 4 and 9 respectively.

But in fact, this is not the case, because when a function is returned, the code inside the function is not executed! Only when this returned function is called will it be executed!

When the count function is called, three new functions are actually returned, and the value of the loop variable i becomes 3. When the three returned functions are called, their code will be executed. At this time, the value of the referenced i is all 3.

What if you have to use external loop variables in closures? We first define a function, bind the loop variable with its parameters, and then define the function to return in it. In this way, no matter how the loop variable changes, the value bound to the parameter will not change, and we can get the desired result. That is, rewrite the above example as:

def count():

    def f(j):
        def g():
            return j*j
        return g

    fs = []
    for i in range(1, 4):
        fs.append(f(i)) # f(i) is executed immediately, so the current value of i is passed into f()
    return fs

Call result:

>>> f1, f2, f3 = count()
>>> f1()
1
>>> f2()
4
>>> f3()
9

Here, the variable J used in closure g is from the external scope f, and j is bound as a parameter in f and will not change, which is different from the variable i in the external scope count function. Therefore, the results of each of the three functions returned by count are different.

summary

• When returning a closure, do not reference the loop variable of the external scope or the variable that will change in the external scope in the closure code.

• Local variables of external scopes should not be modified in closures.