函式的類型

函式跟資料結構一樣都有類型，它不只是特定於函式的概念，而是跟int, tuple<bool,float>等類型同等的概念。在c++函式的類型可以寫做如std::function<int(float,float)>，它可以放在tuple, array等容器裡，當然也可以作為函式的參數或是傳回值，如std::function<int(int)> twice(std::function<int(int)>)。rust的函式類型寫法回傳值被放在後面，這更符合閱讀習慣，例如 fn(f32, f32) -> i32，但它其實只能表達靜態函式，在這裡我們先暫時忘記這部分的差異。

能接受或是回傳函式的函式稱作高階函式，因為它把函式作為和資料結構同等的存在。之前提到過函式的參數列表可看作乘法類型，例如fn(f32, f32) -> i32可看作是接受(f32,f32)作為參數並回傳i32的函式，在函數式程式語言裡常常用currying寫成fn(f32) -> fn(f32) -> i32，也就是回傳接受第二個參數的函式，等到所有參數都到位了才會回傳i32（也有可能是先做部分運算，再回傳剩下運算的函式）。他回傳的函式帶有第一個參數的資訊，這被稱做閉包。這兩種寫法對嚴格控制副作用的程式語言來說是沒有區別的，因為從類型上它並沒有任何副作用，因此何時運算並不會影響回傳結果。

函式可看作帶有佔位符的表達式範本，就像printf的格式化字串一樣，呼叫函式就像是把範本裡的佔位符取代成給定的參數。但如果某個參數出現在範本裡的兩個地方，傳入此參數的表達式就必須複製成多個，當這個表達式做了修改變數或是印出文字等操作，這種取代就會使行為改變。然而在像是Haskell等純函數式程式語言中，這不只是像是而已，這種取代是完全沒有問題的，唯一的不同只有效能上的差異。這種特性稱為引用透明性(referential transparency)：我們可以自由地把函式的呼叫直接改寫成它的定義並取代相應的參數，就像數學函數一樣。具有引用透明性的函式必須沒有副作用，否則結果就可能會改變。這代表這個函式回傳的結果只依賴於參數，任何情境的改變都不會影響計算結果。這使得重構程式碼變得簡單，我們不再需要考慮執行順序、呼叫次數或是呼叫時機，它只會受到傳入參數的束縛，程式邏輯因而變得更容易理解。因此函式應該寫得盡量地引用透明，這也是函式應該盡量避免使用副作用的原因。

如果說函式的參數代表表達式範本上的「洞」，參數類型就是代表洞的形狀。構成加法類型與乘法類型的成員類型角色是同等的，而構成函式類型的參數類型與回傳類型角色則是不一樣的。加法/乘法類型的成員類型和函式的回傳類型代表它能「提供」這種數值，而函式的參數類型則代表它「需要」這種數值。物件導向的繼承機制使我們可以把物件實體當作更抽象的父類別物件來操作，例如List類別的物件可以當作Collection類別的物件。而乘法/加法類型的成員也可以這麼做，例如Tuple<List, Integer>類型的物件可以當作Tuple<Collection, Number>類型的物件，因為它被當作是前者的父類別。而函式的參數類型則相反，例如fn(Collection)->Integer的函式可以當作fn(List)->Number的函式使用，而非fn(Object)->Number。如果類型參數的子類關係與複合類型的子類關係同向則稱為協變(covariant)，反向則稱為逆變(contravariant)，這和線性代數裡相同名詞的概念有類似的意義。協變的位置代表它會提供這類型的資料(producer)，而逆變的位置則是它會需要這個類型的資料(consumer)。有趣的是它有負負得正的特性，例如函式類型fn(fn(res)->bool)->bool，其中fn(res)->bool位於逆變的位置，而res相對於最外層的函式則是協變的：這個函式會產生出res並喂給傳入的callback函式，因此它是res的producer。

