泛函编程(17)-泛函状态-State In Action

    对OOP编程人员来说,泛函状态State是一种全新的数据类型。我们在上节做了些介绍,在这节我们讨论一下State类型的应用:用一个具体的例子来示范如何使用State类型。以下是这个例子的具体描述:

模拟一个自动糖果贩售机逻辑:贩售机有两种操作方法:投入硬币和扭动出糖旋钮。贩售机可以处于锁定和放开两种状态。模拟运作跟踪贩售机内当前的糖果和硬币数量。贩售机的操作逻辑要求如下:

1、如果机内有糖的话,投入硬币贩售机从锁定状态进入放开状态

2、在放开状态下扭动旋钮贩售机放出一块糖果后自动进入锁定状态

3、在锁定状态下扭动旋钮贩售机不做反应

4、在放开状态下投入硬币贩售机不做反应

5、没有糖果的贩售机对任何操作都不做反应

我们先把涉及到的数据类型设计出来:

1   type candy = Int    //方便表达
2   type coin = Int     //方便表达
3   sealed trait Input
4   case object Coin extends Input  //投币
5   case object Turn extends Input  //旋钮
6   case class Machine(locked: Boolean, candies: candy, coins: coin) //状态类

Machine类型就是需要变迁的状态,状态内容包括锁定状态locked,当前糖果数candies,当前硬币数coins。

我们的模拟函数款式如下:

1  def simulateMachine(inputs: List[Input]): State[Machine,coin]

输入一个操作动作List,返回State实例,值是当前硬币数,状态是Machine,里面包括了完成操作后的锁定状态、硬币数、糖果数。

我们先做一个比较直接容易明白的版本。首先是贩售机互动逻辑部分:这部分模拟了操作互动流程并在运行过程中对状态进行变迁,最终以输出形式返回最新状态:

1       def transition(input: Input, machine: Machine): Machine = {
2           (input, machine) match {
3             case (_, Machine(_,0,_)) => machine
4             case (Turn, Machine(true,_,_)) => machine
5             case (Coin, Machine(false,_,_)) => machine
6               case (Coin, Machine(true, _, nCoin)) => machine.copy(locked = false, coins = nCoin + 1)
7               case (Turn, Machine(false, nCandy, _))  => machine.copy(locked = true, candies = nCandy - 1)
8           }
9       }

这个transition函数采用了泛函状态维护风格:传入一个状态;返回新状态。流程逻辑部分是通过分析操作动作及贩售机当前状态来决定如何更新状态;一切按照设计方案要求进行。状态machine是个case class实例,这样我们可以使用machine.copy来复制一个新的状态,内容包括locked,candies,coins、又或者在某些情况下,原封不动地返回传入的状态。很明显,transition就是我们需要的状态行为函数,只要嵌入一个State实例就可以随时实现状态变迁了。

transition只能处理单个操作动作,那么如果我们输入一个List的操作动作该如何连续处理呢?既然涉及List,自然想到用递归算法应该能行:

1       def execute(inputs: List[Input], machine: Machine): Machine = {
2           inputs match {
3               case Nil => machine
4               case h::t => execute(t, transition(h,machine))
5               
6           }
7       }

在execute函数里我们对List里每个操作元素进行transition运算,状态machine也在一连串的transition运算中自动更新了。有了这两个函数我们就很容易推断出整体流程了:获取初始状态 >>> 以此初始状态输入操作处理流程并把最终结果设定为当前状态 >>> 读取当前状态:

1       for {
2           s0 <- getState    //读取起始状态
3           _ <- setState(execute(inputs,s0))  //人工设定新状态
4           s1 <- getState    //读取当前状态
5       } yield s1.coins

整个大流程还是比较容易理解的。我们注意到状态变迁采用了临时手工设定方式 setState。整个程序代码和运行结果示范如下:

 1  type candy = Int    //方便表达
 2   type coin = Int     //方便表达
 3   sealed trait Input
 4   case object Coin extends Input
 5   case object Turn extends Input
 6   case class Machine(locked: Boolean, candies: candy, coins: coin)
 7   
 8   def simulateMachine(inputs: List[Input]): State[Machine,coin] = {
 9       def transition(input: Input, machine: Machine): Machine = {
10           (input, machine) match {
11             case (_, Machine(_,0,_)) => machine
12             case (Turn, Machine(true,_,_)) => machine
13             case (Coin, Machine(false,_,_)) => machine
14               case (Coin, Machine(true, _, nCoin)) => machine.copy(locked = false, coins = nCoin + 1)
15               case (Turn, Machine(false, nCandy, _))  => machine.copy(locked = true, candies = nCandy - 1)
16           }
17       }
18        def execute(inputs: List[Input], machine: Machine): Machine = {
19           inputs match {
20               case Nil => machine
21               case h::t => execute(t, transition(h,machine))
22               
23           }
24       }
25       for {
26           s0 <- getState    //读取起始状态
27           _ <- setState(execute(inputs,s0))  //人工设定新状态
28           s1 <- getState    //读取当前状态
29       } yield s1.coins
30   }                                               //> simulateMachine: (inputs: List[ch6.state.Input])ch6.state.State[ch6.state.M
31                                                   //| achine,ch6.state.coin]
32 
33 val inputs = List(Coin, Turn, Coin, Turn, Turn, Coin, Coin, Coin, Turn)
34                                                   //> inputs  : List[Product with Serializable with ch6.state.Input] = List(Coin,
35                                                   //|  Turn, Coin, Turn, Turn, Coin, Coin, Coin, Turn)
36 simulateMachine(inputs).run(Machine(true,3,0))    //> res0: (ch6.state.coin, ch6.state.Machine) = (3,Machine(true,0,3))
37  

