手把手介紹函數式編程：從命令式重構到函數式
本文是一篇手把手的函數式編程入門介紹，借助代碼示例講解細膩。但又不乏洞見，第一節中列舉和點評了函數式種種讓眼花繚亂的特質，給出了『理解函數式特質的指南針：函數式代碼的核心特質就一條， 無副作用 』，相信這個指南針對于有積極學過挖過函數式的同學看來更是有相知恨晚的感覺。
希望看了這篇文章之后，能在學習和使用函數式編程的旅途中不迷路哦，兄die～
PS：本人是在《 Functional Programming, Simplified(Scala edition) 》這本書了解到這篇文章。這本書由淺入深循序漸進地對 FP 做了體系講解，力薦！
手把手介紹函數式編程：從命令式重構到函數式
有很多函數式編程文章講解了抽象的函數式技術，也就是組合（ composition ）、管道（ pipelining ）、高階函數（ higher order function ）。本文希望以另辟蹊徑的方式來講解函數式：首先展示我們平常編寫的命令式而非函數式的代碼示例，然后將這些示例重構成函數式風格。
本文的第一部分選用了簡短的數據轉換循環，將它們重構成函數式的 map 和 reduce 。第二部分則對更長的循環代碼，將它們分解成多個單元，然后重構各個單元成函數式的。第三部分選用的是有一系列連續的數據轉換循環代碼，將其拆解成為一個函數式管道（ functional pipeline）。
示例代碼用的是 Python 語言，因為多數人都覺得 Python 易于閱讀。示例代碼避免使用 Python 范的（ pythonic ）代碼，以便展示出各個語言通用的函數式技術： map 、 reduce 和管道。所有示例都用的是 Python 2 。
- 理解函數式特質的指南針
- 不要迭代列表，使用
map和reduce - 聲明方式編寫代碼，而非命令式
- 現在開始我們可以做什么？
理解函數式特質的指南針
當人們談論函數式編程時，提到了多到令人迷路的『函數式』特質（ characteristics ）：
- 人們會提到不可變數據（
immutable data）、一等公民的函數（first class function）和尾調用優化（tail call optimisation）。這些是 有助于函數式編程的語言特性 。 - 人們也會提到
map、reduce、管道、遞歸（recursing）、柯里化（currying）以及高階函數的使用。這些是 用于編寫函數式代碼的編程技術 。 - 人們還會提到并行化（
parallelization）、惰性求值（lazy evaluation）和確定性（determinism）。這些是 函數式程序的優點 。
無視這一切。函數式代碼的核心特質就一條： 無副作用 （ side effect ）。即代碼邏輯不依賴于當前函數之外的數據，并且也不會更改當前函數之外的數據。所有其他的『函數式』特質都可以從這一條派生出來。在你學習過程中，請以此作為指南針。不要再迷路哦，兄die～
這是一個非函數式的函數：
- a = 0
- def increment():
- global a
- a += 1
而這是一個函數式的函數：
- def increment(a):
- return a + 1
不要迭代列表，使用 map 和 reduce
map
map 輸入一個函數和一個集合，創建一個新的空集合，在原來集合的每個元素上運行該函數，并將各個返回值插入到新集合中，然后返回新的集合。
這是一個簡單的 map ，它接受一個名字列表并返回這些名字的長度列表：
- name_lengths = map(len, ["Mary", "Isla", "Sam"])
- print name_lengths
- # => [4, 4, 3]
這是一個 map ，對傳遞的集合中的每個數字進行平方：
- squares = map(lambda x: x * x, [0, 1, 2, 3, 4])
- print squares
- # => [0, 1, 4, 9, 16]
這個 map 沒有輸入命名函數，而是一個匿名的內聯函數，用 lambda 關鍵字來定義。 lambda的參數定義在冒號的左側。函數體定義在冒號的右側。（隱式）返回的是函數體的運行結果。
下面的非函數式代碼輸入一個真實名字的列表，替換成隨機分配的代號。
- import random
- names = ['Mary', 'Isla', 'Sam']
- code_names = ['Mr. Pink', 'Mr. Orange', 'Mr. Blonde']
- for i in range(len(names)):
- names[i] = random.choice(code_names)
- print names
- # => ['Mr. Blonde', 'Mr. Blonde', 'Mr. Blonde']
（如你所見，這個算法可能會為多個秘密特工分配相同的秘密代號，希望這不會因此導致混淆了秘密任務。）
可以用 map 重寫成：
- import random
- names = ['Mary', 'Isla', 'Sam']
- secret_names = map(lambda x: random.choice(['Mr. Pink',
- 'Mr. Orange',
- 'Mr. Blonde']),
- names)
練習1：嘗試將下面的代碼重寫為 map ，輸入一個真實名字列表，替換成用更可靠策略生成的代號。
- names = ['Mary', 'Isla', 'Sam']
- for i in range(len(names)):
- names[i] = hash(names[i])
- print names
- # => [6306819796133686941, 8135353348168144921, -1228887169324443034]
（希望特工會留下美好的回憶，在秘密任務期間能記得住搭檔的秘密代號。）
我的實現方案：
- names = ['Mary', 'Isla', 'Sam']
- secret_names = map(hash, names)
reduce
reduce 輸入一個函數和一個集合，返回通過合并集合元素所創建的值。
這是一個簡單的 reduce ，返回集合所有元素的總和。
- sum = reduce(lambda a, x: a + x, [0, 1, 2, 3, 4])
- print sum
- # => 10
x 是迭代的當前元素。 a 是累加器（ accumulator ），它是在前一個元素上執行 lambda 的返回值。 reduce() 遍歷所有集合元素。對于每一個元素，運行以當前的 a 和 x 為參數運行 lambda ，返回結果作為下一次迭代的 a 。
在第一次迭代時， a 是什么值？并沒有前一個的迭代結果可以傳遞。 reduce() 使用集合中的第一個元素作為第一次迭代中的 a 值，從集合的第二個元素開始迭代。也就是說，第一個 x 是集合的第二個元素。
下面的代碼計算單詞 'Sam' 在字符串列表中出現的次數：
- sentences = ['Mary read a story to Sam and Isla.',
- 'Isla cuddled Sam.',
- 'Sam chortled.']
- sam_count = 0
- for sentence in sentences:
- sam_count += sentence.count('Sam')
- print sam_count
- # => 3
這與下面使用 reduce 的代碼相同：
- sentences = ['Mary read a story to Sam and Isla.',
- 'Isla cuddled Sam.',
- 'Sam chortled.']
- sam_count = reduce(lambda a, x: a + x.count('Sam'),
- sentences,
- 0)
這段代碼是如何產生初始的 a 值？ 'Sam' 出現次數的初始值不能是 'Mary read a story to Sam and Isla.' 。初始累加器用 reduce() 的第三個參數指定。這樣就允許使用與集合元素不同類型的值。
為什么 map 和 reduce 更好？
- 這樣的做法通常會是一行簡潔的代碼。
- 迭代的重要部分 —— 集合、操作和返回值 —— 以
map和reduce方式總是在相同的位置。 - 循環中的代碼可能會影響在它之前定義的變量或在它之后運行的代碼。按照約定，
map和reduce都是函數式的。 map和reduce是基本原子操作。- 閱讀
for循環時，必須一行一行地才能理解整體邏輯。往往沒有什么規則能保證以一個固定結構來明確代碼的表義。 - 相比之下，
map和reduce則是一目了然表現出了可以組合出復雜算法的構建塊（building block）及其相關的元素，代碼閱讀者可以迅速理解并抓住整體脈絡。『哦～這段代碼正在轉換每個集合元素；丟棄了一些轉換結果；然后將剩下的元素合并成單個輸出結果。』
- 閱讀
map和reduce有很多朋友，提供有用的、對基本行為微整的版本。比如：filter、all、any和find。
練習2：嘗試使用 map 、 reduce 和 filter 重寫下面的代碼。 filter 需要一個函數和一個集合，返回結果是函數返回 True 的所有集合元素。
- people = [{'name': 'Mary', 'height': 160},
- {'name': 'Isla', 'height': 80},
- {'name': 'Sam'}]
- height_total = 0
- height_count = 0
- for person in people:
- if 'height' in person:
- height_total += person['height']
- height_count += 1
- if height_count > 0:
- average_height = height_total / height_count
- print average_height
- # => 120
如果上面這段代碼看起來有些燒腦，我們試試不以在數據上操作為中心的思考方式。而是想一想數據所經歷的狀態：從人字典的列表轉換成平均身高。不要將多個轉換混在一起。每個轉換放在一個單獨的行上，并將結果分配一個有描述性命名的變量。代碼工作之后，再合并縮減代碼。
我的實現方案：
- people = [{'name': 'Mary', 'height': 160},
- {'name': 'Isla', 'height': 80},
- {'name': 'Sam'}]
- heights = map(lambda x: x['height'],
- filter(lambda x: 'height' in x, people))
- if len(heights) > 0:
- from operator import add
- average_height = reduce(add, heights) / len(heights)
聲明方式編寫代碼，而非命令式
下面的程序演示三輛賽車的比賽。每過一段時間，賽車可能向前跑了，也可能拋錨而原地不動。在每個時間段，程序打印出目前為止的賽車路徑。五個時間段后比賽結束。
這是個示例輸出：
- -
- --
- --
- --
- --
- ---
- ---
- --
- ---
- ----
- ---
- ----
- ----
- ----
- -----
這是程序實現：
- from random import random
- time = 5
- car_positions = [1, 1, 1]
- while time:
- # decrease time
- time -= 1
- print ''
- for i in range(len(car_positions)):
- # move car
- if random() > 0.3:
- car_positions[i] += 1
- # draw car
- print '-' * car_positions[i]
這份代碼是命令式的。函數式版本則是聲明性的，描述要做什么，而不是如何做。
使用函數
通過將代碼片段打包到函數中，程序可以更具聲明性。
- from random import random
- def move_cars():
- for i, _ in enumerate(car_positions):
- if random() > 0.3:
- car_positions[i] += 1
- def draw_car(car_position):
- print '-' * car_position
- def run_step_of_race():
- global time
- time -= 1
- move_cars()
- def draw():
- print ''
- for car_position in car_positions:
- draw_car(car_position)
- time = 5
- car_positions = [1, 1, 1]
- while time:
- run_step_of_race()
- draw()
要理解這個程序，讀者只需讀一下主循環。『如果還剩下時間，請跑一步，然后畫出線圖。再次檢查時間。』如果讀者想要了解更多關于比賽步驟或畫圖的含義，可以閱讀對應函數的代碼。
沒什么要再說明的了。 代碼是自描述的。
拆分代碼成函數是一種很好的、簡單易行的方法，能使代碼更具可讀性。
這個技術使用函數，但將函數用作子例程（ sub-routine ），用于打包代碼。對照上文說的指南針，這樣的代碼并不是函數式的。實現中的函數使用了沒有作為參數傳遞的狀態，即通過更改外部變量而不是返回值來影響函數周圍的代碼。要確認函數真正做了什么，讀者必須仔細閱讀每一行。如果找到一個外部變量，必須反查它的源頭，并檢查其他哪些函數更改了這個變量。
消除狀態
下面是賽車代碼的函數式版本：
- from random import random
- def move_cars(car_positions):
- return map(lambda x: x + 1 if random() > 0.3 else x,
- car_positions)
- def output_car(car_position):
- return '-' * car_position
- def run_step_of_race(state):
- return {'time': state['time'] - 1,
- 'car_positions': move_cars(state['car_positions'])}
- def draw(state):
- print ''
- print '\n'.join(map(output_car, state['car_positions']))
- def race(state):
- draw(state)
- if state['time']:
- race(run_step_of_race(state))
- race({'time': 5,
- 'car_positions': [1, 1, 1]})
代碼仍然是分解成函數。但這些函數是函數式的，有三個跡象表明這點：
- 不再有任何共享變量。
time與car_position作為參數傳入race()。 - 函數是有參數的。
- 在函數內部沒有變量實例化。所有數據更改都使用返回值完成。基于
run_step_of_race()的結果，race()做遞歸調用。每當一個步驟生成一個新狀態時，立即傳遞到下一步。
讓我們另外再來看看這么兩個函數， zero() 和 one() ：
- def zero(s):
- if s[0] == "0":
- return s[1:]
- def one(s):
- if s[0] == "1":
- return s[1:]
zero() 輸入一個字符串 s 。如果第一個字符是 '0' ，則返回字符串的其余部分。如果不是，則返回 None ， Python 函數的默認返回值。 one() 做同樣的事情，但關注的是第一個字符 '1'。
假設有一個叫做 rule_sequence() 的函數，輸入一個字符串和規則函數的列表，比如 zero()和 one() ：
- 調用字符串上的第一個規則。
- 除非
None返回，否則它將獲取返回值并在其上調用第二個規則。 - 除非
None返回，否則它將獲取返回值并在其上調用第三個規則。 - 等等。
- 如果任何規則返回
None，則rule_sequence()停止并返回None。 - 否則，它返回最終規則的返回值。
下面是一些示例輸入和輸出：
- print rule_sequence('0101', [zero, one, zero])
- # => 1
- print rule_sequence('0101', [zero, zero])
- # => None
這是命令式版本的 rule_sequence() 實現：
- def rule_sequence(s, rules):
- for rule in rules:
- s = rule(s)
- if s == None:
- break
- return s
練習3：上面的代碼使用循環來實現。通過重寫為遞歸來使其更具聲明性。
我的實現方案：
- def rule_sequence(s, rules):
- if s == None or not rules:
- return s
- else:
- return rule_sequence(rules[0](s), rules[1:])
使用管道
在上一節中，我們重寫一些命令性循環成為調用輔助函數的遞歸。在本節中，將使用稱為管道的技術重寫另一類型的命令循環。
下面的循環對樂隊字典執行轉換，字典包含了樂隊名、錯誤的所屬國家和活躍狀態。
- bands = [{'name': 'sunset rubdown', 'country': 'UK', 'active': False},
- {'name': 'women', 'country': 'Germany', 'active': False},
- {'name': 'a silver mt. zion', 'country': 'Spain', 'active': True}]
- def format_bands(bands):
- for band in bands:
- band['country'] = 'Canada'
- band['name'] = band['name'].replace('.', '')
- band['name'] = band['name'].title()
- format_bands(bands)
- print bands
- # => [{'name': 'Sunset Rubdown', 'active': False, 'country': 'Canada'},
- # {'name': 'Women', 'active': False, 'country': 'Canada' },
- # {'name': 'A Silver Mt Zion', 'active': True, 'country': 'Canada'}]
看到這樣的函數命名讓人感受到一絲的憂慮，命名中的 format 表義非常模糊。仔細檢查代碼后，憂慮逆流成河。在循環的實現中做了三件事：
'country'鍵的值設置成了'Canada'。- 刪除了樂隊名中的標點符號。
- 樂隊名改成首字母大寫。
我們很難看出這段代碼意圖是什么，也很難看出這段代碼是否完成了它看起來要做的事情。代碼難以重用、難以測試且難以并行化。
與下面實現對比一下：
- print pipeline_each(bands, [set_canada_as_country,
- strip_punctuation_from_name,
- capitalize_names])
這段代碼很容易理解。給人的印象是輔助函數是函數式的，因為它們看過來是串聯在一起的。前一個函數的輸出成為下一個的輸入。如果是函數式的，就很容易驗證。也易于重用、易于測試且易于并行化。
pipeline_each() 的功能就是將樂隊一次一個地傳遞給一個轉換函數，比如 set_canada_as_country() 。將轉換函數應用于所有樂隊后， pipeline_each() 將轉換后的樂隊打包起來。然后，打包的樂隊傳遞給下一個轉換函數。
我們來看看轉換函數。
- def assoc(_d, key, value):
- from copy import deepcopy
- d = deepcopy(_d)
- d[key] = value
- return d
- def set_canada_as_country(band):
- return assoc(band, 'country', "Canada")
- def strip_punctuation_from_name(band):
- return assoc(band, 'name', band['name'].replace('.', ''))
- def capitalize_names(band):
- return assoc(band, 'name', band['name'].title())
每個函數都將樂隊的一個鍵與一個新值相關聯。如果不變更原樂隊，沒有簡單的方法可以直接實現。 assoc() 通過使用 deepcopy() 生成傳入字典的副本來解決此問題。每個轉換函數都對副本進行修改并返回該副本。
一切似乎都很好。當鍵與新值相關聯時，可以保護原樂隊字典免于被變更。但是上面的代碼中還有另外兩個潛在的變更。在 strip_punctuation_from_name() 中，原來的樂隊名通過調用 replace() 生成無標點的樂隊名。在 capitalize_names() 中，原來的樂隊名通過調用 title() 生成大寫樂隊名。如果 replace() 和 title() 不是函數式的，則 strip_punctuation_from_name()和 capitalize_names() 也將不是函數式的。
幸運的是， replace() 和 title() 不會變更他們操作的字符串。這是因為字符串在 Python中是不可變的（ immutable ）。例如，當 replace() 對樂隊名字符串進行操作時，將復制原來的樂隊名并在副本上執行 replace() 調用。Phew～有驚無險！
Python 中字符串和字典之間在可變性上不同的這種對比彰顯了像 Clojure 這樣語言的吸引力。 Clojure 程序員完全不需要考慮是否會改變數據。 Clojure 的數據結構是不可變的。
練習4：嘗試編寫 pipeline_each 函數的實現。想想操作的順序。數組中的樂隊一次一個傳遞到第一個變換函數。然后返回的結果樂隊數組中一次一個樂隊傳遞給第二個變換函數。以此類推。
我的實現方案：
- def pipeline_each(data, fns):
- return reduce(lambda a, x: map(x, a),
- fns,
- data)
所有三個轉換函數都可以歸結為對傳入的樂隊的特定字段進行更改。可以用 call() 來抽象， call() 傳入一個函數和鍵名，用鍵對應的值來調用這個函數。
- set_canada_as_country = call(lambda x: 'Canada', 'country')
- strip_punctuation_from_name = call(lambda x: x.replace('.', ''), 'name')
- capitalize_names = call(str.title, 'name')
- print pipeline_each(bands, [set_canada_as_country,
- strip_punctuation_from_name,
- capitalize_names])
或者，如果我們愿意為了簡潔而犧牲一些可讀性，那么可以寫成：
- print pipeline_each(bands, [call(lambda x: 'Canada', 'country'),
- call(lambda x: x.replace('.', ''), 'name'),
- call(str.title, 'name')])
call() 的實現代碼：
- def assoc(_d, key, value):
- from copy import deepcopy
- d = deepcopy(_d)
- d[key] = value
- return d
- def call(fn, key):
- def apply_fn(record):
- return assoc(record, key, fn(record.get(key)))
- return apply_fn
上面的實現中有不少內容要講，讓我們一點一點地來說明：
call()是一個高階函數。高階函數是指將函數作為參數，或返回函數。或者，就像call()，輸入和返回2者都是函數。apply_fn()看起來與三個轉換函數非常相似。輸入一個記錄（一個樂隊），record[key]是查找出值；再以值為參數調用fn，將調用結果賦值回記錄的副本；最后返回副本。call()不做任何實際的事。而是調用apply_fn()時完成需要做的事。在上面的示例的pipeline_each()中，一個apply_fn()實例會設置傳入樂隊的'country'成'Canada'；另一個實例則將傳入樂隊的名字轉成大寫。- 當運行一個
apply_fn()實例，fn和key2個變量并沒有在自己的作用域中，既不是apply_fn()的參數，也不是本地變量。但2者仍然可以訪問。- 當定義一個函數時，會保存這個函數能閉包進來（
close over）的變量引用：在這個函數外層作用域中定義的變量。這些變量可以在該函數內使用。 - 當函數運行并且其代碼引用變量時，
Python會在本地變量和參數中查找變量。如果沒有找到，則會在保存的引用中查找閉包進來的變量。就在這里，會發現fn和key。
- 當定義一個函數時，會保存這個函數能閉包進來（
- 在
call()代碼中沒有涉及樂隊列表。這是因為call()，無論要處理的對象是什么，可以為任何程序生成管道函數。函數式編程的一大關注點就是構建通用的、可重用的和可組合的函數所組成的庫。
完美！閉包（ closure ）、高階函數以及變量作用域，在上面的幾段代碼中都涉及了。嗯，理解完了上面這些內容，是時候來個驢肉火燒打賞一下自己。 :sushi:
最后還差實現一段處理樂隊的邏輯：刪除除名字和國家之外的內容。 extract_name_and_country() 可以把這些信息提取出來：
- def extract_name_and_country(band):
- plucked_band = {}
- plucked_band['name'] = band['name']
- plucked_band['country'] = band['country']
- return plucked_band
- print pipeline_each(bands, [call(lambda x: 'Canada', 'country'),
- call(lambda x: x.replace('.', ''), 'name'),
- call(str.title, 'name'),
- extract_name_and_country])
- # => [{'name': 'Sunset Rubdown', 'country': 'Canada'},
- # {'name': 'Women', 'country': 'Canada'},
- # {'name': 'A Silver Mt Zion', 'country': 'Canada'}]
extract_name_and_country() 本可以寫成名為 pluck() 的通用函數。 pluck() 使用起來是這個樣子：
【譯注】作者這里用了虛擬語氣『*本*可以』。
言外之意是，在實踐中為了更具體直白地表達出業務，可能不需要進一步抽象成 pluck() 。
- print pipeline_each(bands, [call(lambda x: 'Canada', 'country'),
- call(lambda x: x.replace('.', ''), 'name'),
- call(str.title, 'name'),
- pluck(['name', 'country'])])
練習5： pluck() 輸入是要從每條記錄中提取鍵的列表。試著實現一下。它會是一個高階函數。
我的實現方案：
- def pluck(keys):
- def pluck_fn(record):
- return reduce(lambda a, x: assoc(a, x, record[x]),
- keys,
- {})
- return pluck_fn
現在開始我們可以做什么？
函數式代碼與其他風格的代碼可以很好地共存。本文中的轉換實現可以應用于任何語言的任何代碼庫。試著應用到你自己的代碼中。
想想特工瑪麗、伊絲拉和山姆。轉換列表迭代為 map 和 reduce 。
想想車賽。將代碼分解為函數。將這些函數轉成函數式的。將重復過程的循環轉成遞歸。
想想樂隊。將一系列操作轉為管道。
注：
- 不可變數據是無法更改的。某些語言（如
Clojure）默認就是所有值都不可變。任何『變更』操作都會復制該值，更改副本然后返回更改后的副本。這消除了不完整模型下程序可能進入狀態所帶來的Bug。 - 支持一等公民函數的語言允許像任何其他值一樣對待函數。這意味著函數可以創建，傳遞給函數，從函數返回，以及存儲在數據結構中。
- 尾調用優化是一個編程語言特性。函數遞歸調用時，會創建一個新的棧幀（
stack frame）。棧幀用于存儲當前函數調用的參數和本地值。如果函數遞歸很多次，解釋器或編譯器可能會耗盡內存。支持尾調用優化的語言為其整個遞歸調用序列重用相同的棧幀。像Python這樣沒有尾調用優化的語言通常會限制函數遞歸的次數（如數千次）。對于上面例子中race()函數，因為只有5個時間段，所以是安全的。 - 柯里化（
currying）是指將一個帶有多個參數的函數轉換成另一個函數，這個函數接受第一個參數，并返回一個接受下一個參數的函數，依此類推所有參數。 - 并行化（
parallelization）是指，在沒有同步的情況下，相同的代碼可以并發運行。這些并發處理通常運行在多個處理器上。 - 惰性求值（
lazy evaluation）是一種編譯器技術，可以避免在需要結果之前運行代碼。 - 如果每次重復執行都產生相同的結果，則過程就是確定性的。
