用Python進行基礎的函數式編程的教程

許多函數式文章講述的是組合，流水線和高階函數這樣的抽象函數式技術。本文不同，它展示了人們每天編寫的命令式，非函數式代碼示例，以及將這些示例轉換為函數式風格。
文章的第一部分將一些短小的數據轉換循環重寫成函數式的maps和reduces。第二部分選取長一點的循環，把他們分解成單元，然后把每個單元改成函數式的。第三部分選取一個很長的連續數據轉換循環，然后把它分解成函數式流水線。
示例都是用Python寫的，因為很多人覺得Python易讀。為了證明函數式技術對許多語言來說都相同，許多示例避免使用Python特有的語法：map，reduce，pipeline。
導引
當人們談論函數式編程，他們會提到非常多的“函數式”特性。提到不可變數據1，第一類對象2以及尾調用優化3。這些是幫助函數式編程的語言特征。提到mapping（映射），reducing（歸納），piplining（管道），recursing（遞歸），currying4（科里化）;以及高階函數的使用。這些是用來寫函數式代碼的編程技術。提到并行5，惰性計算6以及確定性。這些是有利于函數式編程的屬性。
忽略全部這些?？梢杂靡痪湓拋砻枋龊瘮凳酱a的特征：避免副作用。它不會依賴也不會改變當前函數以外的數據。所有其他的“函數式”的東西都源于此。當你學習時把它當做指引。

這是一個非函數式方法：    
a = 0
def increment1():
  global a
  a += 1

這是一個函數式的方法：    
def increment2(a):
  return a + 1

不要在lists上迭代。使用map和reduce。
Map（映射）

Map接受一個方法和一個集合作為參數。它創建一個新的空集合，以每一個集合中的元素作為參數調用這個傳入的方法，然后把返回值插入到新創建的集合中。最后返回那個新集合。

這是一個簡單的map，接受一個存放名字的list，并且返回一個存放名字長度的list：    
name_lengths = map(len, ["Mary", "Isla", "Sam"])
 
print name_lengths
# => [4, 4, 3]

接下來這個map將傳入的collection中每個元素都做平方操作：    
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重寫下面的代碼。它接受由真名組成的list作為參數，然后用一個更加穩定的策略產生一個代號來替換這些名字。    
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是累加和也就是在之前的元素上執行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.' 初始的累加和由第三個參數來指定。這樣就允許了集合中元素的類型可以與累加器不同。
為什么map和reduce更好？
首先，它們大多是一行代碼。
二、迭代中最重要的部分：集合，操作和返回值，在所有的map和reduce中總是在相同的位置。
三、循環中的代碼可能會改變之前定義的變量或之后要用到的變量。照例，map和reduce是函數式的。
四、map和reduce是元素操作。每次有人讀到for循環，他們都要逐行讀懂邏輯。幾乎沒有什么規律性的結構可以幫助理解代碼。相反，map和reduce都是創建代碼塊來組織復雜的算法，并且讀者也能非?？斓睦斫庠夭⒃谀X海中抽象出來?！班?，代碼在轉換集合中的每一個元素。然后結合處理的數據成一個輸出?！?br /> 五、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字典列表到平均高度。不要嘗試把多個轉換捆綁在一起。把每一個放在獨立的一行，并且把結果保存在命名良好的變量中。代碼可以運行后，立刻凝練。
我的方案：    
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()
想要理解這段代碼，讀者只需要看主循環?！比绻鹴ime不為0，運行下run_step_of_race和draw，在檢查下time?！叭绻x者想更多的理解這段代碼中的run_step_of_race或draw，可以讀方法里的代碼。
注釋沒有了。代碼是自描述的。
把代碼分解提煉進方法里是非常好且十分簡單的提高代碼可讀性的方法。
這個技術用到了方法，但是只是當做常規的子方法使用，只是簡單地將代碼打包。根據指導，這些代碼不是函數式的。代碼中的方法使用了狀態，而不是傳入參數。方法通過改變外部變量影響了附近的代碼，而不是通過返回值。為了搞清楚方法做了什么，讀者必須仔細閱讀每行。如果發現一個外部變量，必須找他它的出處，找到有哪些方法修改了它。
移除狀態
下面是函數式的版本：    
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_positions直接傳進方法race中。第二，方法接受參數。第三，方法里沒有實例化變量。所有的數據變化都在返回值中完成。rece() 使用run_step_of_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()的方法。接受一個string和一個用于存放zero()和one()模式的規則方法的list。在string上調用第一個規則。除非返回None，不然它會繼續接受返回值并且在string上調用第二個規則。除非返回None，不然它會接受返回值，并且調用第三個規則。等等。如果有哪一個規則返回None，rule_sequence()方法停止，并返回None。不然，返回最后一個規則方法的返回值。
下面是一個示例輸出：    
print rule_sequence('0101', [zero, one, zero])
# => 1
 
