跨越邊界: 用 Haskell 研究函數性編程

過去 50 年中，企業所使用的語言 —— COBOL、C、C++ 和 Java 語言，都是命令式 語言；它們讓您告訴您的程序如何 去完成其任務。函數性 編程語言讓您告訴程序去做什么。這篇文章通過介紹 Haskell 來研究函數性編程。（如果您閱讀過我的跨越邊界 系列中 關于使用另外一種函數性語言 Erlang 進行并發性編程的文章，可能已經有了一定的基礎。）

在我研究超越 Java（請參閱 參考資料）時，我采訪的三位專家提到了 Haskell，他們認為我應該探索一下這種語言。當時，我并不認為市場已經為函數性編程做好了準備，因為這一范式對于大多數程序員來說都太陌生了。我現在仍然不認為我們已經做好了準備。但是我開始欣賞函數性語言帶來的生產力和強大力量。我只是剛剛接觸 Haskell，但這種語言已經影響了我使用 Java 和 Ruby 語言解決問題的方式。

命令式語言及其不足

關于本系列 在 跨越邊界 系列中，作者 Bruce Tate 推動了這樣一個概念：今天的 Java 程序員可以通過學習其他方式和語言受益。Java 技術曾經是編程陣營中所有開發項目的最佳選擇，但這種情況已經發生了變化。其他框架正在塑造 Java 框架的構建方式，從其他語言中學到的概念有助于 Java 編程。所編寫的 Python（或 Ruby、Smalltalk 或 ... 請自由填空）代碼可以改變您編寫 Java 代碼的方式。 本系列介紹了完全不同于 Java 開發，但又直接適用于 Java 開發的編程概念和技術。在某些情況下，需要集成之后才能利用這些技術。在其他情況下，則可以直接應用這些概念。單獨的工具不如其他語言和框架影響 Java 社區的開發人員、框架、甚至基本手段的這個概念重要。

命令式編程由一系列帶有明確順序的語句構成，它們的算法和編程構造嚴重依賴于應用程序的狀態。很難想像沒有這些特征的編程語言，因為命令式語言 “告訴我如何做” 的方式是如此深刻地確立在我們的日常編程哲學中。命令式編程明確塑造了您的思維方式。但通過學習替代的函數性編程工具，可以擴展您思考問題的方式。請考慮以下這些命令式結構：

• 賦值。命令式編程的用戶對賦值的依賴要超過其他編程技術。函數性編程最多允許為每個變量賦值一次。改變值的賦值被叫做 破壞性賦值，是不允許的。例如，多數函數性語言不允許 x = x + 1。
  
  
• 迭代。命令式編程利用迭代來處理許多不同類型的數據結構。許多命令式控制依賴破壞性賦值進行迭代。
  
  
• 副作用。在命令式語言中，輸入相同而可能返回不同值的方法，都有副作用。而對應用程序的狀態變量有影響的方法也有副作用。函數性編程沒有副作用。

如果以前沒用過函數性語言，那么就很難想像如何編寫沒有破壞性賦值和副作用的應用程序。但是這些基本特征給命令性語言帶來了一些更嚴重的問題：

• 正確性問題。有副作用的方法可能返回一個值，但同時也修改了應用程序的狀態。副作用把驗證程序正確的數學問題復雜化。但是復雜不僅僅是數學問題：副作用還使得測試、理解、分析和記錄程序的行為更加困難。
  
  
• 基于順序的 bug。許多優化依賴于對關鍵編程指令重新排序來提高性能。當依賴特定順序的程序被重新排序時，錯誤就發生了。
  
  
• 并發性問題?？勺儬顟B消失時，差不多所有的并發性問題也隨之消失。Brian Goetz 在 Java Concurrency in Practice（請參閱 參考資料）中，用 “這是愚蠢的可變狀態“ 規則結束了第一章。

不管信還是不信，不必強行規定操作的順序或承擔副作用，也可以有效地編程。

回頁首

函數性編程簡介

在數學中，函數把每個輸入映射到一個特定的輸出。函數性編程范式使用數學函數表達程序。函數性語言并不執行命令，而是通過表示、計算數學函數來解決問題。函數性語言通常有以下兩個特征：

