摘要：純函數式狀態隨機數生成器很明顯，原有的函數不是引用透明的，這意味著它難以被測試組合并行化。售貨機在輸出糖果時忽略所有輸入本章知識點惰性求值函數式狀態
第二節?惰性求值與函數式狀態
在下面的代碼中我們對List數據進行了一些處理
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)
我們調用map和filter函數的時候，每次都會遍歷自身，對每個元素使用輸入的函數進行求值。
那么如果我們對一系列的轉換融合為單個函數而避免產生臨時數據效率不是更高？
我們可以在一個for循環中手工完成，但更好的方式是能夠自動實現，并保留高階組合風格。
非嚴格求值(惰性求值) 即是實現這種的產物，它是一項提升函數式編程效率和模塊化的基礎技術。
嚴格與非嚴格函數
非嚴格求值是一種屬性，稱一個函數是非嚴格求值即是這個函數可以選擇不對它的一個參數或多個參數求值。相反，一個嚴格求值函數總是對它的參數求值。
嚴格求值函數在大部分編程語言中是一種常態，而Haskell語言就是一個支持惰性求值的例子。Haskell不能保證任何語句會順序執行（甚至完全不會執行到），因為Haskell的代碼只有在需要的時候才會被執行到。
嚴格求值的定義
如果對一個表達式的求值一直運行或拋出一個錯誤而非返回一個定義的值，我們說這個表達式沒有結束，或者說它是evaluates to bottom(非正常返回)。
如果表達式f(x)對所有的evaluates to bottom的表達式x，也是evaluates to bottom，那么f是嚴格求值的
實際上我們經常接觸非嚴格求值，比如&&和||操作符都是非嚴格求值函數
scala> false && { println("!!");true }
res0: Boolean = false
而另一個例子是if控制結構：
if(input.isEmpty()) sys.error("empty") else input
if語句可以看作一個接收3個參數的函數(實際上Clojure中if就是這樣一個函數)，一個Boolean類型的條件參數，一個返回類型為A的表達式在條件為true時執行，另一個同樣返回類型為A的表達式在條件為false時執行。
因此可以說，if函數對條件參數是嚴格求值，而對分支參數是非嚴格求值。
if_(a < 22,
() -> println("true"),
() -> println("false"))
而一個表達式的未求值形式我們稱為thunk
Scala中提供一種語法可以自動將表達式包裝為thunk：
def if_[A](cond: Boolean, onTrue: => A, onFalse: => A): A =
if(cond) onTrue else onFalse
這樣，在使用和調用的時候都不需要做任何特殊的寫法scala會為我們自動包裝：
if_(false, sys.error("fail"), 3)
默認情況下以上包裝的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也提供一種語法可以延遲求值并保存結果，使后續引用不會觸發重復求值
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版本中通過委托屬性的方式提供了這種特性的實現
惰性列表
定義：
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()方法請求數據，然后請求到1，然后經過一系列計算回到toList();然后請求下一個數據，依次類推直到無數據可取toList()方法結束。
無限流與共遞歸
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函數
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很像，但這里返回的是一個惰性列表，并且沒有可變量
共遞歸有時也稱為守護遞歸，生產能力有時也稱為共結束
函數式編程的主題之一便是關注分離，希望能將計算的描述和實際運行分開。比如
一等函數：函數體內的邏輯只有在接收到參數的時候才執行
Either：將捕獲的錯誤和如何對錯誤進行處理進行分離
Stream：將如何產生一系列元素的邏輯和實際生成元素進行分離
惰性計算便是實踐這一思想。
惰性計算是只有在必要時才進行計算固然在很多方面都提供了好處(無限列表、計算延遲等等)，但這也意味著對函數的純凈度有更高的要求：
由于不確定傳入的函數什么時候執行、按什么順序執行(在性能優化的時候進行指令重排)、甚至會不會執行，如果傳給map或者filter的函數是有副作用的，就會使程序狀態變得不可控。
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));
}
純函數式狀態
eg:
隨機數生成器：
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函數不是引用透明的，這意味著它難以被測試、組合、并行化。
比如現在有一個函數模擬6面色子
fun rollDie(): Int {
val rng = Random()
return rng.nextInt(6)
}
我們希望它能返回1～6的值，然而它返回的是0～5，在測試時有一定可能會失敗，然而在失敗時希望重現失敗也不切實際。
也許我們可以通過傳入指定的Random對象保證一致的生成：
fun rollDie(rng : Random): Int {
return rng.nextInt(6)
}
但調用一次nextInt方法后Random上一次的狀態就丟失了，這意味著我們還需要傳一個調用次數的參數？
不，我們應該避開副作用
定義：
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)
基于這個隨機數生成器我們可以進行更加靈活的組合：
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]
更為通用的狀態行為數據類型：
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推導
val ns: Rand[List[Int]] =
//int為Rand[Int]的值，生成一個隨機整數
int.flatMap(x =>
//ints(x)生成一個長度為x的list
ints(x).map(xs =>
//list中的每個元素變換為除以y的余數
xs.map(_ % y))))
for推導語句：
val ns: Rand[List[Int]] = for {
x <- int
y <- int
xs <- ints(x)
} yield xs.map(_ % y)
類似Haskell的Do語句
for推導使得書寫風格更加命令式、更加易懂
Avocado(為Java中實現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);
經典問題：
實現一個對糖果售貨機建模的有限狀態機。機器有兩種輸入方式：可以投入硬幣，或可以按動按鈕獲取糖果。它可以有一種或兩種狀態：鎖定或非鎖定。它也可以跟蹤還剩多少糖果以及有多少硬幣。
機器遵循下面的規則：
對一個鎖定狀態的售貨機投入一枚硬幣，如果有剩余的糖果它將變為非鎖定狀態。
對一個非鎖定狀態的售貨機按下按鈕，它將給出糖果并變回鎖定狀態。
對一個鎖定狀態的售貨機按下按鈕或對非鎖定狀態的售貨機投入硬幣，什么也不做。
售貨機在“輸出”糖果時忽略所有“輸入”
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)
}
本章知識點：
惰性求值
函數式狀態
To be continued
