函數式程式設計

原文位址：http://coolshell.cn/articles/10822.html

作者：陳皓

++++++++++++++++++++++++++++++++++++++++++++++

當我們說起函數式程式設計來說，我們會看到如下函數式程式設計的長相：

函數式程式設計的三大特性：
- immutable data 不可變資料：像Clojure一樣，預設上變量是不可變的，如果你要改變變量，你需要把變量copy出去修改。這樣一來，可以讓你的程式少很多Bug。因為，程式中的狀态不好維護，在并發的時候更不好維護。（你可以試想一下如果你的程式有個複雜的狀态，當以後别人改你代碼的時候，是很容易出bug的，在并行中這樣的問題就更多了）
- first class functions：這個技術可以讓你的函數就像變量一樣來使用。也就是說，你的函數可以像變量一樣被建立，修改，并當成變量一樣傳遞，傳回或是在函數中嵌套函數。這個有點像Javascript的Prototype（參看Javascript的面向對象程式設計）
- 尾遞歸優化：我們知道遞歸的害處，那就是如果遞歸很深的話，stack受不了，并會導緻性能大幅度下降。是以，我們使用尾遞歸優化技術——每次遞歸時都會重用stack，這樣一來能夠提升性能，當然，這需要語言或編譯器的支援。Python就不支援。

函數式程式設計的幾個技術
- map & reduce ：這個技術不用多說了，函數式程式設計最常見的技術就是對一個集合做Map和Reduce操作。這比起過程式的語言來說，在代碼上要更容易閱讀。（傳統過程式的語言需要使用for/while循環，然後在各種變量中把資料倒過來倒過去的）這個很像C++中的STL中的foreach，find_if，count_if之流的函數的玩法。
- pipeline：這個技術的意思是，把函數執行個體成一個一個的action，然後，把一組action放到一個數組或是清單中，然後把資料傳給這個action list，資料就像一個pipeline一樣順序地被各個函數所操作，最終得到我們想要的結果。
- recursing 遞歸：遞歸最大的好處就簡化代碼，他可以把一個複雜的問題用很簡單的代碼描述出來。注意：遞歸的精髓是描述問題，而這正是函數式程式設計的精髓。
- currying：把一個函數的多個參數分解成多個函數，然後把函數多層封裝起來，每層函數都傳回一個函數去接收下一個參數這樣，可以簡化函數的多個參數。在C++中，這個很像STL中的bind_1st或是bind2nd。
- higher order function 高階函數：所謂高階函數就是函數當參數，把傳入的函數做一個封裝，然後傳回這個封裝函數。現象上就是函數傳進傳出，就像面向對象對象滿天飛一樣。

還有函數式的一些好處
- parallelization 并行：所謂并行的意思就是在并行環境下，各個線程之間不需要同步或互斥。
- lazy evaluation 惰性求值：這個需要編譯器的支援。表達式不在它被綁定到變量之後就立即求值，而是在該值被取用的時候求值，也就是說，語句如x:=expression; (把一個表達式的結果指派給一個變量)明顯的調用這個表達式被計算并把結果放置到 x 中，但是先不管實際在 x 中的是什麼，直到通過後面的表達式中到 x 的引用而有了對它的值的需求的時候，而後面表達式自身的求值也可以被延遲，最終為了生成讓外界看到的某個符号而計算這個快速增長的依賴樹。
- determinism 确定性：所謂确定性的意思就是像數學那樣 f(x) = y ，這個函數無論在什麼場景下，都會得到同樣的結果，這個我們稱之為函數的确定性。而不是像程式中的很多函數那樣，同一個參數，卻會在不同的場景下計算出不同的結果。所謂不同的場景的意思就是我們的函數會根據一些運作中的狀态資訊的不同而發生變化。

上面的那些東西太抽象了，還是讓我們來循序漸近地看一些例子吧。

我們先用一個最簡單的例子來說明一下什麼是函數式程式設計。

先看一個非函數式的例子：

int

cnt;

void