• 不可變的數據。純粹的函數性語言不依賴保存或檢索狀態的操作，因此不允許破壞性賦值。
• 無副作用。用相同的輸入調用函數，總是返回相同的值。

對大多數函數性語言來說，這有點過于簡化，但是只是過了一點點。函數叫做單體（monad），被用來以數學方式表達狀態的變化，而 Haskell 這樣的函數性語言則用單體來處理輸入/輸出并管理狀態中的變化。

看到函數性編程的一些局限性后，您可能認為這種編程范式是一種倒退，但請繼續往下閱讀。函數性語言不是軟弱無力的。實際上，語言專家們通常相信函數性語言操作的抽象級別要比面向對象語言高。它們提供了命令式語言通常不提供的一些工具。在這篇文章中，將看到一些工具的工作效果。

回頁首

使用 Haskell

有兩個 Haskell 實現值得注意：Hugs 和 Glasgow Haskell Compiler（GHC）（請參閱 參考資料）。還有許多其他 Haskell 編譯器和解釋器，包括 Hugs 和 GHC 的分支，但是它們是主要的兩個。如果剛接觸 Haskell，那么 Hugs 解釋器是個不錯的選擇，因為它安裝和理解起來都比較容易。Hugs 有兩方面嚴重的限制：它缺乏編譯器，不能使用獨立函數；必須從文件裝入全部函數。更嚴謹的程序員會采用 GHC。它的解釋器略慢一些，但是它有編譯器模式，還允許獨立函數。在這篇文章中，我使用 Hugs，所以如果您想根據本文編寫代碼，也應當使用它，因為這兩套軟件使用的術語略有不同。

用 Hugs 編碼

請下載適合您操作系統的 Hugs （請參閱 參考資料）并啟動它。我把我信任的 Macbook Pro 放在一邊，而用我的 Windows 機器，這是為了得到一個可以快速安裝的環境。WinHugs 這個 Hugs 實現在 Windows 平臺上有一個簡單的一按即可的安裝程序。

將看到一個帶有 Hugs 提示符的解釋器窗口。啟動即可。輸入一些數字和數學表達式，如清單 1 所示。將看到 Hugs 返回數學表達式的結果。這正是在函數性語言中期待的行為。

Haskell 98 mode: Restart with command line option -98 to enable extensions
            Type :? for help
            Hugs>5
            5
            Hugs>5+4
            9
            

Haskell 擁有強大的類型模型。語言是強類型的，這意味著您只能在類型的某個實例上完成允許的操作。（例如，如果想把數字添加到字符串上，Hugs 會報錯。）Haskell 是靜態類型化的，所以一旦給變量分配了值，那么變量就會一直維持相同的類型。Haskell 會做一些類型推斷，這意味著它會根據程序中的語義線索來推斷元素的類型，所以您會看到我在使用 有些函數時沒有聲明相關的類型。如果使用類型模糊不清或者在函數中使用不支持的類型，Haskell 會報錯。Haskell 還有子類型，而且完全是多態的；這些特性超出了本文的范圍，但如果您對此感興趣，它們也值得研究。

既然已經看到了一些原語類型，例如整型，現在可以繼續了解一些更為復雜的類型了。通常，一個語言中可用的數據結構定義了語言的使用方式。C 使用 struct、Java 使用 class。Haskell 不使用這兩種數據結構。

Haskell 中最突出的三種數據結構是：tuple、列表（list） 和用戶定義的類型。我將著重介紹前兩種。tuple 要包含于括號 ( ) 之中，它有固定長度。tuple 包含固定類型的原語元素，甚至可以包含其他 tuple 或列表。相比之下，列表的長度可變，由同類元素構成。用 [ ] 包含列表。您可使用 Hugs 來體會 tuple 和列表，如清單 2 所示：

Hugs> [1,2]
            [1,2]
            Hugs> [1,"a"]
            ERROR - Cannot infer instance
            *** Instance   : Num [Char]
            *** Expression : [1,"a"]
            Hugs> (1,2,3)
            (1,2,3)
            Hugs> (1,"a")
            (1,"a")
            Hugs> [(1,2),(3,4)]
            [(1,2),(3,4)]
            Hugs> [(1,2),(3,4),(5,6,7)]
            ERROR - Type error in list
            *** Expression     : [(1,2),(3,4),(5,6,7)]
            *** Term           : (5,6,7)
            *** Type           : (c,d,e)
            *** Does not match : (a,b)
            

