第一节 函数式范式

1. 什么是函数式编程

• 函数式编程（英语：functional programming）或称函数程序设计，又称泛函编程，是一种编程范型，它将电脑运算视为数学上的函数计算，并且避免使用程序状态以及易变对象。函数编程语言最重要的基础是 λ演算 （lambda calculus）。而且λ演算的函数可以接受函数当作输入（引数）和输出（传出值）。
• 比起命令式编程，函数式编程更加强调程序执行的结果而非执行的过程，倡导利用若干简单的执行单元让计算结果不断渐进，逐层推导复杂的运算，而不是设计一个复杂的执行过程。

2. 函数式的基本特性

• 不可变性
• 无副作用(纯函数、引用透明)
• 惰性计算
• 高阶函数
• ...

2.1 无副作用

• 对于程序p，如果它包含的表达式e满足 引用透明 ，则所有的e都可以被替换为它的运算结果而不会改变程序p的含义。
• 假设存在一个函数f，若表达式f(x)对所有引用透明的表达式x也是引用透明的，那么这个f是一个 纯函数

函数范式其实核心解决的就是副作用的问题, 无论是隔离副作用的IO还是不可变都是为了解决这个问题而存在. 所以对于副作用的理解一定要足够深刻. 对于GUI开发人员而言副作用尤其无处不在, 实际开发中会使用大量的手法和技巧去隔离它们.

引用透明

引用透明的另一种理解方式是，引用透明的表达式不依赖上下文，可以本地推导，而那些非引用透明的表达式是依赖上下文，并且需要全局推导。

3. 函数式数据结构

3.1 基本数据类型

100个函数操作一种数据结构的组合要好过10个函数操作10种数据结构的组合。

在OOP的世界中，开发者被鼓励针对具体问题建立专门的数据结构，并以方法的形式，将专门的操作关联在数据结构上。

而函数式采用了另一种重用思路，它们用很少一组关键数据结构（如list、set、map）来搭配专为这些数据结构深度优化过的操作。在这些关键数据结构和操作构成的一套运转机构上，按需要插入另外的数据结构（之后会讲解）和高阶函数来调整以适应具体问题。

比如在xml解析问题上，java语音xml解析框架繁多，每一种都有自己定制的数据结构和方法语义。而函数式语言Clojure做法相反，它不鼓励使用专门的数据结构，而是将xml解析成标准的map结构，而Clojure本身有极为丰富的工具可以与map结构相配合，甚至可以说有几乎无数的方法可以操作这些核心数据结构。只要将之适配到这些已有结构上，就可以以统一的方式完成工作

这种构建思想被称为"面向组合子编程", 其实是一种真正更加贴近"数据结构+算法"的构建方式, 以后也许会详细讲到

3.2 Sample: 异常处理

fun failingFn2(i: Int): Int {
    val y: Int = (throw Exception("fail"))
    try {
        val x = 42 + 5
        return x + y
    } catch (e: Exception) {
        return 43
    }
}

可以证明y不是引用透明的。我们用表达式的值替代y，却会得到不同的语义

fun failingFn2(i: Int): Int {
    try {
        val x = 42 + 5
        // 引用透明的概念中，表达式可以被它引用的值替代，
        // 这种替代保持程序的含义。
        // 而我们对 x+y 表达式中的y替代为
        // throw Exception("fail")会产生不同的结果
        return x + ((throw Exception("fail")) as Int)
    } catch (e: Exception) {
        return 43
    }
}

异常存在的两个问题

1. 正如我们所讨论的，异常破坏了引用透明并引入了上下文依赖，让替代模型的简单推导无法适用，并可能写出令人困惑的代码
2. 异常不是类型安全的，函数签名failingFn和(Int) → Int 的函数类型没有告诉我们可能发生什么样的异常，导致异常在运行时才能被检测到。

坊间的一个习惯是建议异常应该只用于错误处理而非控制流

检测异常

Java的异常检测最低程度地强制了是处理错误还是抛出错误，但它们导致了调用者对于签名模板的修改。
但最重要的是它们不适用于高阶函数，因为高阶函数不可能感知由它的参数引起的特定的异常。
例如考虑对List定义的map函数：

