Java8笔记(7)

函数式编程

假设有这样一个系统，它不修改任何数据。维护这样的一个系统将是一个无以伦比的美梦，因为你不再会收到任何由于某些对象在某些地方修改了某个数据结构而导致的意外报告。如果一个方法既不修改它内嵌类的状态，也不修改其他对象的状态，使用 return 返回所有的计算结果，那么我们称其为纯粹的或者无副作用的

更确切地讲，到底哪些因素会造成副作用呢？简而言之，副作用就是函数的效果已经超出了
函数自身的范畴。下面是一些例子：

• 除了构造器内的初始化操作，对类中数据结构的任何修改，包括字段的赋值操作（一个
  典型的例子是 setter 方法）

• 抛出一个异常

• 进行输入/输出操作，比如向一个文件写数据

从另一个角度来看“无副作用”的话，我们就应该考虑不可变对象。不可变对象是这样一种对象，它们一旦完成初始化就不会被任何方法修改状态。这意味着一旦一个不可变对象初始化完毕，它永远不会进入到一个无法预期的状态。你可以放心地共享它，无需保留任何副本，并且由于它们不会被修改，还是线程安全的

声明式编程

如果你希望通过计算找出列表中最昂贵的事务，通常需要执行一系列的命令：从列表中取出一个事务，将其与临时最昂贵事务进行比较；如果该事务开销更大，就将临时最昂贵的事务设置为该事务；接着从列表中取出下一个事务，并重复上述操作

这种“如何做”风格的编程非常适合经典的面向对象编程，有些时候我们也称之为“命令式”编程，因为它的特点是它的指令和计算机底层的词汇非常相近，比如赋值、条件分支以及循环

Transaction mostExpensive = transactions.get(0);
    if(mostExpensive == null)
        throw new IllegalArgumentException("Empty list of transactions")
    for(Transaction t: transactions.subList(1, transactions.size())){
        if(t.getValue() > mostExpensive.getValue()){
            mostExpensive = t;
        }
}

另一种方式则更加关注要做什么

Optional<Transaction> mostExpensive =
    transactions.stream()
            .max(comparing(Transaction::getValue));

这个查询把最终如何实现的细节留给了函数库。我们把这种思想称之为内部迭代

它的巨大优势在于你的查询语句现在读起来就像是问题陈述，由于采用了这种方式，我们马上就能理解它的功能，比理解一系列的命令要简洁得多

函数式编程

对于“什么是函数式编程”这一问题最简化的回答是“它是一种使用函数进行编程的方式”

在函数式编程的上下文中，一个“函数”对应于一个数学函数：它接受零个或多个参数，生成一个或多个结果，并且不会有任何副作用。你可以把它看成一个黑盒，它接收输入并产生一些输出

我们的准则是，被称为“函数式”的函数或方法都只能修改本地变量。除此之外，它引用的
对象都应该是不可修改的对象。通过这种规定，我们期望所有的字段都为 final 类型，所有的引用类型字段都指向不可变对象

如果不使用异常，你该如何对除法这样的函数进行建模呢？答案是请使用Optional<T> 类型：你应该避免让 sqrt 使用 double sqrt(double) 这样的函数签名，因为这种方式可能抛出异常；与之相反我们推荐你使用 Optional<Double> sqrt(double) ——这种方式下，函数要么返回一个值表示调用成功，要么返回一个对象，表明其无法进行指定的操作

引用透明性

如果一个函数只要传递同样的参数值，总是返回同样的结果，那这个函数就是引用透明的

String.replace 方法就是引用透明的，因为像 "raoul".replace('r','R') 这样的调用总是返回同样的结果（ replace 方法返回一个新的字符串，用小写的 r 替换掉所有大写的 R ），而不是更新它的 this 对象，所以它可以被看成函数式的

换句话说，函数无论在何处、何时调用，如果使用同样的输入总能持续地得到相同的结果，
就具备了函数式的特征

函数式编程实战

给定一个列表 List<value> ，比如{1, 4,9}，构造一个 List<List<Integer>> ，它的成员都是类表{1, 4, 9}的子集——我们暂时不考虑元素的顺序。{1, 4, 9}的子集是{1, 4, 9}、{1, 4}、{1, 9}、{4, 9}、{1}、{4}、{9}以及{}

public class M1 {

    public static List<List<Integer>> subsets(List<Integer> list){

        if (list.isEmpty()) {
            List<List<Integer>> ans = new ArrayList<>();
            ans.add(Collections.emptyList());
            return ans;
        }

        Integer first = list.get(0);

        List<Integer> rest = list.subList(1,list.size());

        List<List<Integer>> subans = subsets(rest);

        List<List<Integer>> subans2 = insertAll(first,subans);

        return concat(subans,subans2);
    }


