纯函数式状态（2）

在上一个章节中我们完成如下组合子：unit，map，map2，flatMap，sequence和traverse。这些组合子并不是为处理随机状态而存在的。他们都是处理状态的通用函数，不仅仅可以处理随机状态，也可以处理其他的状态。例如我们可以给map换一个方法签名：

  def map[A, B, S](fa: S => (A, S))(f: A => B): S => (B, S) =
    s => {
      val (a, s1) = fa(s)
      (f(a), s1)
    }

State也可以换成一个更加通用的函数签名：

type State[S, +A] = S => (A, S)

这里将State定义成case class会更加方便操作，代码如下：

package org.fp.scala.state

case class State[S, +A](run: S => (A, S)) {

}

有了State之后我们可以重写使用类型别名来定义Rand:

  type Rand[+A] = State[RNG, A]

好了既然我们已经定义了一种更加通用的状态行为数据结构，那么我们为这个数据结构添加unit，map，map2，flatMap，sequence和Traverse等组合子：

package org.fp.scala.state

case class State[S, +A](run: S => (A, S)) {
  import State._

  def map[B](f: A => B): State[S, B] =
    State {s =>
      val (a, s1) = run(s)
      (f(a), s1)
    }

  def map2[B, C](sb: State[S, B])(f: (A, B) => C): State[S, C] =
    State { s =>
      val (a, s1) = run(s)
      val (b, s2) = sb.run(s1)
      (f(a, b), s2)
    }

  def flatMap[B](f: A => State[S, B]): State[S, B] =
    State { s =>
      val (a, s1) = run(s)
      f(a).run(s1)
    }

  def map_1[B](f: A => B): State[S, B] =
    flatMap(a => unit(f(a)))
  
  def map2_1[B, C](sb: State[S, B])(f: (A, B) => C): State[S, C] =
    flatMap { a =>
      sb.map { b =>
        f(a, b)
      }
    }
}

object State {

  type Rand[+A] = State[RNG, A]

  def unit[S, A](a: A): State[S, A] =
    State((a, _))

  def sequence[S, A](li: List[State[S, A]]): State[S, List[A]] =
    li match {
      case Nil => unit(Nil)
      case h :: t => h.map2(sequence(li))(_ :: _)
    }

  def sequence1[S, A](li: List[State[S, A]]): State[S, List[A]] =
    li.foldRight(unit(Nil): State[S, List[A]])((a, b) => a.map2(b)(_ :: _))
  
  def sequence2[S, A](li: List[State[S, A]]): State[S, List[A]] =
    traverse(li)(x => x)

  def traverse[S, A, B](li: List[A])(f: A => State[S, B]): State[S, List[B]] =
    li match {
      case Nil => unit(Nil)
      case h :: t => f(h).map2(traverse(t)(f))(_ :: _)
    }

  def traverse1[S, A, B](li: List[A])(f: A => State[S, B]): State[S, List[B]] =
    li.foldRight(unit(Nil): State[S, List[B]])((a, b) => f(a).map2(b)(_ :: _))
  
}

有了State和上面这些组合子之后，我们可以尝试纯函数式命令编程了。所谓命令式编程指的是程序是由一串串指令（statement）组成的，每个指令都可以修改程序的状态。在函数式编程中，指令是一个状态行为（state action），他是一个真正的函数，他接收一个状态，产生值和下一个状态。还记得前面章节介绍的for表达式么？也就是flatMap和map的语法糖。利用for表达式我们可以更加清晰的描述命令式编程，想一想我们如何来修改State中的状态，在命令式的代码中我们通常通过set和get来修改一个对象或者程序的状态。那么对于State同样也是这样处理的，我们可通过set写入一个状态，然后通过modify修改状态，最后再通过get获取修改后的状态。来看下代码：

  def set[S](s: S): State[S, Unit] =
    State(_ => ((), s))

  def get[S]: State[S, S] =
    State(s => (s, s))

  def modify[S](f: S => S): State[S, Unit] =
    for {
      s <- get
      _ <- set(f(s))
    } yield ()

为了加强对State的使用经验，实现一个对糖果售货机建模的有限状态机。机器有两种输入模式，一种式投入硬币；另一种式按动按钮获取糖果。他可以有一种或两种状态：锁定和非锁定。它也可以跟踪还剩多少糖果以及多少硬币。

package org.fp.scala.state

trait Input

case object Coin extends Input

case object Turn extends Input

case class Machine(lock: Boolean, candies: Int, coins: Int)

机器遵循下面的规则：

对于一个锁定状态的糖果机投入一枚硬币，如果有糖果，他将变为非锁定状态
对于一个非锁定状态的糖果机按下按钮，他将返回糖果并返回锁定状态
对于一个锁定状态的糖果机按下按钮或者一个非锁定状态的糖果机投入硬币，则什么也不做
糖果机在输出糖果时忽略所有的输入
simulateMachine方法根据输入列表返回硬币数和糖果机里最终剩余的糖果数。

下面来分析下如何处理这个问题：方法的输入是List[Input]，方法的返回值是State[Machine, (Int, Int)]，其中(Int, Int)为当前Machine中的糖果数和硬币数，可以表示为(machine.condies, machine.coins)。List[Input]需要转化成List[State[Machine, Unit]], 已知(Input, Machine) => Machine，那么可以通过modify可以将input转化成State[Machine, Unit]，加map就可以将List[Input]转化成List[State[Machine, Unit]]。而在之前的组合子中，sequence可以将List[State[Machine, Unit]]转换成State[Machine, List[Unit]]。最后我们只需要通过get获取machine最后的状态并map成(machine.condies, machine.coins)。类型变化如下：

(Input, Machine) => Machine
Input => Machine => State[Machine, Unit]
List[Input] => List[State[Machine, Unit]]
List[State[Machine, Unit]] => State[Machine, List[Unit]]
State[Machine, List[Unit]] => State[Machine, (Int, Int)]

全部代码如下：

package org.fp.scala.state

trait Input

case object Coin extends Input

case object Turn extends Input

case class Machine(lock: Boolean, candies: Int, coins: Int)

object Machine {

  import State._

  def simulateMachine(inputs: List[Input]): State[Machine, (Int, Int)] = {
    val li = sequence(inputs.map(i => modify(s => calculate(i, s))))
    for {
      _ <- li
      s <- get
    } yield (s.candies, s.coins)
  }

  // 对于一个锁定状态的糖果机投入一枚硬币，如果有糖果，他将变为非锁定状态
  // 对于一个非锁定状态的糖果机按下按钮，他将返回糖果并返回锁定状态
  // 对于一个锁定状态的糖果机按下按钮或者一个非锁定状态的糖果机投入硬币，则什么也不做
  // 糖果机在输出糖果时忽略所有的输入
  def calculate(input: Input, machine: Machine): Machine =
    (input, machine) match {
      case (_, Machine(_, 0, _)) => machine
      case (Turn, Machine(true, _, _)) => machine
      case (Coin, Machine(false, _, _)) => machine
      case (Coin, Machine(true, candies, coins)) => Machine(false, candies, coins + 1)
      case (Turn, Machine(false, candies, coins)) => Machine(true, candies - 1, coins)
    }


  def main(args: Array[String]): Unit = {
    val inputs = List(Coin, Turn, Coin, Turn, Turn, Coin, Coin, Coin, Turn)
    val res = simulateMachine(inputs).run(Machine(true, 3, 0))
    print("res: " + res)
  }
}

写到这里我们知道写好纯函数式程序的诀窍：写一个函数接受一个状态，然后返回一个新的状态。利用组合子将可以避免显示传递和修改状态。下面我们将开启新的篇章。