Scalaz(28)- ST Monad :FP方式适用变量

    函数式编程模式强调纯代码(pure code),主要实现方式是使用不可变数据结构,目的是函数组合(composability)最终实现函数组件的重复使用。但是,如果我们在一个函数p内部使用了可变量(mutable variables),如果函数的输入参数e是纯代码,那么表达式p(e)同样是纯代码的,因为函数的调用者是无法接触到函数内部申明的这些可变量的。不过,这样的做法会造成函数的臃肿代码,因为在函数内部是无法实现函数组合的,无法重复使用函数组件,实际上又违背了FP的宗旨。Scalaz提供了专门解决可变量使用问题的方法,能保证即使在并行运算的环境内各线程无法影响相互间的可变量,即ST Monad。

Scalaz的可变量分两种:一个内存地址STRef或一个可变数组STArray。我们先看看它们在源代码中的定义:effect/ST.scala

/**Mutable variable in state thread S containing a value of type A. [[http://research.microsoft.com/en-us/um/people/simonpj/papers/lazy-functional-state-threads.ps.Z]] */
sealed trait STRef[S, A] {
  protected var value: A

  /**Reads the value pointed at by this reference. */
  def read: ST[S, A] = returnST(value)

  /**Modifies the value at this reference with the given function. */
  def mod[B](f: A => A): ST[S, STRef[S, A]] = st((s: Tower[S]) => {
    value = f(value);
    (s, this)
  })

  /**Associates this reference with the given value. */
  def write(a: => A): ST[S, STRef[S, A]] = st((s: Tower[S]) => {
    value = a;
    (s, this)
  })

  /**Synonym for write*/
  def |=(a: => A): ST[S, STRef[S, A]] =
    write(a)

  /**Swap the value at this reference with the value at another. */
  def swap(that: STRef[S, A]): ST[S, Unit] = for {
    v1 <- this.read
    v2 <- that.read
    _ <- this write v2
    _ <- that write v1
  } yield ()
}
...
/**Mutable array in state thread S containing values of type A. */
sealed trait STArray[S, A] {
  def size: Int
  def z: A
  implicit def manifest: Manifest[A]

  private lazy val value: Array[A] = Array.fill(size)(z)

  import ST._

  /**Reads the value at the given index. */
  def read(i: Int): ST[S, A] = returnST(value(i))

  /**Writes the given value to the array, at the given offset. */
  def write(i: Int, a: A): ST[S, STArray[S, A]] = st(s => {
    value(i) = a;
    (s, this)
  })

  /**Turns a mutable array into an immutable one which is safe to return. */
  def freeze: ST[S, ImmutableArray[A]] = st(s => (s, ImmutableArray.fromArray(value)))

  /**Fill this array from the given association list. */
  def fill[B](f: (A, B) => A, xs: Traversable[(Int, B)]): ST[S, Unit] = xs match {
    case Nil             => returnST(())
    case ((i, v) :: ivs) => for {
      _ <- update(f, i, v)
      _ <- fill(f, ivs)
    } yield ()
  }

  /**Combine the given value with the value at the given index, using the given function. */
  def update[B](f: (A, B) => A, i: Int, v: B) = for {
    x <- read(i)
    _ <- write(i, f(x, v))
  } yield ()
}

我们看到STRef和STArray都定义了write,mod,update这样有副作用的操作函数,它们都返回了ST[S,STRef[S,A]]类型的结果。ST是个Monad,我们可以从源代码中证实: 

/**
 * Purely functional mutable state threads.
 * Based on JL and SPJ's paper "Lazy Functional State Threads"
 */
sealed trait ST[S, A] {
  private[effect] def apply(s: Tower[S]): (Tower[S], A)

  import ST._

  def flatMap[B](g: A => ST[S, B]): ST[S, B] =
    st(s => apply(s) match {
      case (ns, a) => g(a)(ns)
    })

  def map[B](g: A => B): ST[S, B] =
    st(s => apply(s) match {
      case (ns, a) => (ns, g(a))
    })
}