print rule_sequence('0101', [zero, zero])
# => None

This is the imperative version of 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:])
使用流水線
在之前的章節，一些命令式的循環被重寫成遞歸的形式，并被用以調用輔助方法。在本節中，會用pipline技術重寫另一種類型的命令式循環。
下面有個存放三個子典型數據的list，每個字典存放一個樂隊相關的三個鍵值對：姓名，不準確的國籍和激活狀態。format_bands方法循環處理這個list。    
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'}]

擔心源于方法的名稱?！眆ormat” 是一個很模糊的詞。仔細查看代碼，這些擔心就變成抓狂了。循環中做三件事。鍵值為'country'的值被設置為'Canada'。名稱中的標點符號被移除了。名稱首字母改成了大寫。但是很難看出這段代碼的目的是什么，是否做了它看上去所做的。并且代碼難以重用，難以測試和并行。
和下面這段代碼比較一下：    
print pipeline_each(bands, [set_canada_as_country,
              strip_punctuation_from_name,
              capitalize_names])

這段代碼很容易理解。它去除了副作用，輔助方法是函數式的，因為它們看上去是鏈在一起的。上次的輸出構成下個方法的輸入。如果這些方法是函數式的，那么就很容易核實。它們很容易重用，測試并且也很容易并行。
pipeline_each()的工作是傳遞bands，一次傳一個，傳到如set_cannada_as_country()這樣的轉換方法中。當所有的bands都調用過這個方法之后，pipeline_each()將轉換后的bands收集起來。然后再依次傳入下一個方法中。
我們來看看轉換方法。
    
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())
每一個都將band的一個key聯系到一個新的value上。在不改變原值的情況下是很難做到的。assoc()通過使用deepcopy()根據傳入的dictionary產生一個拷貝來解決這個問題。每個轉換方法修改這個拷貝，然后將這個拷貝返回。
似乎這樣就很好了。原始Band字典不再擔心因為某個鍵值需要關聯新的值而被改變。但是上面的代碼有兩個潛在的副作用。在方法strip_punctuation_from_name()中，未加標點的名稱是通過在原值上調用replace()方法產生的。在capitalize_names()方法中，將名稱的首字母大寫是通過在原值上調用title()產生的。如果replace()和title()不是函數式的，strip_punctuation_from_name()和capitalize_names()也就不是函數式的。
幸運的是，replace() 和 title()并不改變它們所操作的string。因為Python中的strings是不可變的。例如，當replace()操作band的名稱字符串時，是先拷貝原字符串，然后對拷貝的字符串做修改。嘖嘖。
Python中string和dictionaries的可變性比較闡述了類似Clojure這類語言的吸引力。程序員永遠不用擔心數據是否可變。數據是不可變的。
練習4。試著重寫pipeline_each方法?？紤]操作的順序。每次從數組中拿出一個bands傳給第一個轉換方法。然后類似的再傳給第二個方法。等等。
My solution:
我的方案：    
def pipeline_each(data, fns):
  return reduce(lambda a, x: map(x, a),
         fns,
         data)

所有的三個轉換方法歸結于對傳入的band的特定字段進行更改。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

