Hindley-Milner 型別簽名

初識型別

剛接觸函數語言程式設計的人很容易深陷型別簽名(type signatures)的泥淖。型別(type)是讓所有不同背景的人都能高效溝通的元語言。很大程度上,型別簽名是以 “Hindley-Milner” 系統寫就的,本章我們將一起探究下這個系統。

型別簽名在寫純函式時所起的作用非常大,大到英語都不能望其項背。這些簽名輕輕訴說著函式最不可告人的祕密。短短一行,就能暴露函式的行為和目的。型別簽名還衍生出了 “自由定理(free theorems)” 的概念。因為型別是可以推斷的,所以明確的型別簽名並不是必要的;不過你完全可以寫精確度很高的型別簽名,也可以讓它們保持通用、抽象。型別簽名不但可以用於編譯時檢測(compile time checks),還是最好的文件。所以型別簽名在函數語言程式設計中扮演著非常重要的角色——重要程度遠遠超出你的想象。

JavaScript 是一種動態型別語言,但這並不意味著要一味否定型別。我們還是要和字串、數值、布林值等等型別打交道的;只不過,語言層面上沒有相關的整合讓我們時刻謹記各種資料的型別罷了。別擔心,既然我們可以用型別簽名生成文件,也可以用註釋來達到區分型別的目的。

JavaScript 也有一些型別檢查工具,比如 Flow,或者它的靜態型別方言 TypeScript 。由於本書的目標是讓讀者能夠熟練使用各種工具去書寫函數式程式碼,所以我們將選擇所有函數式語言都遵循的標準型別系統。

神祕的傳奇故事

從積塵已久的數學書,到浩如煙海的學術論文;從每週必讀的部落格文章,到原始碼本身,我們都能發現 Hindley-Milner 型別簽名的身影。Hindley-Milner 並不是一個複雜的系統,但還是需要一些解釋和練習才能完全掌握這個小型語言的要義。

//  capitalize :: String -> String
var capitalize = function(s){
  return toUpperCase(head(s)) + toLowerCase(tail(s));
}

capitalize("smurf");
//=> "Smurf"

這裡,capitalize 接受一個 String 並返回了一個 String。先別管實現,我們感興趣的是它的型別簽名。

在 Hindley-Milner 系統中,函式都寫成類似 a -> b 這個樣子,其中 ab 是任意型別的變數。因此,capitalize 函式的型別簽名可以理解為“一個接受 String 返回 String 的函式”。換句話說,它接受一個 String 型別作為輸入,並返回一個 String 型別的輸出。

再來看一些函式簽名:

//  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);
});

strLengthcapitalize 類似:接受一個 String 然後返回一個 Number

至於其他的,第一眼看起來可能會比較疑惑。不過在還不完全瞭解細節的情況下,你儘可以把最後一個型別視作返回值。那麼 match 函式就可以這麼理解:它接受一個 Regex 和一個 String,返回一個 [String]。但是,這裡有一個非常有趣的地方,請允許我稍作解釋。

對於 match 函式,我們完全可以把它的型別簽名這樣分組:

//  match :: Regex -> (String -> [String])
var match = curry(function(reg, s){
  return s.match(reg);
});

是的,把最後兩個型別包在括號裡就能反映更多的資訊了。現在我們可以看出 match 這個函式接受一個 Regex 作為引數,返回一個從 String[String] 的函式。因為 curry,造成的結果就是這樣:給 match 函式一個 Regex,得到一個新函式,能夠處理其 String 引數。當然了,我們並非一定要這麼看待這個過程,但這樣思考有助於理解為何最後一個型別是返回值。

//  match :: Regex -> (String -> [String])

//  onHoliday :: String -> [String]
var onHoliday = match(/holiday/ig);

每傳一個引數,就會彈出型別簽名最前面的那個型別。所以 onHoliday 就是已經有了 Regex 引數的 match

//  replace :: Regex -> (String -> (String -> String))
var replace = curry(function(reg, sub, s){
  return s.replace(reg, sub);
});

但是在這段程式碼中,就像你看到的那樣,為 replace 加上這麼多括號未免有些多餘。所以這裡的括號是完全可以省略的,如果我們願意,可以一次性把所有的引數都傳進來;所以,一種更簡單的思路是:replace 接受三個引數,分別是 RegexString 和另一個 String,返回的還是一個 String

最後幾點:

//  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 並返回同一個型別的資料。和普通程式碼一樣,我們也可以在型別簽名中使用變數。把變數命名為 ab 只是一種約定俗成的習慣,你可以使用任何你喜歡的名稱。對於相同的變數名,其型別也一定相同。這是非常重要的一個原則,所以我們必須重申:a -> b 可以是從任意型別的 a 到任意型別的 b,但是 a -> a 必須是同一個型別。例如,id 可以是 String -> String,也可以是 Number -> Number,但不能是 String -> Bool

相似地,map 也使用了變數,只不過這裡的 b 可能與 a 型別相同,也可能不相同。我們可以這麼理解:map 接受兩個引數,第一個是從任意型別 a 到任意型別 b 的函式;第二個是一個數組,元素是任意型別的 amap 最後返回的是一個型別 b 的陣列。

