定義一些基本操作

伴生對象
除了經(jīng)常聲明的數(shù)據(jù)類型和數(shù)據(jù)構(gòu)造器之外，我們也經(jīng)常聲明伴生對象。它只是與數(shù)據(jù)類型同名的一個(gè)單例，通常在里面定義一些用于創(chuàng)建或處理數(shù)據(jù)類型的便捷方法。
正如之前所說，函數(shù)式需要保持不變性，對于類就包括屬性的不變和方法的不變：

屬性不變，所以我們只能使用純函數(shù)操作它們，而容納這些操作函數(shù)的地方通常就是在伴生對象。
方法不變，所以通常情況下函數(shù)范式不鼓勵(lì)繼承(這也是為什么Kotlin的類默認(rèn)不可繼承)，而是鼓勵(lì)我們通過各種組合子和接口(在不同語言有不同叫法，Swift叫協(xié)議、Scala叫特質(zhì)，Haskell本來就沒有OO中的“類”概念所以叫做“類型類”)的組合來描述復(fù)雜的關(guān)系。

用伴生對象是Scala中的一種慣例。Kotlin也引入了它。

關(guān)于型變
在sealed class List的聲明里，泛型A前的“out”是一個(gè)型變符號，代表A是協(xié)變的，類似Java中的“extend”。意味著如果Dog是Animal的子類，那么List是List的子類型。
型變分為三種：

協(xié)變 是可以用自己替換需要自己父親的位置而是允許的，也就是當(dāng)參數(shù)需要父類型參數(shù)時(shí)你可以傳入子類型
逆變 就是可以用父親替換兒子的位置而是允許的，也就是當(dāng)參數(shù)需要子類型的時(shí)候可以傳入父類型
不變 就是不能改變參數(shù)類型

它是理解類型系統(tǒng)的重要基石，但通常不用太在意型變注釋，不用型變注釋也會使函數(shù)簽名簡單些，只是對于接口而言會失去很多靈活性。

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: _*))

模式匹配類似一個(gè)別致的switch聲明，它可以侵入到表達(dá)式的數(shù)據(jù)結(jié)構(gòu)內(nèi)部（Kotlin只做到了自動類型轉(zhuǎn)換）。
Scala中用關(guān)鍵字“match”和花括號封裝的一系列case語句構(gòu)成。
每一條case語句由“=>”箭頭左邊的模式和右邊的結(jié)果構(gòu)成，如果匹配其中一種模式就返回右邊的對應(yīng)結(jié)果。

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

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)

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

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

當(dāng)我們對一個(gè)已存在的列表xs在前面添加一個(gè)元素1的時(shí)候，返回一個(gè)新的列表，即Cons(1, xs),既然列表是不可變的，我們不需要去復(fù)制一份xs，可以直接復(fù)用它，這稱為 數(shù)據(jù)共享。
共享不可變數(shù)據(jù)可以讓函數(shù)實(shí)現(xiàn)更高的效率。我們可以返回不可變數(shù)據(jù)結(jié)構(gòu)而不用擔(dān)心后續(xù)代碼修改它，不需要悲觀地復(fù)制一份以避免對其修改或污染。
所有關(guān)于更高效支持不同操作方式的純函數(shù)式數(shù)據(jù)結(jié)構(gòu)，其實(shí)都是找到一種聰明的方式來利用數(shù)據(jù)共享。
正因如此，在大型程序里，函數(shù)式編程往往能取得比依賴副作用更好的性能。

函數(shù)范式是不同于面向?qū)ο蟮木幊谭妒剑绻覀円詫ο鬄楸荆秃苋菀撞蛔杂X地按照對象的術(shù)語來思考所有問題的答案。
我們需要改變思維，學(xué)會用不同的范式處理不同的問題。

因?yàn)楹瘮?shù)式世界用來搭建程序的材料不一樣了，所以解決問題的手法也不一樣了。GoF模式在不同的范式下已經(jīng)發(fā)生了許多的變化：

模式已經(jīng)被吸收為語言的一部分

模式中描述的解決辦法在函數(shù)式范式下依然成立，但實(shí)現(xiàn)細(xì)節(jié)有所變化。

由于在新的語言或范式下獲得了原本沒有的能力，產(chǎn)生了新的解決方案。