fun <A, B> map(l: List<A>, f: (A) -> B): List<B>

这个函数很清晰，高度泛化，但与使用检测异常不同的是，我们不能对每一个被f抛出的异常的检测都有一个版本的map。

异常的其他选择

Either类型

sealed class Either<L, R> {
  data class Left<L, R>(val value: L): Either<L, R>()
  data class Right<L, R>(val value: R): Either<L, R>()
}

eg:

data class Person(val name: Name, val age: Age)
data class Name(val value: String)
data class Age(val value: Int)

fun mkName(name: String): Either<String, Name> =
        if(name.isEmpty()) Either.Left("Name is empty.")
        else Either.Right(Name(name))

fun mkAge(age: Int): Either<String, Age> =
        if(age < 0) Either.Left("Age is out of range.")
        else Either.Right(Age(age))

fun mkPerson(name: String, age: Int)
        : Either<String, Person> =
        mkName(name).map2(mkAge(age))
        { n, a -> Person(n, a) }

3.3 函数式数据结构

函数式数据结构被定义为不可变的，函数式数据结构只能被纯函数操作。

比如连接两个list会产生一个新的list，对输入的两个list不做改变。

这是否意味着我们要对数据做很多额外的复制？答案是否定的

我们可以先检验一下最普遍存在的函数式数据结构：单项列表

sealed class List<out A> {
    object Nil: List<Nothing>()
    data class Cons<A>(val head: A,
                       val tail: List<A>): List<A>()
}

定义一些基本操作

sealed class List<out A> {
    ...
    // 伴生对象
    companion object {
        fun sum(ints: List<Int>): Int =
                when(ints) {
                    is Nil -> 0
                    is Cons -> ints.head + sum(ints.tail)
                }

        fun <A> apply(vararg args: A): List<A> =
                if (args.isEmpty()) Nil
                else Cons(args.head, apply(*args.tail))

        fun product(ds: List<Double>): Double =
                when(ds){
                    is Nil -> 1.0
                    is Cons ->
                        if(ds.head == 0.0) 0.0
                        else ds.head * product(ds.tail)
                }
    }
}

伴生对象

除了经常声明的数据类型和数据构造器之外，我们也经常声明伴生对象。它只是与数据类型同名的一个单例，通常在里面定义一些用于创建或处理数据类型的便捷方法。
正如之前所说，函数式需要保持不变性，对于类就包括属性的不变和方法的不变：

1. 属性不变，所以我们只能使用纯函数操作它们，而容纳这些操作函数的地方通常就是在伴生对象。
2. 方法不变，所以通常情况下函数范式不鼓励继承(这也是为什么Kotlin的类默认不可继承)，而是鼓励我们通过各种组合子和接口(在不同语言有不同叫法，Swift叫协议、Scala叫特质，Haskell本来就没有OO中的“类”概念所以叫做“类型类”)的组合来描述复杂的关系。

用伴生对象是Scala中的一种惯例。Kotlin也引入了它。

关于型变

在sealed class List<out A>的声明里，泛型A前的“out”是一个型变符号，代表A是协变的，类似Java中的“extend”。意味着如果Dog是Animal的子类，那么List<Dog>是List<Animal>的子类型。
型变分为三种：

• 协变 是可以用自己替换需要自己父亲的位置而是允许的，也就是当参数需要父类型参数时你可以传入子类型
• 逆变 就是可以用父亲替换儿子的位置而是允许的，也就是当参数需要子类型的时候可以传入父类型
• 不变 就是不能改变参数类型

它是理解类型系统的重要基石，但通常不用太在意型变注释，不用型变注释也会使函数签名简单些，只是对于接口而言会失去很多灵活性。

模式匹配

Kotlin的模式匹配太简单了，还是看看Scala的模式匹配吧

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A,
                    tail: List[A]) extends List[A]

object List {
  def sum(ints: List[Int]): Int = ints match {
    case Nil => 0
    case Cons(x,xs) => x + sum(xs)
  }