There is a lot going on here. Let's take it piece by piece.

這段代碼做了很多事。讓我們一點一點的看。
一、call() 是一個高階函數。高階函數接受一個函數作為參數，或者返回一個函數?；蛘呦馽all()，兩者都有。
二、apply_fn() 看起來很像那三個轉換函數。它接受一個record（一個band），查找在record[key]位置的值，以這個值為參數調用fn，指定fn的結果返回到record的拷貝中，然后返回這個拷貝。
三、call() 沒有做任何實際的工作。當call被調用時，apply_fn()會做實際的工作。上面使用pipeline_each()的例子中，一個apply_fn()的實例會將傳入的band的country值改為”Canada“。另一個實例會將傳入的band的名稱首字母大寫。
四、當一個apply_fn() 實例運行時，fn和key將不再作用域中。它們既不是apply_fn()的參數，也不是其中的本地變量。但是它們仍然可以被訪問。當一個方法被定義時，方法會保存方法所包含的變量的引用：那些定義在方法的作用域外，卻在方法中使用的變量。當方法運行并且代碼引用一個變量時，Python會查找本地和參數中的變量。如果沒找到，就會去找閉包內保存的變量。那就是找到fn和key的地方。
五、在call()代碼中沒有提到bands。因為不管主題是什么，call()都可以為任何程序生成pipeline。函數式編程部分目的就是構建一個通用，可重用，可組合的函數庫。
干的漂亮。閉包，高階函數和變量作用域都被包含在段落里。喝杯檸檬水。
還需要在band上做一點處理。就是移除band上除了name和country之外的東西。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()可以這樣使用：    
print pipeline_each(bands, [call(lambda x: 'Canada', 'country'),
              call(lambda x: x.replace('.', ''), 'name'),
              call(str.title, 'name'),
              pluck(['name', 'country'])])

練習5。pluck()接受一系列的鍵值，根據這些鍵值去record中抽取數據。試著寫寫。需要用到高階函數。
我的方案：    
def pluck(keys):
  def pluck_fn(record):
    return reduce(lambda a, x: assoc(a, x, record[x]),
           keys,
           {})
  return pluck_fn

What now?
還有什么要做的嗎？
函數式代碼可以很好的和其他風格的代碼配合使用。文章中的轉換器可以用任何語言實現。試試用你的代碼實現它。
想想Mary，Isla 和 Sam。將對list的迭代，轉成maps和reduces操作吧。
想想汽車競賽。將代碼分解成方法。把那些方法改成函數式的。把循環處理轉成遞歸。
想想樂隊。將一系列的操作改寫成pipeline。
標注：
1、一塊不可變數據是指不能被改變的數據。一些語言像Clojure的語言，默認所有的值都是不可變的。任何的可變操作都是拷貝值，并對拷貝的值做修改并返回。這樣就消除了程序中對未完成狀態訪問所造成的bugs。
2、支持一等函數的語言允許像處理其他類型的值那樣處理函數。意味著方法可以被創建，傳給其他方法，從方法中返回以及存儲在其他數據結構里。
3、尾調用優化是一個編程語言特性。每次方法遞歸，會創建一個棧。棧用來存儲當前方法需要使用的參數和本地值。如果一個方法遞歸次數非常多，很可能會讓編譯器或解釋器消耗掉所有的內存。有尾調用優化的語言會通過重用同一個棧來支持整個遞歸調用的序列。像Python這樣的語言不支持尾調用優化的通常都限制方法遞歸的數量在千次級別。在race()方法中，只有5次，所以很安全。
4、Currying意即分解一個接受多個參數的方法成一個只接受第一個參數并且返回一個接受下一個參數的方法的方法，直到接受完所有參數。
5、并行意即在不同步的情況下同時運行同一段代碼。這些并發操作常常運行在不同的處理器上。
6、惰性計算是編譯器的技術，為了避免在需要結果之前就運行代碼。
7、只有當每次重復都能得出相同的結果，才能說處理是確定性的