函數式編程

知識 05-27

點擊上方

「

Python開發

」，選擇「置頂公眾號」

關鍵時刻，第一時間送達！

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

函數式編程的三大特性：

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
 x+y
    return
 incx
inc2 = inc(
2
)
inc5 = inc(5
)
print
 inc2(5
 
) 
# 輸出 7

print
 inc5(5
) # 輸出 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
 i 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(9
))
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, [1
, 2
, 3
, 4
, 5
])
# 輸出 15

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

計算數組中正數的平均值

num =[

2

, -5
, 9
, 7
, -2
, 5
, 3
, 1
, 0
, -3
, 8
]
positive_num_cnt = 0

positive_num_sum = 0

for
 i in
 range(len(num)):
    if
 num[i] > 0
:
        positive_num_cnt += 1

        positive_num_sum += num[i]
if
 positive_num_cnt > 0
:
    average = positive_num_sum / positive_num_cnt
print
 average
# 輸出 5

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

positive_num = filter(

lambda

 x: x>0
, num)
average = reduce(lambda
 x,y: x+y, positive_num) / len( positive_num )

C++11玩的法：

#

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

}

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

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實現

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 = 
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()

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

而把代碼邏輯封裝成了函數後，我們就相當於給每個相對獨立的程序邏輯取了個名字，於是代碼成了自解釋的

。

但是，你會發現，封裝成函數後，這些函數都會依賴於共享的變數來同步其狀態。於是，我們在讀代碼的過程時，每當我們進入到函數里，一量讀到訪問了一個外部的變數，我們馬上要去查看這個變數的上下文，然後還要在大腦里推演這個變數的狀態，我們才知道程序的真正邏輯。也就是說，

這些函數間必需知道其它函數是怎麼修改它們之間的共享變數的，所以，這些函數是有狀態的

。

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

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
 "

"
.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
]})

上面的代碼依然把程序的邏輯分成了函數，不過這些函數都是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 % 2
 != 0
:
        return

    num = num * 3

    num = "The Number: %s"
 % num
    return
 num
nums = [
1
, 2
, 3
, 4
, 5
, 6
, 7
, 8
, 9
, 10
]
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 % 2
 == 0
:
            yield
 num
def
 multiply_by_three
(nums)
:

    for
 num in
 nums:
        yield
 num * 3

def
 convert_to_string
(nums)
:

    for
 num in
 nums:
        yield
 "The Number: %s"
 % num
nums = [
1
, 2
, 3
, 4
, 5
, 6
, 7
, 8
, 9
, 10
]
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。

好了，根據前面的原則——「

使用Map & Reduce，不要使用循環

」，那我們用比較純樸的Map & Reduce吧。

def

 even_filter
(nums)
:

    return
 filter(lambda
 x: x%2
==0
, nums)
def
 multiply_by_three
(nums)
:

    return
 map(lambda
 x: x*3
, nums)
def
 convert_to_string
(nums)
:

    return
 map(lambda
 x: "The Number: %s"
 % x,  nums)
nums = [
1
, 2
, 3
, 4
, 5
, 6
, 7
, 8
, 9
, 10
]
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的，我們重要的品味其中的味道

。

參考

Wikipedia: Functional Programming

truly understanding the difference between procedural and functional

A practical introduction to functional programming

What is the difference between procedural programming and functional programming?

Can someone give me examples of functional programming vs imperative/procedural programming?

OOP vs Functional Programming vs Procedural

Python – Functional Programming HOWTO

感謝謝網友提供的shell風格的python pipeline：

class

 Pipe
(object)
:

    
def
 __init__
(self, func)
:

        self.func = func
    
def
 __ror__
(self, other)
:

        
def
 generator
()
:

            for
 obj in
 other:
                if
 obj is
 not
 None
:
                    yield
 self.func(obj)
        return
 generator()
@Pipe

def
 even_filter
(num)
:

    return
 num if
 num % 2
 == 0
 else
 None

@Pipe

def
 multiply_by_three
(num)
:

    return
 num*3

@Pipe

def
 convert_to_string
(num)
:

    return
 "The Number: %s"
 % num
@Pipe

def
 echo
(item)
:

    print
 item
    return
 item
def
 force
(sqs)
:

    for
 item in
 sqs: pass

nums = [
1
, 2
, 3
, 4
, 5
, 6
, 7
, 8
, 9
, 10
]