ST与State Monad极其相似,备有map和flatMap,所以是个Monad,能支持for-comprehension。我们可以通过ST的for-comprehension实现STRef,STArray操作函数的组合,因为这些操作函数的返回结果都是ST类型的。但write,mod这些操作函数有个共同的奇怪现象:它们都没有调用过S类型的值,直接按传入就输出去了。这正是ST Monad如何命名的:ST又可以被称为State Tag,也就是说每一项操作都有独立的状态类型S,如果S类型有所不同的话是无法调用操作函数的。而for-comprehension是一种串型流程,能保证线程之间不会交叉运行,相互影响各自的可变量。ST Monad与State Monad最大的不同是它没有run方法,也就是我们无法用ST的内部方法来获取ST[S,A]的A值。我们先看看STRef和STArray的一些用例:

 1 import scalaz._
 2 import Scalaz._
 3 import effect._
 4 import ST._
 5 object st {
 6 def e1[S] = for {
 7   r <- newVar[S](3)
 8   x <- r.mod {_ + 2}
 9 } yield x                                         //> e1: [S]=> scalaz.effect.ST[S,scalaz.effect.STRef[S,Int]]
10 
11 def e2[S] = for {
12   r <- newVar[S](3)
13   x <- r.mod {_ + 2}
14   y <- x.read
15 } yield y                                         //> e2: [S]=> scalaz.effect.ST[S,Int]
16 
17 def e3[S] = for {
18   arr <- newArr[S,Int](5,0)
19   _ <- arr.write(0,3)
20   _ <- arr.write(1,2)
21   _ <- arr.update ((a: Int,b: Int) => a + b, 2, 4)
22   r <- arr.freeze
23 } yield r                                         //> e3: [S]=> scalaz.effect.ST[S,scalaz.ImmutableArray[Int]]

newVar[S](3)以状态S新建一个Int存放地址并存入值3。mod操作返回ST[S,STRef[S,Int]],返回的是个地址(reference),而read返回的是ST[S,Int],则是个值。首先注意e1[S],e2[S],e3[S]它们都附带了独立状态标签S。

现在我们需要从ST Monad里把运算结果取出来。从上面的分析我们可能面对两种方式:ST[S,A], ST[S,STRef[S,A]]。从ST[S,A]里取出的是一个A类型的值,而从ST[S,STRef[S,A]]里取出的是个内存地址。可以预见,如果我们通过某些方式能获取一个内存地址的话,就有可能在函数体外对地址内的值进行修改,也就造成了副作用的产生。Scalaz的解决方法是通过高阶类参数多态(2nd-rank parameteric polymorphism),利用编译器(compiler)对ST[S,STRef[S,A]]这样的读取操作进行拒绝编译。下面我们看看示范结果:

1 runST(new Forall[({type l[x] = ST[x, Int]})#l]{def apply[S] = e2[S]})
2                                                   //> res0: Int = 5
3 //runST(new Forall[({type l[x] = ST[x, Int]})#l]{def apply[S] = e1[S]})   
4 //type mismatch;  found   : scalaz.effect.ST[S,scalaz.effect.STRef[S,Int]]  required: scalaz.effect.ST[S,Int]  

e1返回ST[S,STRef[S,A]],表达式new Forall[({type l[x] = ST[x, Int]})#l]{def apply[S] = e1[S]}无法通过编译。在这里Forall是个高阶类参数多态类,定义如下:

/** A universally quantified value */
trait Forall[P[_]] {
  def apply[A]: P[A]
}

我们再重新组织一些上面的代码,使大家可以看的更清楚一点:

1 type ForallST[A] = Forall[({type l[x] = ST[x,A]})#l]
2 runST(new ForallST[Int]{ def apply[S] = e2[S] })  //> res0: Int = 5
3 //runST(new ForallST[Int]{def apply[S] = e1[S]})
4 //type mismatch;  found   : scalaz.effect.ST[S,scalaz.effect.STRef[S,Int]]  required: scalaz.effect.ST[S,Int]

从错误信息可以得出:编译器期待的类型是ST[S,Int], ST[S,STRef[S,Int]]是产生类型错误。利用高阶类参数多态类f,只有new Forall { def apply[A] >>> ST[S,A] }这样的款式才能通过编译。

与State Monad比较,ST Monad并不包含为获取运算值而设的run函数。ST Monad在类型外定义了读取运算值的函数runST。

runST方法的定义如下:

  /**Run a state thread */
  def runST[A](f: Forall[({type λ[S] = ST[S, A]})#λ]): A =
    f.apply.apply(ivoryTower)._2

State Monad获取运算值的方式是这样的:someState.run(svalue),svalue是个S类型值,是状态初始值。我们已经了解到所有的变量操作函数都没有使用S类型值,所以上面的f.apply.apply(ivoryTower)中这个ivoryTower是个没有意义的随意类型值,我们不需要注入任何S值去获取运算结果值。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏炉边夜话

GCC内嵌汇编语言

绝大多数 Linux 程序员以前只接触过DOS/Windows 下的汇编语言,这些汇编代码都是 Intel 风格的。但在 Unix 和 Linux 系统中,更多...

822
来自专栏ShaoYL

Objective-C中的@property和@synthesize用法

35311
来自专栏小樱的经验随笔

浅谈String模块ascii_letters和digits

本文介绍string模块ascii_letters和digits方法,其中ascii_letters是生成所有字母,从a-z和A-Z,digits是生成所有数字...

3407
来自专栏人人都是极客

gcc内嵌汇编详解

有时候我们希望在C/C++代码中使用嵌入式汇编,因为C中没有对应的函数或语法可用。比如我最近在ARM上写FIR程序时,需要对最后的结果进行饱和处理,但gcc没有...

932
来自专栏分布式系统和大数据处理

基于业务对象(列表)的排序

在上一篇文章 基于业务对象的筛选 中,我们讨论了如何实现Predicate<T>(T object)委托,自定义DateFilter 类来对业务对象进行筛选。与...

752
来自专栏Golang语言社区

Go Template学习笔记

快速开始 func handler(w http.ResponseWriter,r *http.Request){ t := templ...

2987
来自专栏项勇

笔记29 | 整理Java的容器类

1794
来自专栏java一日一条

Java 泛型详解

泛型是Java中一个非常重要的知识点,在Java集合类框架中泛型被广泛应用。本文我们将从零开始来看一下Java泛型的设计,将会涉及到通配符处理,以及让人苦恼的类...

615
来自专栏java学习

工程师笔试题1(答案解析)

1.访问修饰符作用范围由大到小是( )。 A.private-protected-default-publicB.public-protected-defaul...

2525
来自专栏Android开发指南

Effecvtive Java Note

2755

扫码关注云+社区