increment(){

cnt++;

那麼，函數式的應該怎麼寫呢？

int

increment(

int

cnt){

return

cnt+1;

你可能會覺得這個例子太普通了。是的，這個例子就是函數式程式設計的準則：不依賴于外部的資料，而且也不改變外部資料的值，而是傳回一個新的值給你。

我們再來看一個簡單例子：

def

inc(x):

def

incx(y):

return

return

incx

inc2

inc(

inc5

inc(

print

inc2(

# 輸出 7

print

inc5(

# 輸出 10

我們可以看到上面那個例子inc()函數傳回了另一個函數incx()，于是我們可以用inc()函數來構造各種版本的inc函數，比如：inc2()和inc5()。這個技術其實就是上面所說的Currying技術。從這個技術上，你可能體會到函數式程式設計的理念：把函數當成變量來用，關注于描述問題而不是怎麼實作，這樣可以讓代碼更易讀。

Map & Reduce

在函數式程式設計中，我們不應該用循環疊代的方式，我們應該用更為進階的方法，如下所示的Python代碼

name_len

map

len

, [

"hao"

"chen"

"coolshell"

])

print

name_len

# 輸出 [3, 4, 9]

你可以看到這樣的代碼很易讀，因為，這樣的代碼是在描述要幹什麼，而不是怎麼幹。

我們再來看一個Python代碼的例子：

def

toUpper(item):

return

item.upper()

upper_name

map

(toUpper, [

"hao"

"chen"

"coolshell"

])

print

upper_name

# 輸出 ['HAO', 'CHEN', 'COOLSHELL']

順便說一下，上面的例子個是不是和我們的STL的transform有些像？

#include <iostream>

#include <algorithm>

#include <string>

using

namespace

std;

int

main() {

string s=

"hello"

string out;

transform(s.begin(), s.end(), back_inserter(out), ::

toupper

);

cout << out << endl;

// 輸出：HELLO

在上面Python的那個例子中我們可以看到，我們寫義了一個函數toUpper，這個函數沒有改變傳進來的值，隻是把傳進來的值做個簡單的操作，然後傳回。然後，我們把其用在map函數中，就可以很清楚地描述出我們想要幹什麼。而不會去了解一個在循環中的怎麼實作的代碼，最終在讀了很多循環的邏輯後才發現原來是這個或那個意思。下面，我們看看描述實作方法的過程式程式設計是怎麼玩的（看上去是不是不如函數式的清晰？）：

upname

'HAO'

'CHEN'

'COOLSHELL'

lowname

[]

for

in

range

len

(upname)):

lowname.append( upname[i].lower() )

對于map我們别忘了lambda表達式：你可以簡單地了解為這是一個inline的匿名函數。下面的lambda表達式相當于：def func(x): return x*x

squares

map

lambda

x: x

x,

range

))

print

squares

# 輸出 [0, 1, 4, 9, 16, 25, 36, 49, 64]

我們再來看看reduce怎麼玩？（下面的lambda表達式中有兩個參數，也就是說每次從清單中取兩個值，計算結果後把這個值再放回去，下面的表達式相當于：((((1+2)+3)+4)+5) ）

print

reduce

lambda

x, y: x

y, [

])

# 輸出 15

Python中的除了map和reduce外，還有一些别的如filter, find, all, any的函數做輔助（其它函數式的語言也有），可以讓你的代碼更簡潔，更易讀。我們再來看一個比較複雜的例子：

計算數組中正數的平均值

num

positive_num_cnt

positive_num_sum

for

in

range

len

(num)):

if

num[i] >

positive_num_cnt

positive_num_sum

num[i]

if

positive_num_cnt >

average

positive_num_sum

positive_num_cnt

print

average

# 輸出 5

如果用函數式程式設計，這個例子可以寫成這樣：

positive_num

filter

lambda

x: x>

, num)

average

reduce

lambda

x,y: x

y, positive_num)

len

( positive_num )

C++11玩的法：

#include <iostream>

#include <algorithm>

#include <numeric>

#include <string>

#include <vector>

using

namespace

std;

vector num {2, -5, 9, 7, -2, 5, 3, 1, 0, -3, 8};

vector p_num;

copy_if(num.begin(), num.end(), back_inserter(p_num), [](

int

i){

return

(i>0);} );