在清單 2 中，可以看到 tuple 中的每個元素可以是不同類型的，但列表中的元素必須是相同類型的。而且，如果您使用一個 tuple 列表，那么每個 tuple 的長度必須相同，每個 tuple 中的第 n 個元素必須與列表中所有其他 tuple 中的第 n 個元素匹配。

如您所料，Haskell 有許多在列表上操作的函數。最簡單的就是 head 和 tail。 head 返回列表的第一個元素，tail 返回其他的元素。清單 3 顯示了一些簡單的列表函數：

Hugs> [1,2,3,4,5]
            [1,2,3,4,5]
            Hugs> length [1,2,3,4,5]
            5
            Hugs> head [1,2,3,4,5]
            1
            Hugs> tail [1,2,3,4,5]
            [2,3,4,5]
            

在清單 3 中，可以看到 head 返回了一個元素，tail 返回了一列元素。稍后還會看到（在 編寫函數 中）這些函數如何構成了 Haskell 中眾多遞歸函數的基礎。

在構建列表時，使用 : 操作符，叫做構造（cons） 操作符（用來構造）。構建列表時，只是把元素傳遞給另一個列表?？梢园言S多構建操作串在一起。

字符串只是字符列表的語法代稱而已，像 [1,2,3] 這樣的列表則是 1:2:3:[] 的語法代稱。這個特性使得字符串操作更容易實現。清單 4 顯示了構造操作符的的工作方式以及如何用一個字符序列構建一個字符串：

Hugs> 6:[]
            [6]
            Hugs> 6:[7]
            [6,7]
            Hugs> 6:7:[]
            [6,7]
            Hugs> 'd':'o':'g':' ':'h':'a':'s':' ':'f':'l':'e':'a':'s':[]
            "dog has fleas"
            

在 Haskell 中，您會發現在字符串和列表中這種語法代稱非常普遍。 但是只要記?。阂磺卸际呛瘮?。

把函數當成數據

Haskell 允許把函數當成數據。這項重要的功能讓眾多的 Haskell 函數可以接受函數作為參數。這個策略讓您能夠用不同的方式把函數應用到函數的每個元素。清單 5 顯示了一系列函數，它們把函數應用到列表的每個元素：

Hugs> :l Char
            Char> map toUpper "Hello"
            "HELLO"
            Char> filter isUpper "To Be or Not to Be"
            "TBNB"
            Char> foldr (max) 0 [1,2,3,2,1]
            3
            Char> foldr (+) 0 [1,2,3,2,1]
            9
            

:l 命令裝入模塊。然后可以調用 Char 模塊中的函數。（其他版本的 Haskell 支持 Char.toUpper，但是 Hugs 不支持，所以要先裝入模塊，然后再利用模塊中的函數。）第一個語句在列表的每個元素上調用函數（本例中為 toUpper，用于把字符轉成大寫）。因為 Haskell 的字符串就是字符列表，所以得到的是 "HELLO" 字符串。filter 函數為列表的每個元素調用一個測試函數，測試函數返回布爾值，當測試函數返回 True 時，還包含列表的元素。

fold 函數要略微復雜一些。它有兩種形式：foldl 和 foldr。fold 函數接受一個函數、一個元素和一個列表?？梢赃@樣來看待 fold 函數：

1. 從列表的左側（foldl）右側（foldr）開始放置元素。
2. 把操作符放在列表的所有元素之間。
3. 從列表的一側到另一側應用操作符，對于 foldl 是從左側開始，對于 foldr 是從右側開始。

例如，foldr (+) 0 [1,2,3] 可歸納為 1 + (2 + (3 + 0)) 也就是 6。有些時候，順序會有影響，這就是為什么 Haskell 既提供了 foldr（右聯，從右至左構建）又提供了 foldl （左聯，從左至右構建）的原因。在處理列表時，fold 函數提供了累積任何二進制計算結果的好方法。

把函數組合起來

在 Haskell 程序中，可以用許多不同的方式組合函數。用復雜的方式組合函數，是函數性語言生產力的關鍵，這是因為這可不斷提高抽象的層次。

用復雜的方式組合函數，是函數性語言生產力的關鍵，這是因為這可不斷提高抽象的層次。

