函數式編程

函數是Python內建支持的一種封裝，而函數式編程通俗說來就是把函數本身作為參數傳入另一個函數，允許返回一個函數。

函數名其實也是變數，也可以被賦值。如果函數名被賦值為其他值，則不再指向原來函數。

高階函數：既然變數可以指向函數，函數的參數能接收變數，那麼一個函數就可以接收另一個函數作為參數，這種函數就稱之為高階函數。

此時就可以學習幾個 高階函數：

- map/reduce

可借鑒Google論文[MapReduce: Simplified Data Processing on Large Clusters](http://research.google.com/archive/mapreduce.html)

map(func, Iterator)

第一個參數即為函數名，第二個參數即為一個列表，map將傳入的函數依次作用到序列的每一個元素上，並返回一個新的列表Iterator。

def abc(x):
    return x * x

r = map(abc, [1, 2, 3, 4, 5, 6, 7, 8, 9])
list(r)

結果：

[1, 4, 9, 16, 25, 36, 49, 64, 81]

註意: 迴圈也可以得到相同結果，但是會生成多個list。

reduce(func ,Iterator)

reduce把結果和序列的下一個元素做累積計算。
reduce(f, [x1, x2, x3, x4]) = f(f(f(x1, x2), x3), x4)

綜合例子：str 轉 int

from functools import reduce

DIGITS = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}

def char2num(s):
    return DIGITS[s]

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

print(str2int("124432"))

結果：
124432

- filter(func, Iterator)

用於過濾序列(篩選)。fifter把傳入的函數作用於每個元素之後，根據傳入函數的返回值是True還是False決定保留還是丟棄該元素，最終還是返回列表。

例子:用filter求素數
計算素數的一個方法是埃氏篩法，它的演算法理解起來非常簡單：

首先，列出從2開始的所有自然數，構造一個序列：

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

取序列的第一個數2，它一定是素數，然後用2把序列的2的倍數篩掉：

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

取新序列的第一個數3，它一定是素數，然後用3把序列的3的倍數篩掉：

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

取新序列的第一個數5，然後用5把序列的5的倍數篩掉：

7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

不斷篩下去，就可以得到所有的素數。

用Python來實現這個演算法，可以先構造一個從3開始的奇數序列：

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

註意這是一個生成器，並且是一個無限序列。

然後定義一個篩選函數：

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

最後，定義一個生成器，不斷返回下一個素數：

def primes():
    yield 2
    it = _odd_iter() # 初始序列
    while True:
        n = next(it) # 返回序列的第一個數
        yield n
        it = filter(_not_divisible(n), it) # 構造新序列

這個生成器先返回第一個素數2，然後，利用filter()不斷產生篩選後的新的序列。

由於primes()也是一個無限序列，所以調用時需要設置一個退出迴圈的條件：

# 列印1000以內的素數:
for n in primes():
    if n < 1000:
        print(n)
    else:
        break

註意到Iterator是惰性計算的序列，所以我們可以用Python表示“全體自然數”，“全體素數”這樣的序列，而代碼非常簡潔。

- sorted()

排序演算法：排序也是在程式中經常用到的演算法。無論使用冒泡排序還是快速排序，排序的核心是比較兩個元素的大小。如果是數字，我們可以直接比較，但如果是字元串或者兩個dict呢？直接比較數學上的大小是沒有意義的，因此，比較的過程必須通過函數抽象出來。   


sorted(list, key=func, reserve=False)：按key接收的函數作用在list的每個元素上之後的返回值進行排序， * 而返回的是對應原來的元素*，reserve為反向排序。

返回函數

函數作為函數的返回值。

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

f = lazy_sum(1, 3, 5, 7, 9)
f()

結果：
25

註意點：即使傳入相同的參數，返回的也不是同一個函數。