287
Java中的Functor與monad
這篇文章最初是我們的Reactive Programming with RxJava一書中的附錄，然而提到monad即使它與響應式編程有關，但也隻是一點點，所以我決定把它單獨拿出來出一篇博客。我意識到對monad一邊解釋一邊糾正，對我而言這就像是在編程博客上使用“Hello World”一樣(是對是錯拉出來熘熘)。而且這篇文章從Java數據結構與庫的角度對functor與monad給出了獨特見解，因此我認為這值得拿出來分享。
RxJava是被設計和建立在基礎概念如functors,monoids和monads上的，盡管最初Rx的概念是為C#而提出來的，我們現在學習RxJava同樣可以適用在其他支持函數式編程的命令式編程語言上。在意識到RxJava的API是多麼緊湊之後你不必驚訝，有很多相當有用的核心類都是不可變的，每一步計算都基本使用純粹的函數連接起來。
最近隨著函數式(或函數式風格)編程的興起，一些流行語言如Scala和Clojure的通用表達形式使得monads成為了廣為討論的話題，這裏有些流行的說法：
A monad is a monoid in the category of endofunctors, what’s the problem?
James Iry
The curse of the monad is that once you get the epiphany, once you understand – “oh that’s what it is” – you lose the ability to explain it to anybody.
Douglas Crockford
絕大部分程序員，尤其是沒有函數式編程背景的都傾向於monads是一些晦澀難懂的計算機概念，以至於它不可能對他們的編程有任何幫助，他們之所以有這種消極的思想都要怪罪於那些個太過抽象和狹隘的文章和博客。事實證明monads就在我們身邊，甚至在標準的Java類庫尤其是JDK8(以及之後的版本)中都有體現。這個概念高就高在一旦你領悟到了它，瞬間所有不相幹的用於實現完全不同目的的抽象和類庫都變得熟悉起來。
monads會形成很多相似的獨立概念，所以我們在學習monad的另外一種實現時隻需花費很少時間。例如你不必去學習Java 8中CompletableFuture的工作機理，一旦你知道它是一個monad，你就能精確地知道它是如何工作的並且能從它的語法中讀出些什麼。如果這時你接觸了RxJava，也許它聽起來有些不同但因為Observable是monad，所以也就沒什麼需要額外說明的了。還有很多其他有關monad的例子，你可能早就接觸過了但沒有意識到。因此如果你曾經沒有用好RxJava，這部分將會是一次有用的補習。
Functors
在我們解釋monad是什麼之前，讓我們先了解一下functor的概念。functor(函子)是一種數據結構，能夠封裝一些值。從語法角度來講函子就是容器，例如以下的API:
import java.util.function.Function;
interface Functor<T> {
<R> Functor<R> map(Function<T, R> f);
}
但僅僅從語法角度不足以了解函子是什麼，上麵的函子提供的唯一操作是map(),它的輸入是一個函數f。這個函數會接收盒子(也就是封裝了值的函子)中的任何東西，並對其進行轉換，最後將結果包裝為第二個函子。Functor總是一個不可變的容器，因此map絕不會改變它要執行的原始對象(這裏指的是map不會改變Functor,隻會將裏麵的值T拿出來作為函數f的輸入)，相反map會將計算得到的結果R包裝在一個新的函子中並返回。另外當應用恒等函數時函子不應該執行任何動作，如map(x -> x)。這種模式下應該返回相同的函子或者同一個實例。
Functor經常被比作成裝有實例T的箱子，而唯一使用這個值的方法就是轉換它。然而並沒有慣用的方法去展開這個函子，因此值總是待在函子的上下文背景中。為什麼函子有用？它們會產生很多通用的慣用操作如collections, promises, optionals等，使用一個標準的API就可以貫穿它們所有，讓我來介紹一些函子以便你對下麵的API有更深的了解：
interface Functor<T,F extends Functor<?,?>> {
<R> F map(Function<T,R> f);
}
class Identity<T> implements Functor<T,Identity<?>> {
private final T value;
Identity(T value) { this.value = value; }
public <R> Identity<R> map(Function<T,R> f) {
final R result = f.apply(value);
return new Identity<>(result);
}
}
需要一個F類型的參數使得Identity能夠編譯，上麵的代碼是你見到的最簡單的函子，僅僅持有一個值。而你能夠對這個值做的就隻有在map方法內部進行轉換，而且沒有其他方法可以獲得這個值。這已經超越了純函子的範疇了。唯一使用函子的方法就是對其應用一係列類型安全的轉換：
[coed lang=”java”]
Identity idString = new Identity(“abc”);
Identity idInt = idString.map(String::length);
[/code]
或者你可以一條線地將幾個函數組合起來：
Identity<byte[]> idBytes = new Identity<>(customer)
.map(Customer::getAddress)
.map(Address::street)
.map((String s) -> s.substring(0, 3))
.map(String::toLowerCase)
.map(String::getBytes);
從這個角度看對一個函子進行多次映射與調用一係列的函數大不相同：
byte[] bytes = customer
.getAddress()
.street()
.substring(0, 3)
.toLowerCase()
.getBytes();
你可能會對這些冗餘的命令行感到反感，它不僅沒有提供額外的附加值而且還不能將裏麵的內容提取出來。事實證明，這樣寫的好處有利於你利用這種函子抽象來建立很多其他的概念。例如java 8中的java.util.Optional就是一個擁有map()方法的函子。現在讓我們從頭實現它：
class FOptional<T> implements Functor<T,FOptional<?>> {
private final T valueOrNull;
private FOptional(T valueOrNull) {
this.valueOrNull = valueOrNull;
}
public <R> FOptional<R> map(Function<T,R> f) {
if (valueOrNull == null)
return empty();
else
return of(f.apply(valueOrNull));
}
public static <T> FOptional<T> of(T a) {
return new FOptional<T>(a);
}
public static <T> FOptional<T> empty() {
return new FOptional<T>(null);
}
}
現在事情開始變得有趣了，一個FOptional函子可以包含一個值，而這個值可以為空。這種編碼null的方法是類型安全的。有兩種方法可以構建FOptional,一種是在構建的時候傳入一個值另一種則是傳入一個null。這兩種情況下，和Identity一樣，FOptional是不可變的，我們隻能在容器內部對值進行操作。然而FOptional不同的是變換函數f不會對null進行操作，這就意味著函子不必非要封裝實際類型為T的值，而且它也可以包裹任意數量的值，如List函子：
import com.google.common.collect.ImmutableList;
class FList<T> implements Functor<T, FList<?>> {
private final ImmutableList<T> list;
FList(Iterable<T> value) {
this.list = ImmutableList.copyOf(value);
}
@Override
public <R> FList<?> map(Function<T, R> f) {
ArrayList<R> result = new ArrayList<R>(list.size());
for (T t : list) {
result.add(f.apply(t));
}
return new FList<>(result);
}
}
這個API和之前相似的地方在於你會得到一個將T -> R的函子，但具體的表現形式不同。現在我們可以將變換應用在FList中的每個元素上，顯式地轉換整個list。所以如果你有個customers的列表，而你想要得到他們street的列表，你可以這樣做：
import static java.util.Arrays.asList;
FList<Customer> customers = new FList<>(asList(cust1, cust2));
FList<String> streets = customers
.map(Customer::getAddress)
.map(Address::street);
上麵的代碼就不能簡單的用customers.getAddress().street()來代替了，因為我們不可能對customers集合調用getAddress()，我們必須對集合中的每一個元素調用getAddress()然後將每個結果再放回一個集合中。順便說一句，Groovy發現了這隻能模式以至於它普遍的使用以下的語法糖：customer*.getAddress()*.street()，這種操作符就叫做展開點，它事實上就是偽裝的map。你可能會好奇為什麼我在map裏麵手動遍曆list而不是用Java 8中的Stream：list.stream().map(f).collect(toList())。看到這裏你會想到什麼,其實java.util.stream.Stream就是一個函子同時也是一個monad。
現在你能看到函子的第一個好處-它們對內部表征不予考慮並且具有連貫性，方便對不同的數據結構應用API。作為最後一個例子讓我介紹一下promise函子，它和Future. Promise很相似，“承諾”某一個值在未來將可用。它在這個時刻還不存在可能是因為後台的計算還在進行或者是為我們在等待外部事件，但在未來的某個時刻它終會出現。Promise的完成機製其實沒什麼，其過程如下：
Promise<Customer> customer = //...
Promise<byte[]> bytes = customer
.map(Customer::getAddress)
.map(Address::street)
.map((String s) -> s.substring(0, 3))
.map(String::toLowerCase)
.map(String::getBytes);
是不是看起來很熟悉？那就對了！Promise 函子的實現原理已經超過了本文的範圍這裏就不再贅述。可以肯定的說我們已經非常接近實現Java 8中的CompletableFuture和RxJava中的Observable了。回到函子上，Promise在此時還沒有包含Customer，它承諾在將來會擁有這類值。但我們仍然可以在這類函子上進行映射，就像我們使用FOptional和FList一樣，語法是一樣的，而且其實現的功能就如函子所表示的那樣。調用customer.map(Customer::getAddress)產生Promise意味著map方法是非阻塞的，customer.map()不會等待底層的customer promise去完成，相反它會返回另外一種不同類型的promise。當上遊的promise完成時，下遊的promise就會應用一個函數到map()中然後再將結果往下遊傳。此時函子已經允許我們以一種非阻塞的形式連接異步計算，不過你不必了解這個過程，你隻用知道怎麼使用Promise這個函子的語法規則就行。
還有很多其他有關函子的例子，例如以一種組合形式表示值或者error等，而且是時候介紹monads了。
From functors to monads
到這裏我假設你已經明白了函子是怎樣工作的和它為什麼是有用的抽象，但函子並不是像我們想象的那樣是個一般概念。如果你的轉換函數(作為參數被傳入map()中)返回一個函子實例而不是簡單的值那會怎麼樣？然而函子也隻是一個值而已，不會發生什麼太糟糕的事。無論返回什麼都會被放進一個函子中，所以所有的操作都和之前是一致的。想象一下你使用以下便捷的方法轉換Strings:
FOptional<Integer> tryParse(String s) {
try {
final int i = Integer.parseInt(s);
return FOptional.of(i);
} catch (NumberFormatException e) {
return FOptional.empty();
}
}
異常是有副作用的，它會破壞類型係統和功能純度，在純淨的函數式語言中是沒有異常的一席之地的，畢竟我們從沒有聽說在使用math類時會拋出異常，對嗎？errors和不合法的情況都會明確地使用值或者封裝器進行包裝。例如tryParse()就需要傳入一個String但不會簡單地返回一個int，也不會在運行的時候拋出異常。我們明確指出，經過類型係統的識別tryParse()可能會失敗，但不會拋出異常和錯誤，這種半失敗情況由選擇之後的結果表征。有趣的是Java有已檢查的異常，這種異常必須被聲明和處理，所以在某些場合在對待異常這件事上，Java要更加純淨，沒有隱藏的副作用。但不論好壞，已檢查的異常在Java中經常受阻，所以讓我們回到tryParse()。將tryParse()與包裝有String的FOptional組合起來似乎有用：
FOptional<String> str = FOptional.of("42");
FOptional<FOptional<Integer>> num = str.map(this::tryParse);
對上麵的代碼你不應該感到驚訝，因為如果tryParse()內部產生的是int，那麼它會返回FOptional，但map()返回的也是FOptional，導致int被包裝兩次產生了看起來古怪的FOptional<FOptional>。請把這種數據類型看清楚，要弄明白為什麼會封裝兩次，除了看起來很怪之外，在函子中包裝函子破壞了鏈式結構的構成和流暢性：
FOptional<Integer> num1 = //... FOptional<FOptional<Integer>> num2 = //... FOptional<Date> date1 = num1.map(t -> new Date(t)); //doesn't compile! FOptional<Date> date2 = num2.map(t -> new Date(t));
在這裏我試著對FOptional裏麵的值進行映射，將int轉換成Date類型。我們可以通過函數int -> Date很輕鬆地將Functor轉換成Functor,而且我們知道它是如何工作的。但是對於num2來說情況就複雜了，對於num2.map()來說它的輸入不再是int而是FOoption，顯然java.util.Date並沒有這樣的構造函數，所以兩次包裝破壞了函子。然而這種返回函子而不是值的函數相當普遍(就像tryParse())，我們不能忽略這種需求。有一種解決方法是引入一種無參函數join()，它能夠“展開”內嵌的函子：
FOptional<Integer> num3 = num2.join();
這種方式很有用而且很普遍，但是它有特定的名字flatMap()。flatMap()和map()非常相似，它也是將函數作為輸入並返回函子-或者更精確地說是返回monad：
interface Monad<T,M extends Monad<?,?>> extends Functor<T,M> {
M flatMap(Function<T,M> f);
}
我們可以簡單地總結為flatMap就是一語法糖，更方便組合。而且flatMap方法(經常叫做bind,或者在Haskell中叫做>>=)會造成很大的不同是因為它允許在純淨的函數式風格編程中集成複雜的轉換。如果FOptional是一個monad實例，那麼以下的代碼就會通過編譯：
FOptional<String> num = FOptional.of("42");
FOptional<Integer> answer = num.flatMap(this::tryParse);
monads不必實現map，它很容易在flatMap()的基礎上實現。事實上flatMap才是那個重要的運算函數，它會使整個變換過程煥然一新。顯然和函子一樣，語法的符合並不足以使某些類成為monad，flatMap()的調用者還必須遵從monad的規則，必須要與flatMap()有很直觀的關聯性和同一性。對於任何擁有值x和函數f的monad，同一性要求m(x).flatMap(f)要等同於f(x)。我們不會對monad的理論作進一步的深入，相反的我們會將注意力放在它的實踐上。當monad內部結構變得不再簡單時，它的性能就會變得很出眾，例如Promise monad會在未來的某個時刻持有一個值。你能依據類型係統從下麵的代碼中猜出Promise是怎樣工作的嗎？首先所有的方法都會在後台花少許時間返回一個Promise：
import java.time.DayOfWeek;
Promise<Customer> loadCustomer(int id) {
//...
}
Promise<Basket> readBasket(Customer customer) {
//...
}
Promise<BigDecimal> calculateDiscount(Basket basket, DayOfWeek dow) {
//...
}
現在我們可以將這些函數組合起來，就像是它們在阻塞地使用monad的運算函數一樣：
Promise<BigDecimal> discount =
loadCustomer(42)
.flatMap(this::readBasket)
.flatMap(b -> calculateDiscount(b, DayOfWeek.FRIDAY));
這就變得有趣了，flatmap()必須將結果保存為monad，因此所有的中間對象都為Promise。這並不僅僅是為了保證類型一致，因為前麵的程序突然就可以完全異步了！loadCustomer()返回Promise,所以它沒有阻塞，接著readBasket()就會獲取這個Promise擁有的值(將要擁有的)，並應用一個函數到這個值上然後返回另一個Promise等等像這樣一直持續下去。基本上我們建立了一個異步的計算管道，一個階段的完成會自動地觸發下一個階段。
Exploring flatMap()
使用兩個monad並且將它們封裝的值結合起來是很常見的，然而函子和monad都不允許直接訪問它們的內部，因為這會使函數式編程變得不純淨，相反我們必須小心地進行變換而不用轉義monad。想象一下你有兩個monad，而且你想將它們結合起來：
import java.time.LocalDate;
import java.time.Month;
Monad<Month> month = //...
Monad<Integer> dayOfMonth = //...
Monad<LocalDate> date = month.flatMap((Month m) ->
dayOfMonth
.map((int d) -> LocalDate.of(2016, m, d)));
請花一些時間研究一下上麵的偽代碼，我並沒有使用monad實現如Promise或者List來強調這個核心概念。我們有兩個獨立的monad，一種是包含Month類型的，另一種是包含Integer類型的。為了利用它們建立LocalDate,我們必須使用內嵌的變換來訪問這兩個monad的內部。要把類型弄明白，尤其是要搞清楚為什麼我會把flatmap()放在前麵而把map()放在後麵,思考一下如果有第三個Monad，那麼你會如何構建代碼。這種應用兩個參數(在我們的例子中是m和d)函數的模式非常普遍。在Haskell中有一個特別有用的函數叫liftM2,實現於map與flatmap之上，專門用來進行這樣的變換。用Java偽代碼寫出來是這樣的：
Monad<R> liftM2(Monad<T1> t1, Monad<T2> t2, BiFunction<T1, T2, R> fun) {
return t1.flatMap((T1 tv1) ->
t2.map((T2 tv2) -> fun.apply(tv1, tv2))
);
}
你不必對每一個monad都實現這個方法，用flatMap()就足夠了，而且它始終對所有monad都起作用。當你在思考著如何使用變化的monad時，liftM2就變得極其有用。例如liftM2(list1, list2, function)會應用函數function到每一對來自list1和list2的條目上(笛卡兒積)。另一方麵對於optional來說，僅僅當兩個optional是非空時才會應用函數。更好的是對於Promise monad來說，函數function會被異步地執行僅當這兩個Promise都完成了。這就意味這我們為兩個異步階段創造了一個簡單的同步機製(就像fork-join算法中的join()一樣)。
我們可以很容易地在flatMap()基礎上建立的另一個有用的運算函數是filter(Predicate)，這個函數會取出monad裏麵的任何東西，如果它們不滿足predicate的條件那麼就會被丟棄。在某種程度上filter和map很相似，但與1對1的映射不同的是，filter有1對0和1對1兩種情況。filter對每一個monad都有著相同的語法，但又隨著monad的不同其實現的功能又不一樣。下麵的代碼就會過濾掉list中不符合條件的元素：
FList<Customer> vips =
customers.filter(c -> c.totalOrders > 1_000);
filter對optional同樣適用，在這樣的情況下如果optional裏麵的內容沒有滿足某些條件，那麼我們可以將非空的optional轉化為空的optional。
From list of monads to monad of list
另一個有用的運算函數是sequence(),它起源於flatmap()。你可以從下麵的函數簽名中猜出這個函數到底是做什麼的：
Monad<Iterable<T>> sequence(Iterable<Monad<T>> monads)
我們經常會有一些相同類型的monad，並且我們想要將這些monad轉化為一個包含list的monad。對你來說這聽起來可能有些抽象，但確實非常有用。想象一下你想要並發地通過ID從數據庫中加載一些customer，所以你會對不同的ID多次調用loadCustomer(id)方法，每一次調用都會返回Promise，所以你就會得到一個Promises的列表，但你想要的是customers的列表，因此可以使用sequence()(在RxJava中依使用的情況不同，sequence()叫做concat()或者merge())運算函數：
FList<Promise<Customer>> custPromises = FList
.of(1, 2, 3)
.map(database::loadCustomer);
Promise<FList<Customer>> customers = custPromises.sequence();
customers.map((FList<Customer> c) -> ...);
在得到了包含客戶ID的FList之後，我們對它進行映射(你能看出FList作為一個函子是怎樣起到幫助作用的嗎？)，對每一個客戶的ID調用database.loadCustomer(id)方法，這樣就會產生一個非常不方便的關於Promises的列表。這時sequence()拯救了這一切，而且這個函數並不僅僅是語法糖，因為上麵的代碼完全是非阻塞的。在不同的計算環境下，sequence()對於不同的monad仍然是有意義的。例如，它能夠將FList<FOptional>轉化為FOptional<FList>。而且你也能自己實現在flatmap()的基礎上實現sequence()(就像map()一樣)。
這裏提到flatMap()和monad的有用性僅僅隻是冰山一角。盡管monad的分類定義的的非常模煳，但它在麵向對象的編程語言如Java中卻是非常有用的抽象。能夠將一些函數組合起來並返回monad是非常有益的，這樣會使得一些一些毫不相幹的類都遵從monad式的行為。
而且一旦你將數據封裝進monad中，那麼你想明確地將它拿出來將會非常困難。這種取值操作並不是monad行為的一部分，它會產生非慣用的代碼，例如對promise調用Promise.get()在理論上會返回T，但此時這個方法是阻塞的。然而對於Promise，所有基於flatmap()的運算函數都是非阻塞的。另一個例子是FOptional.get()，這個方法可能會失敗，因為FOptional可能為空。甚至是FList.get(idx)這種訪問列表中特定元素的方法看起來都怪怪的，因為你都能用map()函數取代for循環了。
我希望你能明白為什麼最近一段時間monad如此受歡迎了，甚至在Java這種麵向對象語言中monad也是非常有用的抽象。
最後更新：2017-05-19 14:32:06