泛函编程(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 条评论
登录 后参与评论

相关文章

来自专栏liulun

Nim教程【八】

有序类型 值连续的枚举类型、整型、字符类型、布尔类型(还有这些类型的变种), 都可以称之为有序类型,Nim为有序类型提供了一系列特殊的方法 方法签名 方法...

2156
来自专栏Young Dreamer

正则学习笔记——重复、贪婪与懒惰

1.贪婪与懒惰 贪婪与懒惰的适用情况是针对重复的情况; 重复的限定符: * 重复>=0次 + 重复>=1次 ? 重复0或1次 {n} 重复n次...

1986
来自专栏不想当开发的产品不是好测试

nodejs 语法学习(持续更新)

合并objects var o1 = { a: 1 }; var o2 = { b: 2 }; var o3 = { c: 3 }; var obj = Ob...

24310
来自专栏企鹅号快讯

Python数据结构

所属系列:【Python工程师系列】 所属主题:【Python零基础】 1 ? 编码格式建议 不用Tab缩进,用4倍空格缩进 必要时换行(避免单行超出79个字符...

2190
来自专栏mukekeheart的iOS之旅

OC学习2——C语言特性之函数

1、OC是在C语言的基础上进行扩展的,在OC中直接用C语言进行coding也是可以通过编译的。因此,函数定义的语法格式如下: 函数返回值类型 函数名(形参列表...

3237
来自专栏抠抠空间

函数 (二) 名称空间与作用域

一、什么是名称空间 我们写一段代码,里面肯定会定义一些变量名,函数名,而一旦我们运行代码,python解释器在加载这些代码的时候,会在内存中开辟一片空间专门用来...

34610
来自专栏C/C++基础

C/C++结构体初始化与赋值

结构体是常用的自定义构造类型,是一种很常见的数据打包方法。结构体对象的初始化有多种方式,分为指定初始化、顺序初始化、构造函数初始化。假如有如下结构体。

2172
来自专栏老司机的技术博客

人人都能学会的python编程教程5:循环-2

比如我们要从一个列表中找到某个特定元素,那么只要找到了这次循环就可以停止了,没有必要非得走到最后。

4308
来自专栏aCloudDeveloper

经典排序之 归并排序

Author: bakari  Date: 2012.7.30 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之...

1979
来自专栏LEo的网络日志

python技巧分享(十二)

1447

扫码关注云+社区

领取腾讯云代金券