例如，假設有一個 Java 應用程序，它計算句子中大寫字母的數量。需要對列表進行迭代，每遇到一個大寫字母，就要將一個本地變量加 1。在 Haskell 中，只需用 length (filter (isUpper) "To Be or Not to Be") 取得過濾列表的長度即可。Haskell 程序員就是這樣避免了使用破壞性更新。每個函數都在內部保存中間結果，程序員不必考慮這類細節。

回頁首

編寫函數

如果您使用的是 Hugs，那么需要在獨立的源文件中編寫函數。WinHugs 可以很好的集成我的編輯器，所以不會造成太大的負擔。應當把函數放在模塊中，然后用 :l 命令裝入模塊。在清單 5 中已經看到，我裝入了系統模塊 Char。模塊名稱以及包含模塊的文件，要用大寫字母開始.函數名用小寫字母開始。Haskell 程序文件的擴展名是 .hs。

可以注意到：Haskell 程序頻繁地用遞歸來解決問題。Java 開發人員由于性能的原因和堆棧深度的限制，通常會避免遞歸。在處理遞歸時，Haskell 有兩大優勢：Haskell 優化了尾部遞歸，Haskell 是惰性的。

尾部遞歸優化意味著當遞歸發生在函數末尾時，編譯器或解釋器可以把遞歸表示成迭代。尾部遞歸優化沒有堆棧開銷，所以這個策略降低了把遞歸處理成簡單迭代的成本。為了理解 “惰性” 的含義，請把以下函數輸入名為 Generate.hs 的文件：

generate = 1:generate
            

這個函數是 1 的無窮列表。更精確地說，generate 通過構造操作符，把 1 添加到 generate —— 最初是個空列表。如果裝入并執行這個函數，就會進入無窮遞歸循環，因為沒有什么能夠停止遞歸。但奇怪的是，可以在應用程序中使用 generate 的結果，如清單 6 所示：

Hugs> :l Generate
            Main> head generate
            1
            Main> head (tail generate)
            1
            

雖然 generate 代表 1 的無窮列表，但 Haskell 只計算列表中自己需要的部分。在清單 6 中，第一個命令裝入函數，第二個得到頭（或第一個）元素，第三個命令得到末尾的頭（或第二個）元素。Haskell 只計算列表的頭兩個元素。剩下的被延遲，只在需要的時候計算。這種惰性處理的風格使得函數性語言的效率出人意料，而且支持其他編程語言中得不到的叫做無限流 的強大抽象（請參閱 參考資料）。

在大多數教程中可以發現的大多數經典 Haskell 函數都是遞歸的數學函數，例如 Fibonaclearcase/" target="_blank" >cci 函數和階乘。Fibonacci 序列的定義是：由 1 和 1 開始的序列前兩個數字的和。所以，Fibonacci 序列的前五個數字是 1、1、(1+1) = 2、(1+2) = 3 和 (2+3) = 5。Haskell 實現的這個序列與它的數學定義非常相似，如清單 7 所示：

fib 1 = 1
            fib 2 = 1
            fib x = fib(x-1) + fib(x-2)
            

可以把清單 7 中的代碼輸入到名為 Fib.hs 的文件中，用 :l fib 裝入它，并輸入 fib(4) 來運行它，生成序列的第四個數字。請注意，我不需要聲明保存中間結果的變量。在這個示例中，可以看到更高級別抽象的示例。如果您的問題集恰好適合 Haskell，那么更高級別的抽象就適合您。如果不適合，這種更高級別的抽象將使您陷入麻煩。

可以用與 Fibonacci 序列基本相同的方式對待階乘。x 的階乘就是從 1 到 x 的所有數字的乘積。在 Haskell 中，可以定義一個計算階乘的函數，如清單 8 所示：

factorial 1 = 1
            factorial x = x * factorial(x-1)
            

對列表的遍歷也采用同樣的工作方式。處理列表時，要處理第一個節點，然后處理列表剩下的部分（剩下的也是列表）。清單 9 顯示了計算列表中所有元素之和的一個遞歸函數：

sum [] = 0
            sum (h:t) = h + sum(t)
            