以上这段代码考虑到了OOP编程人员的思维模式,采用了分段表达方式使整个程序变得更容易理解。对比起来,下面的例子就可以说是真正的泛函编程风格了。同样针对以上的贩售机模拟逻辑要求,我们将用典型的泛函风格来编程。我们先看看下面两个函数:

 1     def modify[S](f: S => S): State[S,Unit] = {
 2       for {
 3             s0 <- getState
 4             _ <- setState(f(s0))
 5         } yield ()
 6     }
 7     def sequence[S,A](xs: List[State[S,A]]): State[S,List[A]] = {
 8         def go(s: S, actList: List[State[S,A]], acc: List[A]): (List[A],S) = {
 9             actList match {
10                     case Nil => (acc.reverse, s)  //纠正排序
11                     case h::t => h.run(s) match {case (a2,s2) => go(s2,t,a2 :: acc) }
12             }
13         }
14         State(s => go(s,xs,List()))
15     }

modify比较直白:取出当前状态,对这个状态进行变迁后再设成当前状态。sequence稍微复杂一点。我们先从它的类型匹配开始分析:接收一个List[State]、输出State[List],换句话说就是把一连串的状态变成一个状态内的一连串值。这不刚好和我们模拟函数要求匹配吗?我们要求一个函数对一连串的操作动作进行处理后产生一个最终的状态。sequence函数内部已经包含了处理循环,我们不需要execute函数了。但是这个版本的sequence函数比较低级:我是指它使用了递归算法,必须在函数内部实现状态行为run(s)。如果我们用高价一点的函数实现sequence,有可能不需要理会run(s)了:

1     //用右折叠:输入与输出同排序,但不是tail recursive
2     def sequenceByRight[S,A](xs: List[State[S,A]]): State[S,List[A]] = {
3         xs.foldRight(unit[S,List[A]](List())){ (f,acc) => f.map2(acc)(_ :: _) }
4     }
5     //用左折叠:输入与输出反排序,是tail recursive
6         def sequenceByLeft[S,A](l: List[State[S, A]]): State[S, List[A]] = { 
7           l.reverse.foldLeft(unit[S, List[A]](List()))((acc, f) => f.map2(acc)( _ :: _ ))
8         }

无论用左右折叠算法都可以实现sequence功能。注意:我们没有使用run(s),因为这个东西是在flatMap里,而map2是用flatMap实现的。用这种高阶函数使程序更加简洁。

 1 def simulateMachineFP(inputs: List[Input]): State[Machine,coin] = {
 2   for {
 3     _ <- sequence{
 4         inputs.map {
 5             input => modify {
 6                 machine: Machine => {
 7                     (input, machine) match {
 8                             case (_, Machine(_,0,_)) => machine
 9                             case (Turn, Machine(true,_,_)) => machine
10                              case (Coin, Machine(false,_,_)) => machine
11                           case (Coin, Machine(true, nCandy, nCoin)) => Machine(false,nCandy, nCoin+1)  
12                           case (Turn, Machine(false, nCandy, nCoin))  => Machine(true, nCandy - 1, nCoin) 
13                     }
14                 }
15               }
16         }
17          }
18     s <- getState
19    } yield s.coins
20 }                                                 //> simulateMachineFP: (inputs: List[ch6.state.Input])ch6.state.State[ch6.state
21                                                   //| .Machine,ch6.state.coin]
22 simulateMachineFP(inputs).run(Machine(true,3,0))  //> res1: (ch6.state.coin, ch6.state.Machine) = (3,Machine(true,0,3))