    public static List<List<Integer>> insertAll(Integer first,
                                                List<List<Integer>> lists) {
        List<List<Integer>> result = new ArrayList<>();
        for (List<Integer> list : lists) {

//            复制列表，从而使你有机会对其
//进行添加操作。即使底层是可变
//的，你也不应该复制底层的结构
//（不过 Integer 底层是不可变的）
            List<Integer> copyList = new ArrayList<>();
            copyList.add(first);
            copyList.addAll(list);
            result.add(copyList);
        }
        return result;
    }

    public static List<List<Integer>> concat(List<List<Integer>> a,
                                             List<List<Integer>> b) {

//        它在内部会对对象进行修改（向列
//表 r 添加元素），但是它返回的结果基于参数却没有修改任何一个传入的参数
        List<List<Integer>> r = new ArrayList<>(a);
        r.addAll(b);
        return r;
    }


    public static void main(String[] args) {

        List<Integer> list = Arrays.asList(

                1,4,9
        );

        System.out.println(subsets(list));

    }


}

递归和迭代

纯粹的函数式编程语言通常不包含像 while 或者 for 这样的迭代构造器。为什么呢？因为这种类型的构造器经常隐藏着陷阱，诱使你修改对象。比如， while 循环中，循环的条件需要更新；否则循环就一次都不会执行，要么就进入无限循环的状态

在Java中使用的 for-each 循环

Iterator<Apple> it = apples.iterator();
    while (it.hasNext()) {
            Apple apple = it.next();
// ...
}

这并不是问题，因为改变发生时，这些变化（包括使用 next 方法对迭代器状态的改变以及在 while 循环内部对 apple 变量的赋值）对于方法的调用方是不可见的

但是，如果使用for-each 循环，比如像下面这个搜索算法就会带来问题，因为循环体会对调用方共享的数据结构进行修改

public void searchForGold(List<String> l, Stats stats){
    for(String s: l){
        if("gold".equals(s)){
            stats.incrementFor("gold");
                }
        }
}

一个经典的教学问题是用迭代的方式或者递归的方式（假设输入值大于1）编写一个计算阶乘的函数（参数为正数）

迭代式的阶乘计算

static int factorialIterative(int n) {
    int r = 1;
    for (int i = 1; i <= n; i++) {
        r *= i;
    }
    return r;
}

递归式的阶乘计算

static long factorialRecursive(long n) {
        return n == 1 ? 1 : n * factorialRecursive(n-1);
}

第一段代码展示了标准的基于循环的结构：变量 r 和 i 在每轮循环中都会被更新。第二段代码以更加类数学的形式给出一个递归方法（方法调用自身）的实现

基于 Stream 的阶乘

static long factorialStreams(long n){
        return LongStream.rangeClosed(1, n)
                .reduce(1, (long a, long b) -> a * b);
}

函数式语言提供了一种方法解决这一问题：尾-调优化（tail-call optimization）。基本的思想是你可以编写阶乘的一个迭代定义，不过迭代调用发生在函数的最后（所以我们说调用发生在尾部）。这种新型的迭代调用经过优化后执行的速度快很多

基于“尾递”的阶乘

static long factorialTailRecursive(long n) {
        return factorialHelper(1, n);
}


static long factorialHelper(long acc, long n) {
            return n == 1 ? acc : factorialHelper(acc * n, n-1);
}

方法 factorialHelper 属于“尾递”类型的函数，原因是递归调用发生在方法的最后

这种形式的递归是非常有意义的，现在我们不需要在不同的栈帧上保存每次递归计算的中间
值，编译器能够自行决定复用某个栈帧进行计算。实际上，在 factorialHelper 的定义中，立即数（阶乘计算的中间结果）直接作为参数传递给了该方法。再也不用为每个递归调用分配单独的栈帧用于跟踪每次递归调用的中间值——通过方法的参数能够直接访问这些值

高阶函数

函数式编程的世界里，如果函数，比如 Comparator.comparing ，能满足下面任一要求就
可以被称为高阶函数（higher-order function）：

• 接受至少一个函数作为参数

• 返回的结果是一个函数

这些都和Java 8直接相关。因为Java 8中，函数不仅可以作为参数传递，还可以作为结果返回，能赋值给本地变量，也可以插入到某个数据结构

科里化

应用程序通常都会有国际化的需求，将一套单位转换到另一套单位是经常碰到的问题

单位转换通常都会涉及转换因子以及基线调整因子的问题。比如，将摄氏度转换到华氏度的公式是 CtoF(x) = x9/5 + 32*

所有的单位转换几乎都遵守下面这种模式

• 乘以转换因子

• 如果需要，进行基线调整

使用下面这段通用代码表达这一模式

static double converter(double x, double f, double b) {
            return x * f + b;
}

