Learn Functional Programming In Java (11) - FoldRight, FoldLeft

前面几篇文章里讲了 Tail Recursion （不了解的请点击这里：
知乎专栏）， Category Theory 里面的 Monoid 的概念（不了解的请点击这里：
知乎专栏），以及如何用 FP 的方式写成一个 list (不了解的请点击这里：
知乎专栏)。

这一章，我们就把三个知识点穿插起来，看看他们之间的关系是什么。

我们先来用之前创建好的 list 写两个小程序。( sum 和 product， 也就是所有相加的和，和所有相乘的积)

public static int sum(List<Integer> ls){
        return  ls.isEmpty() ?
                    0 :
                    ls.head() + sum(ls.tail());
}

public static int product(List<Integer> ls){
        return  ls.isEmpty() ?
                    1 :
                    ls.head() * product(ls.tail());
}

测试代码：

//注意！ 这里的 list 是我们之前定义的 fp list， 不是 java 自带的 list List<Integer> ls = list(1, 2, 3, 4, 5);

System.out.println("The result of sum is :"  + sum(ls));

System.out.println("The result of product is :"  + product(ls));

测试结果：

The result of sum is :15
The result of product is :120

Process finished with exit code 0

看出 pattern 来了么？

f (ls) = ls.head op f( ls.tail )

那么展开后 就是Integer op Integer op Integer op Integer op Integer

1 + (2 + 3) 和 (1 + 2) +3 得到的结果相同

1 ＊ （2 ＊ 3）和 (1 ＊ 2) ＊ 3 得到的结果相同

int sum 0 为 int （identity）

int product 1 为 int (identity)

这正是我们之前讲到的 monoid. （associative and identity law ）

把 sum 和 product 相同的地方抽象出来，我们就可以出 foldRight

public static <T, U> U foldRight(List<T> ls, U acc, BiFunction<T, U, U> f){
        return ls.isEmpty()?
                    acc :
                    f.apply(ls.head(), foldRight(ls.tail(), acc, f));

    }

那么我们再把之前的测试代码稍加修改：

int sumResult     = foldRight(ls, 0, (x, y) -> x + y );
int productResult = foldRight(ls, 1, (x, y) -> x * y );

System.out.println("The result of sum is :"  + sumResult);
System.out.println("The result of product is :"  + productResult);

就会得到相同的结果：

The result of sum is :15
The result of product is :120

Process finished with exit code 0

再来一个比较有意思的小程序。

我们看看如何用 foldRight 来实现 list concatenation.

首先，我们来定义一个 factory method

public static <T> List<T> cons(T t, List<T>ls) {
        return new Cons<>(t, ls);
}

测试代码：

List<Integer> ls1 = list(1, 2, 3, 4, 5);
List<Integer> ls2 = list(6, 7, 8, 9, 10);

List<Integer> ls = foldRight(ls1, ls2, (head, tail) -> cons(head, tail));

System.out.println("The result of list concat is :"  + ls);

测试结果：

The result of list concat is :1, 2, 3, 4, 5, 6, 7, 8, 9, 10, Nil

Process finished with exit code 0

爽爆了的感觉有没有？懒得画图了，上网找了一张差不多的图来讲解一下

list concatenation 如何代码展开，其实效果是这样的：

ls1 = cons( head, cons ( head, cons (head, acc ) ) )

这里的 acc 被设为 ls2, 也是一个 cons( head, cons ( head, cons (head, Nil ) ) )

当遇到终止条件，也就是 ls1.isEmpty() 的时候， ls2 会被放进 acc 里作为替换, 于是就有了结果：

cons( head, cons ( head, cons (head, cons(head, cons (head, cons (head, Nil ) ) ) ) ) ) ;

如果用 imperative programming 来进行 list concatenation， performance 会是 n, 但我们上面所有到的 FP 方法， performance 是 n / 2。 因为只要把整个 ls2 丢进去就好，并不用太在意 ls2 里面有写什么。

FoldRight 是一个很理论的东西，放在项目开发中，可能会行不通，因为 foldRight 是一个 recursion call， 如果数据太大，层数太多，稍不小心就会 stackoverflow.

解决方法是有的， 让我们这就写一个 tailRecursion 的 FoldLeft 方法:

public static <T, U> U foldLeft  (List<T> ls, U acc, BiFunction<U, T, U> f) {
        return (U)foldLeft_(ls, acc, f).eval();
}

private static <U,T> TailCall foldLeft_ ( List<T> ls, U acc, BiFunction<U, T, U> f) {
        return ls.isEmpty()?
                TailCall.ret (acc):
                TailCall.sus (() -> foldLeft_( ls.tail(), f.apply(acc, ls.head()), f));
}

测试代码：

List<Integer> ls = list(1, 2, 3, 4, 5);
int sumResult = foldLeft(ls, 0, (x, y)-> x + y );
int productResult = foldLeft(ls, 1, (x, y) -> x * y );


System.out.println("The result of sum is :"  + sumResult);
System.out.println("The result of product is :"  + productResult);


// 一个有趣的 reverse list method List<Integer> reverse = foldLeft(ls, NIL, (head, tail) -> cons(tail, head));
System.out.print("The reverse of the list is: " + reverse);

测试结果：

The result of sum is :15
The result of product is :120
The reverse of the list is: 5, 4, 3, 2, 1, Nil
Process finished with exit code 0

先到这里，以后我们会用一些时间做一些小算法来让大家了解一下如何抽象的来思维问题。