哇,有点过了!不过这里的确没有分段编码,一口气用sequence完成了编程。那我们还是来分析一下:sequence需要接收一个参数类型是:List[State[S,A]] 我们有一个List[Input],需要把这个List[Input] 变成 List[State[S,A]],很明显,我们需要用map来做这个转换 List[Input].map{ Input => State[S,A]}。modify返回类型State[S,Unit],所以我们用了input => modify,这在类型上是匹配的。modify,顾名思义就是更新状态,我们把状态变迁逻辑都放到了modify函数里,它的返回结果就是最终的状态。

_ <- sequence ...modify 起到了 _ <- setState 的作用,所以我们可以用 s <- getState 把最新的状态读出来。

在以上这个例子里我们采用了泛函编程风格:用类型匹配方式进行了函数组合,虽然说代码可能简单了,但清洁可能就说不上了。需要用类型匹配(type line-up)来分析理解,也就是要再熟悉多点泛函编程思考模式。

后面补充一下:如果我来选择,我会稍退一步;把逻辑部分提出来:

 1 def simulateMachineConcise(inputs: List[Input]): State[Machine,coin] = {
 2       def transition(input: Input, machine: Machine): Machine = {
 3           (input, machine) match {
 4             case (_, Machine(_,0,_)) => machine
 5             case (Turn, Machine(true,_,_)) => machine
 6             case (Coin, Machine(false,_,_)) => machine
 7               case (Coin, Machine(true, nCandy, nCoin)) => Machine(false,nCandy, nCoin+1)  
 8               case (Turn, Machine(false, nCandy, nCoin))  => Machine(true, nCandy - 1, nCoin) 
 9           }
10       }
11 
12   for {
13         _ <- sequence{inputs.map {input => modify {machine: Machine => transition(input, machine)}}}                   s <- getState
15       } yield s.coins
16 }                                                 //> simulateMachineConcise: (inputs: List[ch6.state.Input])ch6.state.State[ch6.
17                                                   //| state.Machine,ch6.state.coin]
18 simulateMachineConcise(inputs).run(Machine(true,3,0))
19                                                   //> res2: (ch6.state.coin, ch6.state.Machine) = (3,Machine(true,0,3))
20  

这段核心代码是不是简洁多了,也比较容易理解:

1   for {
2     _ <- sequence{inputs.map {input => modify {machine: Machine => transition(input, machine)}}}                              s <- getState
3       } yield s.coins

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏刘望舒

几条曲线构建Android表白程序

每年的情人节和七夕,甜蜜与痛苦的日子,做点什么好呢? 写诗画画送礼物,逛街吃饭看电影? 作为搬砖爱好者,写个表白脚本或者动画什么的吧。 想起之前看到的一段H5动...

653
来自专栏PPV课数据科学社区

《用地图说话》之:十字绣中国热力数据地图

作图思路: 准备一块300*300小单元格组成的区域,对照地图图形,在每个省图形范围内的单元格填入该省的数据,然后对这些单元格应用条件格式->色阶,就形成了一幅...

2753
来自专栏java 成神之路

HashMap实现中文分词器

3317
来自专栏数据小魔方

R语言可视化——图表嵌套(母子图)

之前在学习ggplot的时候,一直存在着一个困惑。 就是这个函数是否允许两个做出来的两个相关图表重叠嵌套(也就是在一个大图(主图)的边缘位置,放置另一个缩小版的...

1884
来自专栏数据科学与人工智能

【Python环境】可爱的 Python: 自然语言工具包入门

鄙人并非见多识广,虽然写过很多关于 文本处理 方面的东西(例如,一本书),但是,对我来说, 语言处理(linguistic processing) 是一个相对新...

2918
来自专栏听雨堂

地图校正方法心得

如果想校正两张比例,坐标系,时间都不同的电子地图,简直太难了,大概辛苦了一周时间,才有点心得: 1、选择公共点时,河流、公路、高程、等高线均不能选,大的固定...

1895
来自专栏CDA数据分析师

教你掌握Excel中最为重要的逻辑 ——「链接」(一)

如果把Excel比作武侠小说中的“剑”,那么按照武侠小说中御“剑”能力的高低程度可以大致将剑客分为以下几个等级: Level 1(剑客):小说中常见的劫匪甲乙...

1917
来自专栏hightopo

原 HT for Web中3D流动效果的实

1493
来自专栏北京马哥教育

黑科技 | 用Python只花十五分钟完成正则表达式五天任务量

数据清理是很多机器学习任务上我们遇到的首要问题。本文介绍的 FastText 是一个开源 Python 库,可用于快速进行大规模语料库的文本搜索与替换。该项目的...

3299
来自专栏人工智能

手把手带你用机器学习写unity AI

2017unity机器学习社区挑战赛参加地址:https://connect.unity.com/challenges/ml-agents-1 打开下载的uni...

2097

扫码关注云+社区