[TOC] # Hindley-Milner 類型簽名 ## 初識類型 剛接觸函數式編程的人很容易深陷類型簽名（type signatures）的泥淖。類型（type）是讓所有不同背景的人都能高效溝通的元語言。很大程度上，類型簽名是以 “Hindley-Milner” 系統寫就的，本章我們將一起探究下這個系統。 類型簽名在寫純函數時所起的作用非常大，大到英語都不能望其項背。這些簽名輕輕訴說著函數最不可告人的秘密。短短一行，就能暴露函數的行為和目的。類型簽名還衍生出了 “自由定理（free theorems）” 的概念。因為類型是可以推斷的，所以明確的類型簽名并不是必要的；不過你完全可以寫精確度很高的類型簽名，也可以讓它們保持通用、抽象。類型簽名不但可以用于編譯時檢測（compile time checks），還是最好的文檔。所以類型簽名在函數式編程中扮演著非常重要的角色——重要程度遠遠超出你的想象。 JavaScript 是一種動態類型語言，但這并不意味著要一味否定類型。我們還是要和字符串、數值、布爾值等等類型打交道的；只不過，語言層面上沒有相關的集成讓我們時刻謹記各種數據的類型罷了。別擔心，既然我們可以用類型簽名生成文檔，也可以用注釋來達到區分類型的目的。 JavaScript 也有一些類型檢查工具，比如 [Flow](http://flowtype.org/)，或者它的靜態類型方言 [TypeScript](http://www.typescriptlang.org/) 。由于本書的目標是讓讀者能夠熟練使用各種工具去書寫函數式代碼，所以我們將選擇所有函數式語言都遵循的標準類型系統。 ## 神秘的傳奇故事 從積塵已久的數學書，到浩如煙海的學術論文；從每周必讀的博客文章，到源代碼本身，我們都能發現 Hindley-Milner 類型簽名的身影。Hindley-Milner 并不是一個復雜的系統，但還是需要一些解釋和練習才能完全掌握這個小型語言的要義。 ```js // capitalize :: String -> String var capitalize = function(s){ return toUpperCase(head(s)) + toLowerCase(tail(s)); } capitalize("smurf"); //=> "Smurf" ``` 這里，`capitalize` 接受一個 `String` 并返回了一個 `String`。先別管實現，我們感興趣的是它的類型簽名。 在 Hindley-Milner 系統中，函數都寫成類似 `a -> b` 這個樣子，其中 `a` 和`b` 是任意類型的變量。因此，`capitalize` 函數的類型簽名可以理解為“一個接受 `String` 返回 `String` 的函數”。換句話說，它接受一個 `String` 類型作為輸入，并返回一個 `String` 類型的輸出。 再來看一些函數簽名： ```js // strLength :: String -> Number var strLength = function(s){ return s.length; } // join :: String -> [String] -> String var join = curry(function(what, xs){ return xs.join(what); }); // match :: Regex -> String -> [String] var match = curry(function(reg, s){ return s.match(reg); }); // replace :: Regex -> String -> String -> String var replace = curry(function(reg, sub, s){ return s.replace(reg, sub); }); ``` `strLength` 和 `capitalize` 類似：接受一個 `String` 然后返回一個 `Number`。 至于其他的，第一眼看起來可能會比較疑惑。不過在還不完全了解細節的情況下，你盡可以把最后一個類型視作返回值。那么 `match` 函數就可以這么理解：它接受一個 `Regex` 和一個 `String`，返回一個 `[String]`。但是，這里有一個非常有趣的地方，請允許我稍作解釋。 對于 `match` 函數，我們完全可以把它的類型簽名這樣分組： ```js // match :: Regex -> (String -> [String]) var match = curry(function(reg, s){ return s.match(reg); }); ``` 是的，把最后兩個類型包在括號里就能反映更多的信息了。現在我們可以看出 `match` 這個函數接受一個 `Regex` 作為參數，返回一個從 `String` 到 `[String]` 的函數。因為 curry，造成的結果就是這樣：給 `match` 函數一個 `Regex`，得到一個新函數，能夠處理其 `String` 參數。當然了，我們并非一定要這么看待這個過程，但這樣思考有助于理解為何最后一個類型是返回值。 ```js // match :: Regex -> (String -> [String]) // onHoliday :: String -> [String] var onHoliday = match(/holiday/ig); ``` 每傳一個參數，就會彈出類型簽名最前面的那個類型。所以 `onHoliday` 就是已經有了 `Regex` 參數的 `match`。 ```js // replace :: Regex -> (String -> (String -> String)) var replace = curry(function(reg, sub, s){ return s.replace(reg, sub); }); ``` 但是在這段代碼中，就像你看到的那樣，為 `replace` 加上這么多括號未免有些多余。所以這里的括號是完全可以省略的，如果我們愿意，可以一次性把所有的參數都傳進來；所以，一種更簡單的思路是：`replace` 接受三個參數，分別是 `Regex`、`String` 和另一個 `String`，返回的還是一個 `String`。 最后幾點： ```js // id :: a -> a var id = function(x){ return x; } // map :: (a -> b) -> [a] -> [b] var map = curry(function(f, xs){ return xs.map(f); }); ``` 這里的 `id` 函數接受任意類型的 `a` 并返回同一個類型的數據。和普通代碼一樣，我們也可以在類型簽名中使用變量。把變量命名為 `a` 和 `b` 只是一種約定俗成的習慣，你可以使用任何你喜歡的名稱。對于相同的變量名，其類型也一定相同。這是非常重要的一個原則，所以我們必須重申：`a -> b` 可以是從任意類型的 `a` 到任意類型的 `b`，但是 `a -> a` 必須是同一個類型。例如，`id` 可以是 `String -> String`，也可以是 `Number -> Number`，但不能是 `String -> Bool`。 相似地，`map` 也使用了變量，只不過這里的 `b` 可能與 `a` 類型相同，也可能不相同。我們可以這么理解：`map` 接受兩個參數，第一個是從任意類型 `a` 到任意類型 `b` 的函數；第二個是一個數組，元素是任意類型的 `a`；`map` 最后返回的是一個類型 `b` 的數組。 類型簽名的美妙令人印象深刻，希望你已經被它深深折服。類型簽名簡直能夠一字一句地告訴我們函數做了什么事情。比如 `map` 函數就是這樣：給定一個從 `a` 到 `b` 的函數和一個 `a` 類型的數組作為參數，它就能返回一個 `b` 類型的數組。`map` 唯一的明智之舉就是使用其函數參數調用每一個 `a`，其他所有操作都是噱頭。 辨別類型和它們的含義是一項重要的技能，這項技能可以讓你在函數式編程的路上走得更遠。不僅論文、博客和文檔等更易理解，類型簽名本身也基本上能夠告訴你它的函數性（functionality）。要成為一個能夠熟練讀懂類型簽名的人，你得勤于練習；不過一旦掌握了這項技能，你將會受益無窮，不讀手冊也能獲取大量信息。 這里還有一些例子，你可以自己試試看能不能理解它們。 ```js // head :: [a] -> a var head = function(xs){ return xs[0]; } // filter :: (a -> Bool) -> [a] -> [a] var filter = curry(function(f, xs){ return xs.filter(f); }); // reduce :: (b -> a -> b) -> b -> [a] -> b var reduce = curry(function(f, x, xs){ return xs.reduce(f, x); }); ``` `reduce` 可能是以上簽名里讓人印象最為深刻的一個，同時也是最復雜的一個了，所以如果你理解起來有困難的話，也不必氣餒。為了滿足你的好奇心，我還是試著解釋一下吧；盡管我的解釋遠遠不如你自己通過類型簽名理解其含義來得有教益。 不保證解釋完全正確...（譯者注：此處原文是“here goes nothing”，一般用于人們在做沒有把握的事情之前說的話。）注意看 `reduce` 的簽名，可以看到它的第一個參數是個函數，這個函數接受一個 `b` 和一個 `a` 并返回一個 `b`。那么這些 `a` 和 `b` 是從哪來的呢？很簡單，簽名中的第二個和第三個參數就是 `b` 和元素為 `a` 的數組，所以唯一合理的假設就是這里的 `b` 和每一個 `a` 都將傳給前面說的函數作為參數。我們還可以看到，`reduce` 函數最后返回的結果是一個 `b`，也就是說，`reduce` 的第一個參數函數的輸出就是 `reduce` 函數的輸出。知道了 `reduce` 的含義，我們才敢說上面關于類型簽名的推理是正確的。 ## 縮小可能性范圍 一旦引入一個類型變量，就會出現一個奇怪的特性叫做 *parametricity*（http://en.wikipedia.org/wiki/Parametricity ）。這個特性表明，函數將會*以一種統一的行為作用于所有的類型*。我們來研究下： ```js // head :: [a] -> a ``` 注意看 `head`，可以看到它接受 `[a]` 返回 `a`。我們除了知道參數是個`數組`，其他的一概不知；所以函數的功能就只限于操作這個數組上。在它對 `a` 一無所知的情況下，它可能對 `a` 做什么操作呢？換句話說，`a` 告訴我們它不是一個`特定`的類型，這意味著它可以是`任意`類型；那么我們的函數對*每一個*可能的類型的操作都必須保持統一。這就是 *parametricity* 的含義。要讓我們來猜測 `head` 的實現的話，唯一合理的推斷就是它返回數組的第一個，或者最后一個，或者某個隨機的元素；當然，`head` 這個命名應該能給我們一些線索。 再看一個例子： ```js // reverse :: [a] -> [a] ``` 僅從類型簽名來看，`reverse` 可能的目的是什么？再次強調，它不能對 `a` 做任何特定的事情。它不能把 `a` 變成另一個類型，或者引入一個 `b`；這都是不可能的。那它可以排序么？答案是不能，沒有足夠的信息讓它去為每一個可能的類型排序。它能重新排列么？可以的，我覺得它可以，但它必須以一種可預料的方式達成目標。另外，它也有可能刪除或者重復某一個元素。重點是，不管在哪種情況下，類型 `a` 的多態性（polymorphism）都會大幅縮小 `reverse` 函數可能的行為的范圍。 這種“可能性范圍的縮小”（narrowing of possibility）允許我們利用類似 [Hoogle](https://www.haskell.org/hoogle) 這樣的類型簽名搜索引擎去搜索我們想要的函數。類型簽名所能包含的信息量真的非常大。 ## 自由定理 類型簽名除了能夠幫助我們推斷函數可能的實現，還能夠給我們帶來*自由定理*（free theorems）。下面是兩個直接從 [Wadler 關于此主題的論文](http://ttic.uchicago.edu/~dreyer/course/papers/wadler.pdf) 中隨機選擇的例子： ```js // head :: [a] -> a compose(f, head) == compose(head, map(f)); // filter :: (a -> Bool) -> [a] -> [a] compose(map(f), filter(compose(p, f))) == compose(filter(p), map(f)); ``` 不用寫一行代碼你也能理解這些定理，它們直接來自于類型本身。第一個例子中，等式左邊說的是，先獲取數組的`頭部`（譯者注：即第一個元素），然后對它調用函數 `f`；等式右邊說的是，先對數組中的每一個元素調用 `f`，然后再取其返回結果的`頭部`。這兩個表達式的作用是相等的，但是前者要快得多。 你可能會想，這不是常識么。但根據我的調查，計算機是沒有常識的。實際上，計算機必須要有一種形式化方法來自動進行類似的代碼優化。數學提供了這種方法，能夠形式化直觀的感覺，這無疑對死板的計算機邏輯非常有用。 第二個例子 `filter` 也是一樣。等式左邊是說，先組合 `f` 和 `p` 檢查哪些元素要過濾掉，然后再通過 `map` 實際調用 `f`（別忘了 `filter` 是不會改變數組中元素的，這就保證了 `a` 將保持不變）；等式右邊是說，先用 `map` 調用 `f`，然后再根據 `p` 過濾元素。這兩者也是相等的。 以上只是兩個例子，但它們傳達的定理卻是普適的，可以應用到所有的多態性類型簽名上。在 JavaScript 中，你可以借助一些工具來聲明重寫規則，也可以直接使用 `compose` 函數來定義重寫規則。總之，這么做的好處是顯而易見且唾手可得的，可能性則是無限的。 # 類型約束 最后要注意的一點是，簽名也可以把類型約束為一個特定的接口（interface）。 ```js // sort :: Ord a => [a] -> [a] ``` 胖箭頭左邊表明的是這樣一個事實：`a` 一定是個 `Ord` 對象。也就是說，`a` 必須要實現 `Ord` 接口。`Ord` 到底是什么？它是從哪來的？在一門強類型語言中，它可能就是一個自定義的接口，能夠讓不同的值排序。通過這種方式，我們不僅能夠獲取關于 `a` 的更多信息，了解 `sort` 函數具體要干什么，而且還能限制函數的作用范圍。我們把這種接口聲明叫做*類型約束*（type constraints）。 ```js // assertEqual :: (Eq a, Show a) => a -> a -> Assertion ``` 這個例子中有兩個約束：`Eq` 和 `Show`。它們保證了我們可以檢查不同的 `a` 是否相等，并在有不相等的情況下打印出其中的差異。 我們將會在后面的章節中看到更多類型約束的例子，其含義也會更加清晰。 ## 總結 Hindley-Milner 類型簽名在函數式編程中無處不在，它們簡單易讀，寫起來也不復雜。但僅僅憑簽名就能理解整個程序還是有一定難度的，要想精通這個技能就更需要花點時間了。從這開始，我們將給每一行代碼都加上類型簽名。 [第 8 章: 特百惠](ch8.md)