如果您以前沒見過這種模式，那么可能需要一點時間來習慣它。第一行說明空列表的和是 0。第二行代表的概念在幾乎所有函數性語言中都很普遍。(h:t) 把列表表示成 tuple，列表的頭（包含第一個元素）在 h 內，列表剩余的元素包含在 t 中。由于尾部遞歸優化，這種方式是對列表進行迭代的一種非常簡單的方式。思維過程與代碼的匹配非常好：做第一件事，剩下的事后面再做；什么都不剩時，就完成了。

用同樣的方式也可以遍歷非常復雜的數據結構。只要多付出一點功夫，就能表達 B 樹 —— B 樹的每個節點都容納一個值和兩個分支。用 Haskell 表示的簡單 B 樹形式如下：

data Tree a = Null | Node (Tree a) a (Tree a)
            

在這個示例中，data 是構建抽象類型的手段。a 是類型。它告訴 Haskell：樹可以可以什么都不包含，也可以是由樹構成的，樹后面跟著值，后面又跟著另一個樹。樹中的每個節點都有一個值、一個左子節點和一個右子節點。（子節點可以是 null，也可以不為 null。）

遍歷樹的代碼看起來與遍歷列表的代碼非常像。如果想要 null 樹的匯總為 null，典型節點的匯總是左樹的匯總加上值的匯總和右樹的匯總，請看清單 10：

sum_tree :: Tree Integer -> Integer
            sum_tree Null = 0
            sum_tree (Node left val right) = sum_tree left + val + sum_tree right
            

在清單 10 中，第一行定義了函數使用的類型。 sum_tree :: Tree Integer -> Integer 意味著函數 sum_tree 要接受一個 Integer 的 Tree 作為參數，并返回 Integer。下兩行代碼指定函數?？諛涞膮R總是零，其他樹的匯總是左樹加上 Integer 的值再加上右樹的值。

現在可以把它放在 Tree.hs 中，如清單 11 所示：

data Tree a = Null | Node (Tree a) a (Tree a)
            sum_tree :: Tree Integer -> Integer
            sum_tree Null = 0
            sum_tree (Node left val right) = sum_tree left + val + sum_tree right
            t::Tree Integer
            t=Node Null 4 Null
            

在這個示例中，t::Tree Integer 把 Tree 綁定到一個類型，下一行把 t 綁定到一個值?？梢杂?:l Tree 把清單 11 裝入 Hugs，并輸入 sum_tree t。也可以表示更復雜的樹，例如 Node Null 6 (Node Null 7 Null) 表示代碼一個右節點的樹?？梢园巡煌臉浞旁?t 中，然后再次運行 sum_tree 來感受一下。（請記住，每次試驗時都需要重新裝入函數。）

回頁首

回顧函數性 “限制”

Haskell 能夠很好地處理數據結構。因為把字符串看成是字符的簡單列表，所以 Haskell 不僅能很好地處理各種形式的文本，您還可以有效地處理樹、復雜的數學問題以及嵌套結構。函數性語言被頻繁地用來構建編譯器或者解析語言的工具，因為語言通常是用語法樹表示的。因為可以在數據結構中包含函數，所以函數性語言構成了元編程的優秀平臺。

現在已經看到了函數性語言的基礎，接下來可以開始了解，您要如何在沒有副作用和對狀態只有有限支持的環境下生活。正如我在前面提到過的，單體可以表示狀態的變化。但是即使用了單體，管理狀態也是困難的 —— 所以不要嘗試這樣做。相反，可以考慮通過定義不需要中間狀態的復合函數來解決問題的方式。不要考慮迭代，而應使用遞歸或以下某個函數 —— map、filter 或 fold，它們會把表達式應用到列表的每個元素。要使用函數性語言，只需要放棄命令式編程的風格。學習用更加函數性的風格進行編程，有以下好處：

• 可以用更緊湊的方式表示思想。
• 通過避免副作用，可以限制應用程序某些類型的 bug 的影響。
• 通過減少本地變量，可以讓代碼更具伸縮性。

函數性語言極大地影響了編程的思考方式。多年以來，MIT 的程序員最初使用了 Lisp，因為這種語言能夠有力地幫助程序員學習如何在更高層次的抽象上工作。

本文僅僅觸及到了函數性語言的皮毛。我鼓勵您下載 Haskell 或其他函數性語言，親自動手去體驗它。我猜，它會改造您對編程的思考方式。