int

average = accumulate(p_num.begin(), p_num.end(), 0) / p_num.size();

cout <<

"averge: "

<< average << endl;

我們可以看到，函數式程式設計有如下好處：

1）代碼更簡單了。

2）資料集，操作，傳回值都放到了一起。

3）你在讀代碼的時候，沒有了循環體，于是就可以少了些臨時變量，以及變量倒來倒去邏輯。

4）你的代碼變成了在描述你要幹什麼，而不是怎麼去幹。

最後，我們來看一下Map/Reduce這樣的函數是怎麼來實作的（下面是Javascript代碼）

map函數

var

map =

function

(mappingFunction, list) {

var

result = [];

forEach(list,

function

(item) {

result.push(mappingFunction(item));

});

return

result;

};

下面是reduce函數的javascript實作（謝謝 @下雨在家修正的我原來的簡單版本）

reduce函數

function

reduce(actionFunction, list, initial){

var

accumulate;

var

temp;

if

(initial){

accumulate = initial;

else

accumulate = list.shfit();

temp = list.shift();

while

(temp){

accumulate = actionFunction(accumulate,temp);

temp = list.shift();

return

accumulate;

};

Declarative Programming vs Imperative Programming

前面提到過多次的函數式程式設計關注的是：describe what to do, rather than how to do it. 于是，我們把以前的過程式的程式設計範式叫做 Imperative Programming – 指令式程式設計，而把函數式的這種範式叫做 Declarative Programming – 聲明式程式設計。

下面我們看一下相關的示例（本示例來自這篇文章）。

比如，我們有3輛車比賽，簡單起見，我們分别給這3輛車有70%的機率可以往前走一步，一共有5次機會，我們打出每一次這3輛車的前行狀态。

對于Imperative Programming來說，代碼如下（Python）：

from

random

import

random

time

car_positions

while

time:

# decrease time

time

print

''

for

in

range

len

(car_positions)):

# move car

if

random() >

0.3

car_positions[i]

# 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]

def

draw_car(car_position):

print

'-'

car_position

def

run_step_of_race():

global

time

time

move_cars()

def

draw():

print

''

for

car_position

in

car_positions:

draw_car(car_position)

time

car_positions

while

time:

run_step_of_race()

draw()

上面的代碼，我們可以從主循環開始，我們可以很清楚地看到程式的主幹，因為我們把程式的邏輯分成了幾個函數，這樣一來，我們的代碼邏輯也會變得幾個小碎片，于是我們讀代碼時要考慮的上下文就少了很多，閱讀代碼也會更容易。不像第一個示例，如果沒有注釋和說明，你還是需要花些時間了解一下。而把代碼邏輯封裝成了函數後，我們就相當于給每個相對獨立的程式邏輯取了個名字，于是代碼成了自解釋的。

但是，你會發現，封裝成函數後，這些函數都會依賴于共享的變量來同步其狀态。于是，我們在讀代碼的過程時，每當我們進入到函數裡，一量讀到通路了一個外部的變量，我們馬上要去檢視這個變量的上下文，然後還要在大腦裡推演這個變量的狀态，我們才知道程式的真正邏輯。也就是說，這些函數間必需知道其它函數是怎麼修改它們之間的共享變量的，是以，這些函數是有狀态的。

我們知道，有狀态并不是一件很好的事情，無論是對代碼重用，還是對代碼的并行來說，都是有副作用的。是以，我們要想個方法把這些狀态搞掉，于是出現了我們的 Functional Programming 的程式設計範式。下面，我們來看看函數式的方式應該怎麼寫？

from

random

import

random

def

move_cars(car_positions):

return

map

lambda

x: x

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'

'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'

'car_positions'

: [

]})

上面的代碼依然把程式的邏輯分成了函數，不過這些函數都是functional的。因為它們有三個症狀：

1）它們之間沒有共享的變量。

2）函數間通過參數和傳回值來傳遞資料。

3）在函數裡沒有臨時變量。

我們還可以看到，for循環被遞歸取代了（見race函數）—— 遞歸是函數式程式設計中帶用到的技術，正如前面所說的，遞歸的本質就是描述問題是什麼。

