泛函编程(16)-泛函状态-Functional State

    初接触泛函状态觉着很不习惯。主要是在使用State数据类型时很难理解其中的原理,特别是泛函状态变迁机制(state transition mechanism):怎么状态就起了变化,实在难以跟踪。我想这主要是因为状态变迁机制经过了函数组合,已经深深的埋藏在运行代码后面。上节我们讨论到RNG,对于了解State类型是个很好的开头。RNG简单描述了泛函方式的状态变迁及支持状态变迁所需要的数据结构和操作函数款式。

    在上节我们提到过 type Rand[+A] = RNG => (A, RNG),Rand是一个随意数产生函数。由于Rand是个类型,一个函数类型,所以可以被当作参数或者返回值来使用。我们把这个定义再扩展一下,变得更通用一些:type State[S, +A] = S => (A, S)。Rand就是State的一个特殊案例:type Rand[+A] = State[RNG, +A] 。我们称State为状态行为,即S => (A,S)是一个定义状态变迁方式的函数。State类型的状态变迁机制就是通过状态行为函数来确定的。再次聚焦一下我们设计State类型的目标:State类型不但可以使我们像设计其它类型一样封装一个较低阶类型元素并且提供一套状态变迁机制,而且状态变迁机制是泛函式的,自然隐性的。

我们先试试简单的State类型设计:

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

没错,就是这么简单,也是我刻意为之。注意状态行为函数run是State类的内部成员,我们有针对性的把一个State的状态变迁机制通过在构建State类时作为参数注入。然后产生的State实例就会按照我们期待的那样进行状态变迁了。case class自备了apply,这样我们可以直接使用State(???)创建State实例。我会把State(s => (a,s))写成State { s => (a,s)},这样表达传入的是一段代码会更形象自然一点。State[]既然是一个高阶类型,那么我们应该也为它提供一套在管子内部进行元素操作的函数。切记!切记!在处理管子内封装元素值的同时要按照状态行为函数的要求对类型状态进行相应变迁。

先从高阶类型最基本的组件开始:

1 object State {
2     def unit[S,A](a: A) = State[S,A](s => (a, s))
3 }

我们前面接触过这个unit。它就是一个封装元素值和状态都不转变的State实例。unit的唯一功能就是把低阶一级的封装元素类型a升格为State类型。

我们来编写一个State函数,切记!切记!要同时处理状态变迁机制:

1 case class State[S,+A](run: S => (A, S)) {
2     def flatMap[B](f: A => State[S,B]): State[S,B] = State[S,B] {
3         s => {
4             val (a, s1) = run(s)
5             f(a).run(s1)
6         }
7     }

在flatMap里我们用函数f处理了封装元素a, f(a)。同时我们又引用了状态行为函数run对传入的状态s进行了状态变迁 run(s)。

1     def map[B](f: A => B): State[S,B] = State[S,B] {
2         s => {
3             val (a, s1) = run(s)
4             (f(a),s1)
5         }
6     }
7     def map_1[B](f: A => B): State[S,B] = {
8         flatMap { a => unit(f(a)) }
9     }

同样,map也实施了f(a),run(s)。map也可以用flatMap来实现。它们之间的分别只是f: A => B 和 A => State[S,B]。因为我们有unit, unit(a) = State[S,A],unit(f(a)) = State[S,B]所以我们用unit把map的函数参数A升格就行了。用flatMap来实现map可以把map抽升到更高级:这样map就不用再理会那个状态行为函数了。

那么map2呢?

1     def map2[B,C](sb: State[S,B])(f: (A,B) => C): State[S,C] = {
2         flatMap {a => sb.map { b => f(a,b) }}
3     }
4     def map3[B,C,D](sb: State[S,B], sc: State[S,C])(f: (A,B,C) => D): State[S,D] = {
5         flatMap {a => sb.flatMap {b => sc.map { c => f(a,b,c) }}}
6     }

map2的功能是用封装元素类型函数(A,B) => C来把两个State管子里的元素结合起来。我们可以施用flatMap两次来把两个管子里的元素结合起来。对于map3我们可以再加一次。

另一种连续施用flatMap的表达方式:

 1     def map2_1[B,C](sb: State[S,B])(f: (A,B) => C): State[S,C] ={
 2         for {
 3             a <- this
 4             b <- sb
 5         } yield f(a,b)
 6     }
 7     def map3_1[B,C,D](sb: State[S,B], sc: State[S,C])(f: (A,B,C) => D): State[S,D] ={
 8         for {
 9             a <- this
10             b <- sb
11             c <- sc
12         } yield f(a,b,c)
13     }

以上的语法糖(syntatic sugar)for-comprehension让我们俨然进入了一个泛函世界,好像有了一种兴奋的感觉。这种表达形式简洁直白,更加容易理解。同样,在map2,map3里没有涉及到任何状态变迁的东西。我们实现了状态变迁的隐形操作。

下面举个切实例子来示范泛函状态:

 1 //Stack类型就是一个List[Int],后面比较容易表达点
 2 type Stack = List[Int]
 3 //pop就是一个State实例。它的状态行为函数是partial function:把一个现成的List[Int]拆分成新的值和状态
 4 //即把第一个元素去掉放到值里
 5 def pop = State[Stack, Int]{ case x::xs => (x, xs) }
 6                                                   //> pop: => ch6.state.State[ch6.state.Stack,Int]
 7 //push就是一个State实例。它的状态行为函数把i压到一个现成的List[Int]上,跟值没有任何关系
 8 def push(i: Int) = State[Stack, Unit]{ case xs => ((), i :: xs ) }
 9                                                   //> push: (i: Int)ch6.state.State[ch6.state.Stack,Unit]
10 def stackRun: State[Stack, Int] = {
11     for {
12         _ <- push(13)
13         a <- pop
14         b <- pop
15     } yield a+b
16 }                                                 //> stackRun: => ch6.state.State[ch6.state.Stack,Int]
17 
18 val (a, s) =stackRun.run(List(10,11,12))          //> a  : Int = 23
19                                                   //| s  : ch6.state.Stack = List(11, 12)

在stackRun里我们没有在任何地方提到状态Stack,但看看运行结果(a,s):不但返回值是正确的,而且Stack状态也默默地发生了转变。如果尝试从stackRun的代码里去分析状态是如何转变的是永远无法理解的,建议还是老老实实从头来吧。

泛函状态是一种隐形自动的变迁,那么如果我们需要打乱既定流程,手动设定或者临时读取状态时该怎么办呢?

1 object State {
2     def unit[S,A](a: A) = State[S,A](s => (a, s))
3     def getState[S]: State[S,S] = State[S,S] { s => (s,s) }
4   def setState[S](s: S): State[S,Unit] = State[S,Unit] { _ => ((),s)}
5     
6 }

还是通过状态行为函数来实现的。

 1 def stackRun: State[Stack, Int] = {
 2     for {
 3         _ <- push(13)
 4         a <- pop
 5         _ <- setState(List(8,9))
 6         b <- pop
 7         s1 <- getState
 8     } yield (a + b)
 9 }                                                 //> stackRun: => ch6.state.State[ch6.state.Stack,Int]
10 
11 val (a, s) =stackRun.run(List(10,11,12))          //> a  : Int = 21
12                                                   //| s  : ch6.state.Stack = List(9)

我们可以临时将状态设置成List(8,9)。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Kirito的技术分享

从Spring Session源码看Session机制的实现细节

去年我曾经写过几篇和 Spring Session 相关的文章,从一个未接触过 Spring Session 的初学者视角介绍了 Spring Session ...

51812
来自专栏码农阿宇

一种关于缓存数据何时更新的解决思路

为什么写? 和大家一样,我有每天逛逛博客园的习惯,今天在博客园看到了“一只攻城狮”写的《初遇 Asp.net MVC 数据库依赖缓存那些事儿》。该朋友利用.Ne...

4126
来自专栏小程序·云开发专栏

解剖小程序的 setData

原文链接:https://godbasin.github.io/2018/10/05/wxapp-set-data/

1913
来自专栏difcareer的技术笔记

Android智能指针

网上已经有很多分析智能指针的文章了,讲得不错的是:Android系统的智能指针(轻量级指针、强指针和弱指针)的实现原理分析。本文尽量从不分析代码的角度,将And...

594
来自专栏python爬虫日记

python 下字符串格式时间比较

python 下有多个有关时间的模块,分别是time、datetime、calendar,今天重点讨论下time写法。

722
来自专栏Java技术交流群809340374

史上最全Java面试266题:算法+缓存+TCP+JVM+搜索+分布式+数据库

以上是总结出的最全Java面试题目,以下是最新总结出的BAT面试java必考题目和答案。

450
来自专栏Java学习网

Java面试题系列之基础部分(六)——每天学5个问题

Java基础部分学习的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语法,集合的语法,io的语法,虚拟机方面的语法,这些都是最基...

2385
来自专栏散尽浮华

事故记录:php-cgi进程过多导致系统资源耗尽

事故现象: 机房一台服务器运行一段时间后,突然发现系统资源即将被耗尽! 1)top命令查看一下系统的cpu ram swap的使用情况 ? 由上图分析,可以看出...

1985
来自专栏ImportSource

厕读:每日一题,面试无忧

2. 下面关于java.lang.Exception类的说法正确的是() A 继承自Throwable B Serialable CD 不记...

3425
来自专栏Java技术

关于Java代码优化的N条建议!

本文是作者:五月的仓颉 结合自己的工作和平时学习的体验重新谈一下为什么要进行代码优化。在修改之前,作者的说法是这样的:

812

扫码关注云+社区