Java中的Functor与monad

原文链接 作者:Tomasz Nurkiewicz  译者:simonwang

这篇文章最初是我们的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也是非常有用的抽象。

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: Java中的Functor与monad


FavoriteLoading添加本文到我的收藏
  • Trackback 关闭
  • 评论 (1)
    • a180285
    • 2016/09/29 4:46下午

    很久以前学过一点Haskell,但一直没有用过。
    现在Java 8 出来了,但工作上也没有用到。所以对这些知识还只是一知半解。

    不知现在有哪些公司或者项目已经在使用这方面的思想了。如果有的话,可否推荐一些。

您必须 登陆 后才能发表评论

return top