在rust，類型描述的是在記憶體中的實際結構，而函式實際上就是一段指令，因此它也可以用類型描述。跟其他語言不一樣的是，即使兩個函式的參數類型和回傳類型都一樣，它們的類型還是不一樣，因為指令長度和結構可能不一樣。closure和async等特殊結構更是如此，編譯器會在內部實作一個結構保存捕捉的變數和管理狀態，因此它們實際上就是一種資料結構。它們都擁有匿名的類型，每個函式、閉包都有獨立的類型，並沒辦法直接混用(see Rust Functions Are Weird (But Be Glad))。基於這個理由，rust主要是以trait描述函式的signature，而非類型。而對於函數式編程來說則沒有這麼具體，函式的類型是由參數類型和回傳類型組成，不管它內部是什麼結構，只要這兩項相同就是同一種類型。函數式程式語言的類型描述的是更抽象的結構和行為，並不考慮物理上系統怎麼做處理。前幾篇文章以「函數式編程的類型描述的是實際的資料結構」用來對比「物件導向的變數類型與實體類型可以不一樣」，事實上這是不準確的，尤其是討論到函式類型時（對於惰性求值的Haskell更為明顯）。正確來說，函數式編程的類型描述的是「抽象的結構」。這跟物件導向的差別在於它只會包含它描述的特性，不會像物件導向的子類轉換使得變數實際上帶有其他特性。例如在TypeScript裡{x:1, y:2, z:3}可以被當作{x:number, y:number}類型下的物件，但它多了可存取z成員的特性，這對於函數式編程的類型系統是非法的。

乘法類型和加法類型的「資料的抽象結構」可以用一個函式描述。乘法類型具有「同時取得成員」的特性，例如類型type IntAndStr = Tuple<int, string>可以由fn(fn(int) -> fn(string) -> A) -> A描述，其中我們透過callback函式取得它的成員。加法類型具有「取得其中一個成員」的特性，例如類型type IntOrStr = Result<int, string>可由fn(fn(int) -> A) -> fn(fn(string) -> A) -> A描述，其中我們透過兩個callback函式分別取得它的成員。如果嚴格遵守函數式編程的教條，只有唯一一種方法可以實作出這兩類函式，實際上就只是pattern matching而已，而它們顯現出乘法類型和加法類型的基礎且唯一的特性，因此可以說它們是代數資料類型的另一種實現方法，這被稱作Scott encoding。事實上所有代數資料類型，包括還沒介紹到的遞迴類型，都能用函式描述。相對於圖靈機使用資料描述函式，這是稱為lambda calculus的另一套計算理論。smalltalk同樣利用方法定義物件本身，例如boolean只是擁有if-else函式的閉包，然而物件會有內部狀態，這使得這種閉包與純函數式的閉包變成完全不一樣的東西。

函式類型也是代數資料類型的一種，他擁有類似指數的代數結構：fn(A)->B類似於B^A，例如fn(A)->fn(B)->C跟fn(A,B)->C是等價的，因為(C^B)^A = C^(A*B)；(fn(A)->C, fn(B)->C)和fn(Result<A, B>)->C是等價的，因為(C^A)*(C^B) = C^(A+B)。它還有一個特殊的結構：fn<B>(fn(A)->B)->B相當於A，其中它擁有泛型變數B。透過這些結構可以很容易推導出Scott encoding。它在實體數量上也符合這個代數結構，例如擁有fn(bool)->i8類型的函式有256^2種；可以想像它其實是(i8,i8)，傳入false時回傳第一個，傳入true時回傳第二個。這些代數結構只有在沒有副作用時才符合，基於這點，純函數式程式語言對於函式的理解和其他語言有根本上的不同。沒有副作用的函式根本上與資料結構無異，例如Map<A,B>就只是能根據A取得B的資料結構，它可以直接改寫成fn(A)->Option<B>。如果再包含惰性求值的特性，甚至反過來也是可以的：函式fn(A)->B可以改寫成惰性求值的Map<A,B>，這種方法可以達到暫存計算結果的效果。