这里 x 是你希望转换的数量， f 是转换因子， b 是基线值。但是这个方法有些过于宽泛了。通常，你还需要在同一类单位之间进行转换，比如公里和英里。当然，你也可以在每次调用converter 方法时都使用3个参数，但是每次都提供转换因子和基准比较繁琐，并且你还极有可能输入错误

你可以定义一个“工厂”方法，它生产带一个参数的转换方法，我们希望借此来说明科里化。下面是这段代码

static DoubleUnaryOperator curriedConverter(double f, double b){
            return (double x) -> x * f + b;
}

现在，你要做的只是向它传递转换因子和基准值（ f 和 b ），它会不辞辛劳地按照你的要求返回一个方法（使用参数 x ）

科里化的理论定义

科里化是一种将具备2个参数（比如， x 和 y ）的函数 f 转化为使用一个参数的函数 g ，并且这个函数的返回值也是一个函数，它会作为新函数的一个参数。后者的返回值和初始函数的返回值相同，即 f(x,y) = (g(x))(y) 。当然，我们可以由此推出：你可以将一个使用了6个参数的函数科里化成一个接受第2、4、6号参数，并返回一个接受5号参数的函数，这个函数又返回一个接受剩下的第1号和第3号参数的函数。一个函数使用所有参数仅有部分被传递时，通常我们说这个函数是 部分应用的（partiallyapplied）

持久化数据结构

函数式方法不允许修改任何全局数据结构或者任何作为参数传入的参数。为什么呢？因为一旦对这些数据进行修改，两次相同的调用就很可能产生不同的结构——这违背了引用透明性原则，我们也就无法将方法简单地看作由参数到结果的映射

破坏式更新和函数式更新的比较

public class TrainJourney {


//    可变类 TrainJourney （利用一
//个简单的单向链接列表实现）表示从A地到B地的火车旅行
    public int price;
    public TrainJourney onward;
    public TrainJourney(int p, TrainJourney t) {
        price = p;
        onward = t;
    }


}

假设你有几个相互分隔的 TrainJourney 对象分别代表从X到Y和从Y到Z的旅行。你希望创
建一段新的旅行，它能将两个 TrainJourney 对象串接起来（即从X到Y再到Z）。

一种方式是采用简单的传统命令式的方法将这些火车旅行对象链接起来

//    这个方法是这样工作的，它找到 TrainJourney 对象 a 的下一站，将其由表示 a 列表结束的
//null 替换为列表 b （如果 a 不包含任何元素，你需要进行特殊处理）。
    static TrainJourney link(TrainJourney a, TrainJourney b){
        if (a==null) return b;
        TrainJourney t = a;
        while(t.onward != null){
            t = t.onward;
        }
        t.onward = b;
        return a;
    }

这就出现了一个问题：假设变量 firstJourney 包含了从X地到Y地的线路，另一个变量secondJourney 包含了从Y地到Z地的线路。如果你调用 link(firstJourney,secondJourney)方法，这段代码会破坏性地更新 firstJourney ，结果 secondJourney 也会加被入到firstJourney ，最终请求从X地到Z地的用户会如其所愿地看到整合之后的旅程，不过从X地到Y地的旅程也被破坏性地更新了。这之后，变量 firstJourney 就不再代表从X到Y的旅程，而是一个新的从X到Z的旅程了！这一改动会导致依赖原先的 firstJourney 代码失效！假设firstJourney 表示的是清晨从伦敦到布鲁塞尔的火车，这趟车上后一段的乘客本来打算要去布鲁塞尔，可是发生这样的改动之后他们莫名地多走了一站，最终可能跑到了科隆

函数式编程解决这一问题的方法是禁止使用带有副作用的方法。如果你需要使用表示计算结果的数据结果，那么请创建它的一个副本而不要直接修改现存的数据结构。这一最佳实践也适用于标准的面向对象程序设计

采用函数式编程方案的代码如下

   static TrainJourney append(TrainJourney a, TrainJourney b){
            return a==null ? b : new TrainJourney(a.price, append(a.onward, b));
    }

很明显，这段代码是函数式的（它没有做任何修改，即使是本地的修改），它没有改动任何现存的数据结构

Stream 的延迟计算

自定义的 Stream

可以用下面这种方式计算得出由质数构成的Stream

    public static Stream<Integer> primes(int n) {
        return Stream.iterate(2, i -> i + 1)
                .filter(MyMathUtils::isPrime)
                .limit(n);
    }


public class MyMathUtils {

    public static boolean isPrime(int candidate) {
        int candidateRoot = (int) Math.sqrt((double) candidate);
        return IntStream.rangeClosed(2, candidateRoot)
                .noneMatch(i -> candidate % i == 0);
    }


}

你每次都需要遍历每个数字，查看它能否被候选数字整除（实际上，你只需要测试那些已经被判定为质数的数字

理想情况下，Stream应该实时地筛选掉那些能被质数整除的数字,不过我们一起看看怎样才能达到这样的效果

