函数范式入门(惰性求值与函数式状态)

摘要：纯函数式状态随机数生成器很明显，原有的函数不是引用透明的，这意味着它难以被测试组合并行化。售货机在输出糖果时忽略所有输入本章知识点惰性求值函数式状态

在下面的代码中我们对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() {...}
    ...
}

</>复制代码 
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()
    }
}

</>复制代码 
共递归有时也称为守护递归，生产能力有时也称为共结束

函数式编程的主题之一便是关注分离，希望能将计算的描述和实际运行分开。比如

一等函数：函数体内的逻辑只有在接收到参数的时候才执行

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

本章知识点：

惰性求值

函数式状态