型別簽名的美妙令人印象深刻,希望你已經被它深深折服。型別簽名簡直能夠一字一句地告訴我們函式做了什麼事情。比如 map 函式就是這樣:給定一個從 ab 的函式和一個 a 型別的陣列作為引數,它就能返回一個 b 型別的陣列。map 唯一的明智之舉就是使用其函式引數呼叫每一個 a,其他所有操作都是噱頭。

辨別型別和它們的含義是一項重要的技能,這項技能可以讓你在函數語言程式設計的路上走得更遠。不僅論文、部落格和文件等更易理解,型別簽名本身也基本上能夠告訴你它的函式性(functionality)。要成為一個能夠熟練讀懂型別簽名的人,你得勤於練習;不過一旦掌握了這項技能,你將會受益無窮,不讀手冊也能獲取大量資訊。

這裡還有一些例子,你可以自己試試看能不能理解它們。

//  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。那麼這些 ab 是從哪來的呢?很簡單,簽名中的第二個和第三個引數就是 b 和元素為 a 的陣列,所以唯一合理的假設就是這裡的 b 和每一個 a 都將傳給前面說的函式作為引數。我們還可以看到,reduce 函式最後返回的結果是一個 b,也就是說,reduce 的第一個引數函式的輸出就是 reduce 函式的輸出。知道了 reduce 的含義,我們才敢說上面關於型別簽名的推理是正確的。

縮小可能性範圍

一旦引入一個型別變數,就會出現一個奇怪的特性叫做 parametricityhttp://en.wikipedia.org/wiki/Parametricity )。這個特性表明,函式將會以一種統一的行為作用於所有的型別。我們來研究下:

// head :: [a] -> a

注意看 head,可以看到它接受 [a] 返回 a。我們除了知道引數是個陣列,其他的一概不知;所以函式的功能就只限於操作這個陣列上。在它對 a 一無所知的情況下,它可能對 a 做什麼操作呢?換句話說,a 告訴我們它不是一個特定的型別,這意味著它可以是任意型別;那麼我們的函式對每一個可能的型別的操作都必須保持統一。這就是 parametricity 的含義。要讓我們來猜測 head 的實現的話,唯一合理的推斷就是它返回陣列的第一個,或者最後一個,或者某個隨機的元素;當然,head 這個命名應該能給我們一些線索。

再看一個例子:

// reverse :: [a] -> [a]

僅從型別簽名來看,reverse 可能的目的是什麼?再次強調,它不能對 a 做任何特定的事情。它不能把 a 變成另一個型別,或者引入一個 b;這都是不可能的。那它可以排序麼?答案是不能,沒有足夠的資訊讓它去為每一個可能的型別排序。它能重新排列麼?可以的,我覺得它可以,但它必須以一種可預料的方式達成目標。另外,它也有可能刪除或者重複某一個元素。重點是,不管在哪種情況下,型別 a 的多型性(polymorphism)都會大幅縮小 reverse 函式可能的行為的範圍。

這種“可能性範圍的縮小”(narrowing of possibility)允許我們利用類似 Hoogle 這樣的型別簽名搜尋引擎去搜索我們想要的函式。型別簽名所能包含的資訊量真的非常大。

自由定理

型別簽名除了能夠幫助我們推斷函式可能的實現,還能夠給我們帶來自由定理(free theorems)。下面是兩個直接從 Wadler 關於此主題的論文 中隨機選擇的例子:

// 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 也是一樣。等式左邊是說,先組合 fp 檢查哪些元素要過濾掉,然後再通過 map 實際呼叫 f(別忘了 filter 是不會改變陣列中元素的,這就保證了 a 將保持不變);等式右邊是說,先用 map 呼叫 f,然後再根據 p 過濾元素。這兩者也是相等的。

以上只是兩個例子,但它們傳達的定理卻是普適的,可以應用到所有的多型性型別簽名上。在 JavaScript 中,你可以藉助一些工具來宣告重寫規則,也可以直接使用 compose 函式來定義重寫規則。總之,這麼做的好處是顯而易見且唾手可得的,可能性則是無限的。

型別約束

最後要注意的一點是,簽名也可以把型別約束為一個特定的介面(interface)。

// sort :: Ord a => [a] -> [a]

胖箭頭左邊表明的是這樣一個事實:a 一定是個 Ord 物件。也就是說,a 必須要實現 Ord 介面。Ord 到底是什麼?它是從哪來的?在一門強型別語言中,它可能就是一個自定義的介面,能夠讓不同的值排序。通過這種方式,我們不僅能夠獲取關於 a 的更多資訊,瞭解 sort 函式具體要幹什麼,而且還能限制函式的作用範圍。我們把這種介面宣告叫做型別約束(type constraints)。

// assertEqual :: (Eq a, Show a) => a -> a -> Assertion

這個例子中有兩個約束:EqShow。它們保證了我們可以檢查不同的 a 是否相等,並在有不相等的情況下打印出其中的差異。

我們將會在後面的章節中看到更多型別約束的例子,其含義也會更加清晰。

總結

Hindley-Milner 型別簽名在函數語言程式設計中無處不在,它們簡單易讀,寫起來也不復雜。但僅僅憑簽名就能理解整個程式還是有一定難度的,要想精通這個技能就更需要花點時間了。從這開始,我們將給每一行程式碼都加上型別簽名。

第 8 章: 特百惠

results matching ""

    No results matching ""