詳細(xì)： Scala與Clojure函數(shù)式編程模式：Java虛擬機(jī)高效編程

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

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

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

對純函數(shù)的調(diào)用結(jié)果進(jìn)行緩存，從而避免執(zhí)行相同的計(jì)算。
由于在給定參數(shù)不變的情況下，純函數(shù)始終會返回相同的值，所以我們可以采用緩存的調(diào)用結(jié)果來替代重復(fù)的純函數(shù)調(diào)用。

所有被記憶的函數(shù)必須保證：

沒有副作用
不依賴任何外部信息

Groovy和Clojure有都內(nèi)建的memoize函數(shù)。
Scala和Kotlin可以擴(kuò)展實(shí)現(xiàn)（內(nèi)部的實(shí)現(xiàn)方法可以看做局部作用，關(guān)于局部作用最后一章會詳講）

在不使用可變狀態(tài)且沒有棧溢出的情況下完成對某個(gè)計(jì)算的重復(fù)執(zhí)行。

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

尾遞歸對函數(shù)寫法有嚴(yán)格的要求，但一方面有些語言不支持(如Java)，另一方面尾遞歸被大量使用，因此引入了應(yīng)對棧溢出的通用解決方案：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]

未優(yōu)化：

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

當(dāng)程序在JVM中進(jìn)行函數(shù)調(diào)用時(shí)，它將棧中壓入調(diào)用幀。而Trampoline將這種控制邏輯在Trampoline數(shù)據(jù)結(jié)構(gòu)中顯式地描述了出來。
當(dāng)解釋Free程序時(shí)，它將決定程序是否請求使用Suspend(s)執(zhí)行某些“作用”，還是使用FlatMap(x,f)調(diào)用子程序。
取代采用調(diào)用棧，它將調(diào)用x，然后通過在結(jié)果上調(diào)用f繼續(xù)。而且f無論何時(shí)都立即返回，再次將控制交于執(zhí)行的run()函數(shù)。

這種方式其實(shí)可以認(rèn)為是一種 協(xié)程

Scala中的Trampoline采用語言原生的尾遞歸優(yōu)化實(shí)現(xiàn)：

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

尾遞歸實(shí)現(xiàn)涉及大量后面會講的知識，因此此處不會詳解

FunctionalJava中則直接通過循環(huán)替換遞歸的方式實(shí)現(xiàn)：

OOP開發(fā)人員習(xí)慣于框架級別的重用；在面向?qū)ο蟮恼Z言中進(jìn)行重用所需的必要構(gòu)件需要非常大的工作量，他們通常會將精力留給更大的問題。

面向?qū)ο笙到y(tǒng)由一群互相發(fā)送消息(或者叫做調(diào)用方法)的對象組成。如果我們從中發(fā)現(xiàn)了一小群有價(jià)值的類以及相應(yīng)的消息，就可以將這部分類關(guān)系提取出來，加以重用。它們重用的單元是類以及與這些類進(jìn)行通信的消息。
該領(lǐng)域的開創(chuàng)性著作是《設(shè)計(jì)模式》，至少為每個(gè)模式提供一個(gè)類圖。在 OOP 的世界中，鼓勵(lì)開發(fā)人員創(chuàng)建獨(dú)特的數(shù)據(jù)結(jié)構(gòu)，以方法的形式附加特定的操作。

函數(shù)級的封裝支持在比構(gòu)建自定義類結(jié)構(gòu)更細(xì)的基礎(chǔ)級別上進(jìn)行重用，在列表和映射等基本數(shù)據(jù)結(jié)構(gòu)之上通過高階函數(shù)提供定制，從而實(shí)現(xiàn)重用。
例如，在下面的代碼中，filter() 方法接受使用一個(gè)代碼塊作為 “插件” 高階函數(shù)（該函數(shù)確定了篩選條件），而該機(jī)制以有效方式應(yīng)用了篩選條件，并返回經(jīng)過篩選的列表。

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

在后面的《函數(shù)設(shè)計(jì)的通用結(jié)構(gòu)》這一節(jié)中我們會詳細(xì)體會到函數(shù)范式中這種高抽象度的重用思想

本章知識點(diǎn)：

函數(shù)范式的定義及基本特性

函數(shù)式數(shù)據(jù)結(jié)構(gòu)

函數(shù)式設(shè)計(jì)模式