Pipeline

pipeline 管道借鑒于Unix Shell的管道操作——把若幹個指令串起來，前面指令的輸出成為後面指令的輸入，如此完成一個流式計算。（注：管道絕對是一個偉大的發明，他的設哲學就是KISS – 讓每個功能就做一件事，并把這件事做到極緻，軟體或程式的拼裝會變得更為簡單和直覺。這個設計理念影響非常深遠，包括今天的Web Service，雲計算，以及大資料的流式計算等等）

比如，我們如下的shell指令：

ps

auwwx |

awk

'{print $2}'

sort

-n |

xargs

echo

如果我們抽象成函數式的語言，就像下面這樣：

xargs(  echo, sort(n, awk(

'print $2'

, ps(auwwx)))  )

也可以類似下面這個樣子：

pids

for_each(result, [ps_auwwx, awk_p2, sort_n, xargs_echo])

好了，讓我們來看看函數式程式設計的Pipeline怎麼玩？

我們先來看一個如下的程式，這個程式的process()有三個步驟：

1）找出偶數。

2）乘以3

3）轉成字元串傳回

def

process(num):

# filter out non-evens

if

num

return

num

num

num

'The Number: %s'

num

return

num

nums

for

num

in

nums:

print

process(num)

# 輸出：

# None

# The Number: 6

# None

# The Number: 12

# None

# The Number: 18

# None

# The Number: 24

# None

# The Number: 30

我們可以看到，輸出的并不夠完美，另外，代碼閱讀上如果沒有注釋，你也會比較暈。下面，我們來看看函數式的pipeline（第一種方式）應該怎麼寫？

def

even_filter(nums):

for

num

in

nums:

if

num

yield

num

def

multiply_by_three(nums):

for

num

in

nums:

yield

num

def

convert_to_string(nums):

for

num

in

nums:

yield

'The Number: %s'

num

nums

pipeline

convert_to_string(multiply_by_three(even_filter(nums)))

for

num

in

pipeline:

print

num

# 輸出：

# The Number: 6

# The Number: 12

# The Number: 18

# The Number: 24

# The Number: 30

我們動用了Python的關鍵字 yield，這個關鍵字主要是傳回一個Generator，yield 是一個類似 return 的關鍵字，隻是這個函數傳回的是個Generator-生成器。所謂生成器的意思是，yield傳回的是一個可疊代的對象，并沒有真正的執行函數。也就是說，隻有其傳回的疊代對象被真正疊代時，yield函數才會正真的運作，運作到yield語句時就會停住，然後等下一次的疊代。（這個是個比較詭異的關鍵字）這就是lazy evluation。

注：yield的效果就是下次調用的時候函數記住了上次執行到的位置，比如這次處理的是清單nums中的第3個元素，下次調用的時候函數處理清單nums 中的第四個元素

好了，根據前面的原則——“使用Map & Reduce，不要使用循環”，那我們用比較純樸的Map & Reduce吧。

def

even_filter(nums):

return

filter

lambda

x: x

, nums)

def

multiply_by_three(nums):

return

map

lambda

x: x

, nums)

def

convert_to_string(nums):

return

map

lambda

x:

'The Number: %s'

x,  nums)

nums

pipeline