  def product(ds: List[Double]): Double = ds match {
    case Nil => 1.0
    case Cons(0.0, _) => 0.0
    case Cons(x,xs) => x * product(xs)
  }

  def apply[A](as: A*): List[A] = 
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail: _*))

模式匹配

模式匹配类似一个别致的switch声明，它可以侵入到表达式的数据结构内部（Kotlin只做到了自动类型转换）。
Scala中用关键字“match”和花括号封装的一系列case语句构成。
每一条case语句由“=>”箭头左边的模式和右边的结果构成，如果匹配其中一种模式就返回右边的对应结果。

def product(ds: List[Double]): Double = ds match {
    case Nil => 1.0
    case Cons(0.0, _) => 0.0
    case Cons(x,xs) => x * product(xs)
  }

Haskell实现

data List a = Nil | Cons a (List a) deriving (Show)

sum :: List Integer -> Integer
sum Nil = 0
sum (Cons x xs) = x + (sum xs)

product :: List Double -> Double
product Nil = 1
product (Cons 0 t) = 0
product (Cons x xs) = x * product xs

apply :: [a] -> List a
apply [] = Nil
apply (x:xs) = Cons x (apply xs)

Avocado中的模式匹配DSL(早期为Java实现模式匹配开发的小工具)

public Integer sum(List<Integer> ints) {
    return match(ints)
            .empty(() -> 0)
            .matchF((x, xs) -> x + sum(xs))
            .el_get(0);
}

public Double product(List<Double> ds) {
    return match(ds)
            .empty(() -> 1.0)
            .matchF(0.0, xs -> 0.0)
            .matchF((x, xs) -> x * product(xs))
            .el_get(0.0);
}

函数式数据结构中的数据共享

当我们对一个已存在的列表xs在前面添加一个元素1的时候，返回一个新的列表，即Cons(1, xs),既然列表是不可变的，我们不需要去复制一份xs，可以直接复用它，这称为 数据共享。
共享不可变数据可以让函数实现更高的效率。我们可以返回不可变数据结构而不用担心后续代码修改它，不需要悲观地复制一份以避免对其修改或污染。
所有关于更高效支持不同操作方式的纯函数式数据结构，其实都是找到一种聪明的方式来利用数据共享。
正因如此，在大型程序里，函数式编程往往能取得比依赖副作用更好的性能。

4. 函数式设计模式

函数范式是不同于面向对象的编程范式，如果我们以对象为本，就很容易不自觉地按照对象的术语来思考所有问题的答案。
我们需要改变思维，学会用不同的范式处理不同的问题。

因为函数式世界用来搭建程序的材料不一样了，所以解决问题的手法也不一样了。GoF模式在不同的范式下已经发生了许多的变化：

• 模式已经被吸收为语言的一部分
• 模式中描述的解决办法在函数式范式下依然成立，但实现细节有所变化。
• 由于在新的语言或范式下获得了原本没有的能力，产生了新的解决方案。

详细： Scala与Clojure函数式编程模式：Java虚拟机高效编程

科里化与部分施用

科里化：

(A, B, C) -> D  ==> (A) -> (B) -> (C) -> D

//Java lambda
a -> b -> c -> d

部分施用

(A, B, C) -> D  ==> (A， C) -> D

记忆模式

对纯函数的调用结果进行缓存，从而避免执行相同的计算。
由于在给定参数不变的情况下，纯函数始终会返回相同的值，所以我们可以采用缓存的调用结果来替代重复的纯函数调用。

1. 所有被记忆的函数必须保证：

• 没有副作用
• 不依赖任何外部信息

1. Groovy和Clojure有都内建的memoize函数。

Scala和Kotlin可以扩展实现（内部的实现方法可以看做局部作用，关于局部作用最后一章会详讲）

尾递归模式

在不使用可变状态且没有栈溢出的情况下完成对某个计算的重复执行。

tailrec fun findFixPoint(x: Double = 1.0): Double = 
        if (x == Math.cos(x)) x
        else findFixPoint(Math.cos(x))

Trampoline：蹦床

