高階函數英文叫Higher-order function。什么是高階函數？我們以實際代碼為例子，一步一步深入概念。 ### 變量可以指向函數 以Python內置的求絕對值的函數`abs()`為例，調用該函數用以下代碼： ~~~ >>> abs(-10) 10 ~~~ 但是，如果只寫`abs`呢？ ~~~ >>> abs <built-in function abs> ~~~ 可見，`abs(-10)`是函數調用，而`abs`是函數本身。 要獲得函數調用結果，我們可以把結果賦值給變量： ~~~ >>> x = abs(-10) >>> x 10 ~~~ 但是，如果把函數本身賦值給變量呢？ ~~~ >>> f = abs >>> f <built-in function abs> ~~~ 結論：函數本身也可以賦值給變量，即：變量可以指向函數。 如果一個變量指向了一個函數，那么，可否通過該變量來調用這個函數？用代碼驗證一下： ~~~ >>> f = abs >>> f(-10) 10 ~~~ 成功！說明變量`f`現在已經指向了`abs`函數本身。直接調用`abs()`函數和調用變量`f()`完全相同。 ### 函數名也是變量 那么函數名是什么呢？函數名其實就是指向函數的變量！對于`abs()`這個函數，完全可以把函數名`abs`看成變量，它指向一個可以計算絕對值的函數！ 如果把`abs`指向其他對象，會有什么情況發生？ ~~~ >>> abs = 10 >>> abs(-10) Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: 'int' object is not callable ~~~ 把`abs`指向`10`后，就無法通過`abs(-10)`調用該函數了！因為`abs`這個變量已經不指向求絕對值函數而是指向一個整數`10`！ 當然實際代碼絕對不能這么寫，這里是為了說明函數名也是變量。要恢復`abs`函數，請重啟Python交互環境。 注：由于`abs`函數實際上是定義在`__builtin__`模塊中的，所以要讓修改`abs`變量的指向在其它模塊也生效，要用`__builtin__.abs = 10`。 ### 傳入函數 既然變量可以指向函數，函數的參數能接收變量，那么一個函數就可以接收另一個函數作為參數，這種函數就稱之為高階函數。 一個最簡單的高階函數： ~~~ def add(x, y, f): return f(x) + f(y) ~~~ 當我們調用`add(-5, 6, abs)`時，參數`x`，`y`和`f`分別接收`-5`，`6`和`abs`，根據函數定義，我們可以推導計算過程為： ~~~ x = -5 y = 6 f = abs f(x) + f(y) ==> abs(-5) + abs(6) ==> 11 return 11 ~~~ 用代碼驗證一下： ~~~ >>> add(-5, 6, abs) 11 ~~~ 編寫高階函數，就是讓函數的參數能夠接收別的函數。 ### 小結 把函數作為參數傳入，這樣的函數稱為高階函數，函數式編程就是指這種高度抽象的編程范式。 Python內建了`map()`和`reduce()`函數。 如果你讀過Google的那篇大名鼎鼎的論文“[MapReduce: Simplified Data Processing on Large Clusters](http://research.google.com/archive/mapreduce.html)”，你就能大概明白map/reduce的概念。 我們先看map。`map()`函數接收兩個參數，一個是函數，一個是`Iterable`，`map`將傳入的函數依次作用到序列的每個元素，并把結果作為新的`Iterator`返回。 舉例說明，比如我們有一個函數f(x)=x2，要把這個函數作用在一個list `[1, 2, 3, 4, 5, 6, 7, 8, 9]`上，就可以用`map()`實現如下：  現在，我們用Python代碼實現： ~~~ >>> 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] ~~~ `map()`傳入的第一個參數是`f`，即函數對象本身。由于結果`r`是一個`Iterator`，`Iterator`是惰性序列，因此通過`list()`函數讓它把整個序列都計算出來并返回一個list。 你可能會想，不需要`map()`函數，寫一個循環，也可以計算出結果： ~~~ L = [] for n in [1, 2, 3, 4, 5, 6, 7, 8, 9]: L.append(f(n)) print(L) ~~~ 的確可以，但是，從上面的循環代碼，能一眼看明白“把f(x)作用在list的每一個元素并把結果生成一個新的list”嗎？ 所以，`map()`作為高階函數，事實上它把運算規則抽象了，因此，我們不但可以計算簡單的f(x)=x2，還可以計算任意復雜的函數，比如，把這個list所有數字轉為字符串： ~~~ >>> list(map(str, [1, 2, 3, 4, 5, 6, 7, 8, 9])) ['1', '2', '3', '4', '5', '6', '7', '8', '9'] ~~~ 只需要一行代碼。 再看`reduce`的用法。`reduce`把一個函數作用在一個序列`[x1, x2, x3, ...]`上，這個函數必須接收兩個參數，`reduce`把結果繼續和序列的下一個元素做累積計算，其效果就是： ~~~ reduce(f, [x1, x2, x3, x4]) = f(f(f(x1, x2), x3), x4) ~~~ 比方說對一個序列求和，就可以用`reduce`實現： ~~~ >>> from functools import reduce >>> def add(x, y): ... return x + y ... >>> reduce(add, [1, 3, 5, 7, 9]) 25 ~~~ 當然求和運算可以直接用Python內建函數`sum()`，沒必要動用`reduce`。 但是如果要把序列`[1, 3, 5, 7, 9]`變換成整數`13579`，`reduce`就可以派上用場： ~~~ >>> from functools import reduce >>> def fn(x, y): ... return x * 10 + y ... >>> reduce(fn, [1, 3, 5, 7, 9]) 13579 ~~~ 這個例子本身沒多大用處，但是，如果考慮到字符串`str`也是一個序列，對上面的例子稍加改動，配合`map()`，我們就可以寫出把`str`轉換為`int`的函數： ~~~ >>> 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] ... >>> reduce(fn, map(char2num, '13579')) 13579 ~~~ 整理成一個`str2int`的函數就是： ~~~ from functools import reduce 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)) ~~~ 還可以用lambda函數進一步簡化成： ~~~ from functools import reduce 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)) ~~~ 也就是說，假設Python沒有提供`int()`函數，你完全可以自己寫一個把字符串轉化為整數的函數，而且只需要幾行代碼！ lambda函數的用法在后面介紹。 ### 練習 利用`map()`函數，把用戶輸入的不規范的英文名字，變為首字母大寫，其他小寫的規范名字。輸入：`['adam', 'LISA', 'barT']`，輸出：`['Adam', 'Lisa', 'Bart']`： ### 參考代碼 [do_map.py](https://github.com/michaelliao/learn-python3/blob/master/samples/functional/do_map.py) [do_reduce.py](https://github.com/michaelliao/learn-python3/blob/master/samples/functional/do_reduce.py) Python內建的`filter()`函數用于過濾序列。 和`map()`類似，`filter()`也接收一個函數和一個序列。和`map()`不同的時，`filter()`把傳入的函數依次作用于每個元素，然后根據返回值是`True`還是`False`決定保留還是丟棄該元素。 例如，在一個list中，刪掉偶數，只保留奇數，可以這么寫： ~~~ def is_odd(n): return n % 2 == 1 list(filter(is_odd, [1, 2, 4, 5, 6, 9, 10, 15])) # 結果: [1, 5, 9, 15] ~~~ 把一個序列中的空字符串刪掉，可以這么寫： ~~~ def not_empty(s): return s and s.strip() list(filter(not_empty, ['A', '', 'B', None, 'C', ' '])) # 結果: ['A', 'B', 'C'] ~~~ 可見用`filter()`這個高階函數，關鍵在于正確實現一個“篩選”函數。 注意到`filter()`函數返回的是一個`Iterator`，也就是一個惰性序列，所以要強迫`filter()`完成計算結果，需要用`list()`函數獲得所有結果并返回list。 ### 用filter求素數 計算[素數](http://baike.baidu.com/view/10626.htm)的一個方法是[埃氏篩法](http://baike.baidu.com/view/3784258.htm)，它的算法理解起來非常簡單： 首先，列出從`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表示“全體自然數”，“全體素數”這樣的序列，而代碼非常簡潔。 ### 小結 `filter()`的作用是從一個序列中篩出符合條件的元素。由于`filter()`使用了惰性計算，所以只有在取`filter()`結果的時候，才會真正篩選并每次返回下一個篩出的元素。 ### 參考源碼 [do_filter.py](https://github.com/michaelliao/learn-python3/blob/master/samples/functional/do_filter.py) [prime_numbers.py](https://github.com/michaelliao/learn-python3/blob/master/samples/functional/prime_numbers.py) ### 排序算法 排序也是在程序中經常用到的算法。無論使用冒泡排序還是快速排序，排序的核心是比較兩個元素的大小。如果是數字，我們可以直接比較，但如果是字符串或者兩個dict呢？直接比較數學上的大小是沒有意義的，因此，比較的過程必須通過函數抽象出來。通常規定，對于兩個元素`x`和`y`，如果認為`x y`，則返回`1`，這樣，排序算法就不用關心具體的比較過程，而是根據比較結果直接排序。 Python內置的`sorted()`函數就可以對list進行排序： ~~~ >>> sorted([36, 5, -12, 9, -21]) [-21, -12, 5, 9, 36] ~~~ 此外，`sorted()`函數也是一個高階函數，它還可以接收一個`key`函數來實現自定義的排序，例如按絕對值大小排序： ~~~ >>> sorted([36, 5, -12, 9, -21], key=abs) [5, 9, -12, -21, 36] ~~~ key指定的函數將作用于list的每一個元素上，并根據key函數返回的結果進行排序。對比原始的list和經過`key=abs`處理過的list： ~~~ list = [36, 5, -12, 9, -21] keys = [36, 5, 12, 9, 21] ~~~ 然后`sorted()`函數按照keys進行排序，并按照對應關系返回list相應的元素： ~~~ keys排序結果 => [5, 9, 12, 21, 36] | | | | | 最終結果 => [5, 9, -12, -21, 36] ~~~ 我們再看一個字符串排序的例子： ~~~ >>> sorted(['bob', 'about', 'Zoo', 'Credit']) ['Credit', 'Zoo', 'about', 'bob'] ~~~ 默認情況下，對字符串排序，是按照ASCII的大小比較的，由于`'Z' < 'a'`，結果，大寫字母`Z`會排在小寫字母`a`的前面。 現在，我們提出排序應該忽略大小寫，按照字母序排序。要實現這個算法，不必對現有代碼大加改動，只要我們能用一個key函數把字符串映射為忽略大小寫排序即可。忽略大小寫來比較兩個字符串，實際上就是先把字符串都變成大寫（或者都變成小寫），再比較。 這樣，我們給`sorted`傳入key函數，即可實現忽略大小寫的排序： ~~~ >>> sorted(['bob', 'about', 'Zoo', 'Credit'], key=str.lower) ['about', 'bob', 'Credit', 'Zoo'] ~~~ 要進行反向排序，不必改動key函數，可以傳入第三個參數`reverse=True`： ~~~ >>> sorted(['bob', 'about', 'Zoo', 'Credit'], key=str.lower, reverse=True) ['Zoo', 'Credit', 'bob', 'about'] ~~~ 從上述例子可以看出，高階函數的抽象能力是非常強大的，而且，核心代碼可以保持得非常簡潔。 ### 小結 `sorted()`也是一個高階函數。用`sorted()`排序的關鍵在于實現一個映射函數。 ### 練習 假設我們用一組tuple表示學生名字和成績： ~~~ L = [('Bob', 75), ('Adam', 92), ('Bart', 66), ('Lisa', 88)] ~~~ 請用`sorted()`對上述列表分別按名字排序： ~~~ # -*- coding: utf-8 -*- L = [('Bob', 75), ('Adam', 92), ('Bart', 66), ('Lisa', 88)] def by_name(t): L2 = sorted(L, key=by_name) print(L2) ?Run 再按成績從高到低排序： # -*- coding: utf-8 -*- L = [('Bob', 75), ('Adam', 92), ('Bart', 66), ('Lisa', 88)] print(L2) ~~~ ?Run ### 參考源碼 [do_sorted.py](https://github.com/michaelliao/learn-python3/blob/master/samples/functional/do_sorted.py)