纯度,参考透明度和国家Monad

Question

我目前正在设计一种数值算法,作为其操作的一部分,需要doubles多次更新矢量.由于算法必须尽可能节省空间和时间,因此我不想对传统类型的FP代码进行编码,这些FP代码在每次操作后都会在引擎盖下创建许多版本的数据结构.我也不想创建可变数据结构并使它们全局可用.因此,我决定使用可变数据结构,但随后选择在Statemonad中执行可变操作.由于这是我第一次使用Statemonad,我想确认我是否拥有

1. 保留了参考透明度
2. 保持功能纯度

该update函数转换数据结构状态.由于破坏性更新已本地化在此函数中,并且无法从外部获取数据结构的句柄,因此我认为此函数是纯粹且引用透明的.

def update(i : Int,d : Double) = State[ArraySeq[Double], Unit]{
  case xs: ArraySeq[Double] => {xs(i) = d; (xs, ())}
}

该app函数是一个玩具函数,它将使用一系列doubles并修改它的状态:

def app : State[ArraySeq[Double], Unit] = for{
    _ <- update(0, 3.142)
  // do a heap of stuff on ArraySeq
}yield()

呼叫:

app(Vector(0.0, 1.0, 2.0, 3.0, 4.0).to[ArraySeq])._1.to[Vector]

结果:

res0: Vector[Double] = Vector(3.142, 1.0, 2.0, 3.0, 4.0)

Answer 1

我想你可以说你update自己是纯粹的,因为它只代表一些突变,但是一旦你运行它所有的赌注都是关闭的:

scala> val xs = List(1.0, 2.0, 3.0).to[ArraySeq]
xs: scala.collection.mutable.ArraySeq[Double] = ArraySeq(1.0, 2.0, 3.0)

scala> update(0, 10).eval(xs)
res0: scalaz.Id.Id[Unit] = ()

scala> xs
res1: scala.collection.mutable.ArraySeq[Double] = ArraySeq(10.0, 2.0, 3.0)

这是一个糟糕的场景,它与纯粹或引用透明相反.

State并不是真的在你的例子中为你买了任何东西 - 事实上你app以一种ArraySeq其他人无法改变的方式打电话.您也可以咬住子弹并在您控制的范围内以通常的方式使用可变数据结构 - 即,app像这样写:

def app(xs: Vector[Double]): Vector[Double] = {
  val arr = xs.to[ArraySeq]
  // Perform all your updates in the usual way
  arr.toVector
}

这实际上是纯粹的和引用透明的,但它也比State版本更诚实.如果我看到一个类型的值State[Foo, Unit],我的假设是这个值代表某种操作,它将一个Foo变为一个新的Foo,而不会改变原始的Foo.这是状态monad的所有状态 - 它提供了一种很好的方法,可以对不可变数据结构进行建模操作,并以类似于变异的方式组合它们.如果你把它与实际的变异混合在一起,你很可能会混淆任何使用你代码的人.

如果你真的想要同时真正的变异和纯度,你可以看看Scalaz的STArray.这是一个非常聪明的解决方案,在像Haskell这样的语言中,这是一种很有意义的方法.我自己的感觉是,它在Scala中几乎总是错误的解决方案.如果你真的需要一个可变数组的性能,只需使用一个本地可变数组,并确保你不会泄漏到外部世界.如果你不需要那种表现(大部分时间你都不需要),可以使用类似的东西State.