尾递归对函数写法有严格的要求，但一方面有些语言不支持(如Java)，另一方面尾递归被大量使用，因此引入了应对栈溢出的通用解决方案：Trampoline

sealed trait Free[F[_],A] {
  def flatMap[B](f: A => Free[F,B]): Free[F,B] =
    FlatMap(this, f)
  def map[B](f: A => B): Free[F,B] =
    flatMap(f andThen (Return(_)))
}
case class Return[F[_],A](a: A) extends Free[F, A]
case class Suspend[F[_],A](s: F[A]) extends Free[F, A]
case class FlatMap[F[_],A,B](s: Free[F, A],
                             f: A => Free[F, B]) extends Free[F, B]

未优化：

val f = (x: Int) => x
val g = List.fill(10000)(f).foldLeft(f)(_ compose _)

scala> g(42)
java.lang.StackOverflowError

Trampoline：

val f: Int => Free[Int] = (x: Int) => Return(x)
val g = List.fill(10000)(f).foldLeft(f) {
    (a, b) => x => Suspend(() => a(x).flatMap(b))
}

伪代码：

FlatMap(a1, a1 => 
    FlatMap(a2, a2 => 
        FlatMap(a3, a4 =>
            ...
            DlatMap(aN, aN => Return(aN)))))

当程序在JVM中进行函数调用时，它将栈中压入调用帧。而Trampoline将这种控制逻辑在Trampoline数据结构中显式地描述了出来。
当解释Free程序时，它将决定程序是否请求使用Suspend(s)执行某些“作用”，还是使用FlatMap(x,f)调用子程序。
取代采用调用栈，它将调用x，然后通过在结果上调用f继续。而且f无论何时都立即返回，再次将控制交于执行的run()函数。

这种方式其实可以认为是一种 协程

Scala中的Trampoline采用语言原生的尾递归优化实现：

@annotation.tailrec
def runTrampoline[A](a: Free[Function0,A]): A = (a) match {
  case Return(a) => a
  case Suspend(r) => r()
  case FlatMap(x,f) => x match {
    case Return(a) => runTrampoline { f(a) }
    case Suspend(r) => runTrampoline { f(r()) }
    case FlatMap(a0,g) => runTrampoline { a0 flatMap { a0 => g(a0) flatMap f } }
  }
}

尾递归实现涉及大量后面会讲的知识，因此此处不会详解

FunctionalJava中则直接通过循环替换递归的方式实现：

public final A run() {
  Trampoline<A> current = this;
  while (true) {
    final Either<P1<Trampoline<A>>, A> x = 
        current.resume();
    for (final P1<Trampoline<A>> t : x.left()) {
      current = t._1();
    }
    for (final A a : x.right()) {
      return a;
    }
  }
}

OOP开发人员习惯于框架级别的重用；在面向对象的语言中进行重用所需的必要构件需要非常大的工作量，他们通常会将精力留给更大的问题。

函数级别的重用

面向对象系统由一群互相发送消息(或者叫做调用方法)的对象组成。如果我们从中发现了一小群有价值的类以及相应的消息，就可以将这部分类关系提取出来，加以重用。它们重用的单元是类以及与这些类进行通信的消息。
该领域的开创性著作是《设计模式》，至少为每个模式提供一个类图。在 OOP 的世界中，鼓励开发人员创建独特的数据结构，以方法的形式附加特定的操作。

函数级的封装支持在比构建自定义类结构更细的基础级别上进行重用，在列表和映射等基本数据结构之上通过高阶函数提供定制，从而实现重用。
例如，在下面的代码中，filter() 方法接受使用一个代码块作为 “插件” 高阶函数（该函数确定了筛选条件），而该机制以有效方式应用了筛选条件，并返回经过筛选的列表。

List<Integer> transactionsIds = transactions.parallelStream()
    .filter(t -> t.getType() == Transaction.GROCERY)
    .collect(toList());

在后面的《函数设计的通用结构》这一节中我们会详细体会到函数范式中这种高抽象度的重用思想

本章知识点：

1. 函数范式的定义及基本特性
2. 函数式数据结构
3. 函数式设计模式

To be continued