第一节函数式范式

1. 什么是函数式编程

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

2. 函数式的基本特性

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

2.1 无副作用

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

引用透明

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

3. 函数式数据结构

3.1 基本数据类型

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

在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
    }
}

异常存在的两个问题

正如我们所讨论的，异常破坏了引用透明并引入了上下文依赖，让替代模型的简单推导无法适用，并可能写出令人困惑的代码
异常不是类型安全的，函数签名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 函数式数据结构

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

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

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)
                }
    }
}

模式匹配

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模式在不同的范式下已经发生了许多的变化：

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

科里化与部分施用

科里化：

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

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

部分施用

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

记忆模式

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

尾递归模式

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

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 的世界中，鼓励开发人员创建独特的数据结构，以方法的形式附加特定的操作。
函数范式入门(什么是函数式编程)-LMLPHP

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

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

本章知识点：

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

Yumenokanata

函数范式入门(什么是函数式编程)

第一节函数式范式

1. 什么是函数式编程

2. 函数式的基本特性

2.1 无副作用

引用透明

3. 函数式数据结构

3.1 基本数据类型

3.2 Sample: 异常处理

异常存在的两个问题

检测异常

异常的其他选择

Either类型

eg:

3.3 函数式数据结构

模式匹配

模式匹配

Haskell实现

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

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

4. 函数式设计模式

科里化与部分施用

科里化：

部分施用

记忆模式

尾递归模式

Trampoline：蹦床

函数级别的重用

To be continued

Yumenokanata

函数范式入门(什么是函数式编程)

第一节 函数式范式

1. 什么是函数式编程

2. 函数式的基本特性

2.1 无副作用

引用透明

3. 函数式数据结构

3.1 基本数据类型

3.2 Sample: 异常处理

异常存在的两个问题

检测异常

异常的其他选择

Either类型

eg:

3.3 函数式数据结构

模式匹配

模式匹配

Haskell实现

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

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

4. 函数式设计模式

科里化与部分施用

科里化：

部分施用

记忆模式

尾递归模式

Trampoline：蹦床

函数级别的重用

To be continued

第一节函数式范式