摘要：純函數(shù)式狀態(tài)隨機(jī)數(shù)生成器很明顯，原有的函數(shù)不是引用透明的，這意味著它難以被測試組合并行化。售貨機(jī)在輸出糖果時忽略所有輸入本章知識點(diǎn)惰性求值函數(shù)式狀態(tài)
第二節(jié)?惰性求值與函數(shù)式狀態(tài)
在下面的代碼中我們對List數(shù)據(jù)進(jìn)行了一些處理
List(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)
考慮一下這段程序是如何求值的，如果我們跟蹤一下求值過程，步驟如下：
List(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)
List(11,12,13,14).filter(_ % 2 == 0).map(_ * 3)
List(12,14).map(_ * 3)
List(36,42)
我們調(diào)用map和filter函數(shù)的時候，每次都會遍歷自身，對每個元素使用輸入的函數(shù)進(jìn)行求值。
那么如果我們對一系列的轉(zhuǎn)換融合為單個函數(shù)而避免產(chǎn)生臨時數(shù)據(jù)效率不是更高？
我們可以在一個for循環(huán)中手工完成，但更好的方式是能夠自動實(shí)現(xiàn)，并保留高階組合風(fēng)格。
非嚴(yán)格求值(惰性求值) 即是實(shí)現(xiàn)這種的產(chǎn)物，它是一項(xiàng)提升函數(shù)式編程效率和模塊化的基礎(chǔ)技術(shù)。
嚴(yán)格與非嚴(yán)格函數(shù)
非嚴(yán)格求值是一種屬性，稱一個函數(shù)是非嚴(yán)格求值即是這個函數(shù)可以選擇不對它的一個參數(shù)或多個參數(shù)求值。相反，一個嚴(yán)格求值函數(shù)總是對它的參數(shù)求值。
嚴(yán)格求值函數(shù)在大部分編程語言中是一種常態(tài)，而Haskell語言就是一個支持惰性求值的例子。Haskell不能保證任何語句會順序執(zhí)行（甚至完全不會執(zhí)行到），因?yàn)镠askell的代碼只有在需要的時候才會被執(zhí)行到。
嚴(yán)格求值的定義
如果對一個表達(dá)式的求值一直運(yùn)行或拋出一個錯誤而非返回一個定義的值，我們說這個表達(dá)式?jīng)]有結(jié)束，或者說它是evaluates to bottom(非正常返回)。
如果表達(dá)式f(x)對所有的evaluates to bottom的表達(dá)式x，也是evaluates to bottom，那么f是嚴(yán)格求值的
實(shí)際上我們經(jīng)常接觸非嚴(yán)格求值，比如&&和||操作符都是非嚴(yán)格求值函數(shù)
scala> false && { println("!!");true }
res0: Boolean = false
而另一個例子是if控制結(jié)構(gòu)：
if(input.isEmpty()) sys.error("empty") else input
if語句可以看作一個接收3個參數(shù)的函數(shù)(實(shí)際上Clojure中if就是這樣一個函數(shù))，一個Boolean類型的條件參數(shù)，一個返回類型為A的表達(dá)式在條件為true時執(zhí)行，另一個同樣返回類型為A的表達(dá)式在條件為false時執(zhí)行。
因此可以說，if函數(shù)對條件參數(shù)是嚴(yán)格求值，而對分支參數(shù)是非嚴(yán)格求值。
if_(a < 22,
() -> println("true"),
() -> println("false"))
而一個表達(dá)式的未求值形式我們稱為thunk
Scala中提供一種語法可以自動將表達(dá)式包裝為thunk：
def if_[A](cond: Boolean, onTrue: => A, onFalse: => A): A =
if(cond) onTrue else onFalse
這樣，在使用和調(diào)用的時候都不需要做任何特殊的寫法scala會為我們自動包裝：
if_(false, sys.error("fail"), 3)
默認(rèn)情況下以上包裝的thunk在每次引用的時候都會求值一次：
scala> def maybeTwice(b: Boolean, i => int) =
if(b) i+i else 0
scala> val x = maybeTwice(true, { println("hi"); 42})
hi
hi
x: Int = 84
所以Scala也提供一種語法可以延遲求值并保存結(jié)果，使后續(xù)引用不會觸發(fā)重復(fù)求值
scala> def maybeTwice(b: Boolean, i => int) = {
| lazy val j = i
| if(b) j+j else 0
| }
scala> val x = maybeTwice(true, { println("hi"); 42})
hi
x: Int = 84
Kotlin在1.1版本中通過委托屬性的方式提供了這種特性的實(shí)現(xiàn)
惰性列表
定義：
sealed class Stream {
abstract val head: () -> A
abstract val tail: () -> Stream
object Empty : Stream() {...}
data class Cons(val h: () -> A,
val t: () -> Stream)
: Stream() {...}
...
}
sealed class List {
abstract val head: A
abstract val tail: List
object Nil : List() {...}
data class Cons(val head: A,
val tail: List)
: List() {...}
...
}
eg:
Stream.apply(1, 2, 3, 4)
.map { it + 10 }
.filter { it % 2 == 0 }
.toList()
toList()方法請求數(shù)據(jù)，然后請求到1，然后經(jīng)過一系列計(jì)算回到toList();然后請求下一個數(shù)據(jù)，依次類推直到無數(shù)據(jù)可取toList()方法結(jié)束。
無限流與共遞歸
eg:
fun ones(): Stream = Stream.cons({ 1 }, { ones() })
fun constant(a: A): Stream =
Cons({ a }, { constant(a) })
val fibs = {
fun go(f0: Int, f1: Int): Stream =
cons({ f0 }, { go(f1, f0+f1) })
go(0, 1)
}
unfold函數(shù)
fun unfold(z: S, f: (S) -> Option>)
: Stream {
val option = f(z)
return when {
option is Option.Some -> {
val h = option.get.first
val s = option.get.second
cons({ h }, { unfold(s, f) })
}
else -> empty()
}
}
似乎和Iterator很像，但這里返回的是一個惰性列表，并且沒有可變量
共遞歸有時也稱為守護(hù)遞歸，生產(chǎn)能力有時也稱為共結(jié)束
函數(shù)式編程的主題之一便是關(guān)注分離，希望能將計(jì)算的描述和實(shí)際運(yùn)行分開。比如
一等函數(shù)：函數(shù)體內(nèi)的邏輯只有在接收到參數(shù)的時候才執(zhí)行
Either：將捕獲的錯誤和如何對錯誤進(jìn)行處理進(jìn)行分離
Stream：將如何產(chǎn)生一系列元素的邏輯和實(shí)際生成元素進(jìn)行分離
惰性計(jì)算便是實(shí)踐這一思想。
惰性計(jì)算是只有在必要時才進(jìn)行計(jì)算固然在很多方面都提供了好處(無限列表、計(jì)算延遲等等)，但這也意味著對函數(shù)的純凈度有更高的要求：
由于不確定傳入的函數(shù)什么時候執(zhí)行、按什么順序執(zhí)行(在性能優(yōu)化的時候進(jìn)行指令重排)、甚至?xí)粫?zhí)行，如果傳給map或者filter的函數(shù)是有副作用的，就會使程序狀態(tài)變得不可控。
eg:
public Adapter getAdapter() {
BaseAdapter adapter = new ListAdapter(getContext());
presenter.getListData()
.map(m -> m.getName())
.subscribe(adapter::setData);
return adapter;
}
public Observable> getAdapter() {
return Observable.zip(
Observable.just(getContext())
.map(c -> new ListAdapter(c)),
presenter.getListData()
.map(m -> m.getName()),
(adapter, data) -> adapter.setData(data));
}
public Observable> getAdapter(
Context context,
Observable dataProvider) {
return Observable.zip(
Observable.just(context)
.map(c -> new ListAdapter(c)),
dataProvider
.map(m -> m.getName()),
(adapter, data) -> adapter.setData(data));
}
純函數(shù)式狀態(tài)
eg:
隨機(jī)數(shù)生成器：
public static int main(String[] args) {
Random random = new Random();
System.out.println(random.nextInt());
System.out.println(random.nextInt());
System.out.println(random.nextInt());
}
很明顯，原有的Random函數(shù)不是引用透明的，這意味著它難以被測試、組合、并行化。
比如現(xiàn)在有一個函數(shù)模擬6面色子
fun rollDie(): Int {
val rng = Random()
return rng.nextInt(6)
}
我們希望它能返回1～6的值，然而它返回的是0～5，在測試時有一定可能會失敗，然而在失敗時希望重現(xiàn)失敗也不切實(shí)際。
也許我們可以通過傳入指定的Random對象保證一致的生成：
fun rollDie(rng : Random): Int {
return rng.nextInt(6)
}
但調(diào)用一次nextInt方法后Random上一次的狀態(tài)就丟失了，這意味著我們還需要傳一個調(diào)用次數(shù)的參數(shù)？
不，我們應(yīng)該避開副作用
定義：
interface Rng {
fun nextInt: (Int, Rng)
}
class LcgRng(val seed: Int = System.currentTimeMillis())
: Rng {
//線性同余算法
fun nextInt(): Pair {
val newSeed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;
val nextRng = LcgRng(newSeed)
val n = (newSeed >>> 16).toInt();
return Pair(n, nextRng);
}
}
更加范化此生成器我們可以定義：
type Rand[+A] = RNG => (A, RNG)
基于這個隨機(jī)數(shù)生成器我們可以進(jìn)行更加靈活的組合：
val int: Rand[Int] = _.nextInt
def map[A,B](s: Rand[A])(f: A => B): Rand[B]
def double(rng: RNG): (Double, RNG)
def map2[A,B,C](ra: Rand[A], rb: Rand[B],
f: (A, B) => C): Rand[C]
def flatMap[A,B](f: Rand[A])(g: A => Rand[B]): Rand[B]
更為通用的狀態(tài)行為數(shù)據(jù)類型：
scala
case class State[S, +A](run: S => (A, S))
kotlin
class State(val run: (S) -> Pair)
java
public final class State {
private final F> runF;
}
for推導(dǎo)
val ns: Rand[List[Int]] =
//int為Rand[Int]的值，生成一個隨機(jī)整數(shù)
int.flatMap(x =>
//ints(x)生成一個長度為x的list
ints(x).map(xs =>
//list中的每個元素變換為除以y的余數(shù)
xs.map(_ % y))))
for推導(dǎo)語句：
val ns: Rand[List[Int]] = for {
x <- int
y <- int
xs <- ints(x)
} yield xs.map(_ % y)
類似Haskell的Do語句
for推導(dǎo)使得書寫風(fēng)格更加命令式、更加易懂
Avocado(為Java中實(shí)現(xiàn)do語法的小工具)
DoOption
.do_(() -> Optional.ofNullable("1"))
.do_(() -> Optional.ofNullable("2"))
.do_12((x, y) -> Optional.ofNullable(x + y))
.return_123((t1, t2, t3) -> t1 + t2 + t3)
.ifPresent(System.out::println);
經(jīng)典問題：
實(shí)現(xiàn)一個對糖果售貨機(jī)建模的有限狀態(tài)機(jī)。機(jī)器有兩種輸入方式：可以投入硬幣，或可以按動按鈕獲取糖果。它可以有一種或兩種狀態(tài)：鎖定或非鎖定。它也可以跟蹤還剩多少糖果以及有多少硬幣。
機(jī)器遵循下面的規(guī)則：
對一個鎖定狀態(tài)的售貨機(jī)投入一枚硬幣，如果有剩余的糖果它將變?yōu)榉擎i定狀態(tài)。
對一個非鎖定狀態(tài)的售貨機(jī)按下按鈕，它將給出糖果并變回鎖定狀態(tài)。
對一個鎖定狀態(tài)的售貨機(jī)按下按鈕或?qū)Ψ擎i定狀態(tài)的售貨機(jī)投入硬幣，什么也不做。
售貨機(jī)在“輸出”糖果時忽略所有“輸入”
sealed trait Input
case object Coin extends Input
case object Turn extends Input
case class Machine(locked: Boolean, candies: Int,
coins: Int)
object Candy {
def update = (i: Input) => (s: Machine) =>
(i, s) match {
case (_, Machine(_, 0, _)) => s
case (Coin, Machine(false, _, _)) => s
case (Turn, Machine(true, _, _)) => s
case (Coin, Machine(true, candy, coin)) =>
Machine(false, candy, coin + 1)
case (Turn, Machine(false, candy, coin)) =>
Machine(true, candy - 1, coin)
}
def simulateMachine(inputs: List[Input])
: State[Machine, (Int, Int)] = for {
_ <- sequence(inputs map (modify[Machine] _ compose update))
s <- get
} yield (s.coins, s.candies)
}
本章知識點(diǎn)：
惰性求值
函數(shù)式狀態(tài)
To be continued