• 需要一个由数字构成的Stream，你会在其中选择质数

• 从该Stream中取出第一个数字（即Stream的首元素），它是一个质数（初始时，这个
  值是2）

• 从Stream的尾部开始，筛选掉所有能被该数字整除的元素

• 剩下的结果就是新的Stream，你会继续用它进行质数的查找。本质上，你还会回到
  第一步，继续进行后续的操作，所以这个算法是递归的

第一步： 构造由数字组成的Stream

使用方法 IntStream.iterate 构造由数字组成的Stream，它由2开始，可以上达无限

static Intstream numbers(){
        return IntStream.iterate(2, n -> n + 1);
}

第二步： 取得首元素

IntStream 类提供了方法 findFirst ，可以返回Stream的第一个元素：

static int head(IntStream numbers){
        return numbers.findFirst().getAsInt();
}

第三步： 对尾部元素进行筛选

static IntStream tail(IntStream numbers){
        return numbers.skip(1);
}

拿到Stream的头元素，像下面这段代码那样对数字进行筛选

IntStream numbers = numbers();
int head = head(numbers);
IntStream filtered = tail(numbers).filter(n -> n % head != 0);

第四步：递归地创建由质数组成的Stream

static IntStream primes(IntStream numbers) {
    int head = head(numbers);
    return IntStream.concat(
        IntStream.of(head),
        primes(tail(numbers).filter(n -> n % head != 0))
    );
}

如果执行步骤四中的代码，你会遭遇如下这个错误：“java.lang.IllegalStateException:
stream has already been operated upon or closed.”实际上，你正试图使用两个终端操作： findFirst和 skip 将Stream切分成头尾两部分。一旦你对Stream执行一次终端操作调用，它就永久地终止了！

你需要一种方法推迟 primes 中对 concat 的第二个参数计算。如果用更加技术性的程序设计术语来描述，我们称之为延迟计算、非限制式计算或者名调用。只在你需要处理质数的那个时刻（比如，要调用方法 limit 了）才对Stream进行计算

创建你自己的延迟列表

一个基本的链接列表

public interface MyList<T> {

    T head();
    MyList<T> tail();

    default boolean isEmpty() {
        return true;
    }
}



public class MyLinkedList<T> implements MyList<T> {

    private final T head;

    private final MyList<T> tail;

    public MyLinkedList(T head, MyList<T> tail) {
        this.head = head;
        this.tail = tail;
    }

    @Override
    public T head() {
        return head;
    }

    @Override
    public MyList<T> tail() {
        return tail;
    }

    public boolean isEmpty(){
        return false;
    }
}


public class Empty<T> implements MyList<T> {

    @Override
    public T head() {
        throw new UnsupportedOperationException();
    }

    @Override
    public MyList<T> tail() {
        throw new UnsupportedOperationException();
    }
}




public class M1 {


    public static void main(String[] args) {

        MyList<Integer> l =
                new MyLinkedList<>(5, new MyLinkedList<>(10, new Empty<>()));



    }
}

一个基础的延迟列表

对这个类进行改造，使其符合延迟列表的思想，最简单的方法是避免让 tail 立刻出现在内
存中，提供一个 Supplier<T> 方法（你也可以将其看成一个使用函数描述符void -> T 的工厂方法），它会产生列表的下一个节点

public class LazyList<T> implements MyList<T> {


    final T head;
    final Supplier<MyList<T>> tail;


    public LazyList(T head, Supplier<MyList<T>> tail) {
        this.head = head;
        this.tail = tail;
    }

    @Override
    public T head() {
        return head;
    }

//    注意，与前面的 head 不同，这//里 tail 使用了一个 Supplier//方法提供了延迟性
    @Override
    public MyList<T> tail() {
        return tail.get();
    }


    public boolean isEmpty() {
        return false;
    }
}

调用 Supplier 的 get 方法会触发延迟列表（ LazyList ）的节点创建，就像工厂会创建新的对象一样

现在，你可以像下面那样传递一个 Supplier 作为 LazyList 的构造器的 tail 参数，创建由数字构成的无限延迟列表了，该方法会创建一系列数字中的下一个元素

public class M2 {

    public static LazyList<Integer> from(int n) {
        return new LazyList<Integer>(n, () -> from(n+1));
    }


    public static void main(String[] args) {

        LazyList<Integer> numbers = from(2);
        int two = numbers.head();
        int three = numbers.tail().head();
        int four = numbers.tail().tail().head();
        System.out.println(two + " " + three + " " + four);

    }
}

生成质数

实现一个延迟筛选器

public MyList<T> filter(Predicate<T> p) {
    return isEmpty() ?
    this :
    p.test(head()) ?
    new LazyList<>(head(), () -> tail().filter(p)) :
    tail().filter(p);
}