convert_to_string(

multiply_by_three(

even_filter(nums)

for

num

in

pipeline:

print

num

但是他們的代碼需要嵌套使用函數，這個有點不爽，如果我們能像下面這個樣子就好了（第二種方式）。

pipeline_func(nums, [even_filter,

multiply_by_three,

convert_to_string])

那麼，pipeline_func 實作如下：

def

pipeline_func(data, fns):

return

reduce

lambda

a, x: x(a),

fns,

data)

好了，在讀過這麼多的程式後，你可以回頭看一下這篇文章的開頭對函數式程式設計的描述，可能你就更有感覺了。

最後，我希望這篇淺顯易懂的文章能讓你感受到函數式程式設計的思想，就像OO程式設計，泛型程式設計，過程式程式設計一樣，我們不用太糾結是不是我們的程式就是OO，就是functional的，我們重要的品味其中的味道。

完

+++++++++++++++++++++++++++++++++++++++++++++++++

對上面用到的python中函數式程式設計文法糖的介紹參考

filter(function, sequence)：對sequence中的item依次執行function(item)，将執行結果為True的item組成一個List/String/Tuple（取決于sequence的類型）傳回：

>>> def f(x): return x % 2 != 0 and x % 3 != 0

>>> filter(f, range(2, 25))

[5, 7, 11, 13, 17, 19, 23]

>>> def f(x): return x != 'a'

>>> filter(f, "abcdef")

'bcdef'

map(function, sequence) ：對sequence中的item依次執行function(item)，見執行結果組成一個List傳回：

>>> def cube(x): return x*x*x

>>> map(cube, range(1, 11))

[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]

>>> def cube(x) : return x + x

...

>>> map(cube , "abcde")

['aa', 'bb', 'cc', 'dd', 'ee']

另外map也支援多個sequence，這就要求function也支援相應數量的參數輸入：

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

>>> map(add, range(8), range(8))

[0, 2, 4, 6, 8, 10, 12, 14]

reduce(function, sequence, starting_value)：對sequence中的item順序疊代調用function，如果有starting_value，還可以作為初始值調用，例如可以用來對List求和：

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

>>> reduce(add, range(1, 11))

55 （注：1+2+3+4+5+6+7+8+9+10）

>>> reduce(add, range(1, 11), 20)

75 （注：1+2+3+4+5+6+7+8+9+10+20）

lambda：這是Python支援一種有趣的文法，它允許你快速定義單行的最小函數，類似與C語言中的宏，這些叫做lambda的函數，是從LISP借用來的，可以用在任何需要函數的地方：

>>> g = lambda x: x * 2

>>> g(3)

>>> (lambda x: x * 2)(3)

我們也可以把filter map reduce 和lambda結合起來用，函數就可以簡單的寫成一行。

例如

kmpathes = filter(lambda kmpath: kmpath,

map(lambda kmpath: string.strip(kmpath),

string.split(l, ':')))

看起來麻煩，其實就像用語言來描述問題一樣，非常優雅。

對 l 中的所有元素以':'做分割，得出一個清單。對這個清單的每一個元素做字元串strip，形成一個清單。對這個清單的每一個元素做直接傳回操作(這個地方可以加上過濾條件限制)，最終獲得一個字元串被':'分割的清單，清單中的每一個字元串都做了strip，并可以對特殊字元串過濾。

[轉] http://hi.baidu.com/black/item/307001d18715fc322a35c747

---------------------------------------------------------------

lambda表達式傳回一個函數對象

例子：

func = lambda x,y:x+y

func相當于下面這個函數

def func(x,y):

return x+y

注意def是語句而lambda是表達式

下面這種情況下就隻能用lambda而不能用def

[(lambda x:x*x)(x) for x in range(1,11)]

map，reduce，filter中的function都可以用lambda表達式來生成！

map(function,sequence)

把sequence中的值當參數逐個傳給function，傳回一個包含函數執行結果的list。

如果function有兩個參數，即map(function,sequence1,sequence2)。

求1*1,2*2,3*3,4*4

map(lambda x:x*x,range(1,5))

傳回值是[1,4,9,16]

reduce(function,sequence)

function接收的參數個數隻能為2

先把sequence中第一個值和第二個值當參數傳給function，再把function的傳回值和第三個值當參數傳給

function，然後隻傳回一個結果。

求1到10的累加

reduce(lambda x,y:x+y,range(1,11))

傳回值是55。

filter(function,sequence)

function的傳回值隻能是True或False

把sequence中的值逐個當參數傳給function，如果function(x)的傳回值是True，就把x加到filter的傳回值裡面。一般來說filter的傳回值是list，特殊情況如sequence是string或tuple，則傳回值按照sequence的類型。

找出1到10之間的奇數

filter(lambda x:x%2!=0,range(1,11))

傳回值

[1,3,5,7,9]

如果sequence是一個string

filter(lambda x:len(x)!=0,'hello')傳回'hello'

filter(lambda x:len(x)==0,'hello')傳回''

make it simple, make it happen