Scala：收集不变状态的更新/更改 [英] Scala: collecting updates/changes of immutable state

问题描述

目前，我正在尝试将一个更具功能性的编程风格应用于涉及低级（LWJGL）GUI开发的项目。显然，在这种情况下，需要携带很多状态，这在当前版本中是可变的。我的目标是最终有一个完全不变的状态，以避免国家的变化作为副作用。我研究了scalaz的镜头和状态monads一段时间，但我的主要关切仍然是：所有这些技术都依赖于写时复制。既然我的国家既有大量的领域，也有一些相当大的领域，我担心的是表现。

I'm currently trying to apply a more functional programming style to a project involving low-level (LWJGL-based) GUI development. Obviously, in such a case it is necessary to carry around a lot of state, which is mutable in the current version. My goal is to eventually have a completely immutable state, in order to avoid state changes as side effect. I studied scalaz's lenses and state monads for awhile, but my main concern remains: All these techniques rely on copy-on-write. Since my state has both a large number of fields and also some fields of considerable size, I'm worried about performance.

据我所知，修改不可变对象的最常见方法是使用复制方法c $ c>案例类（这也是透镜下的镜头）。我的第一个问题是，这个复制方法实际上是如何实现的？我执行了一个类的实验：

To my knowledge the most common approach to modify immutable objects is to use the generated copy method of a case class (this is also what lenses do under the hood). My first question is, how this copy method is actually implemented? I performed a few experiments with a class like:

case class State(
  innocentField: Int, 
  largeMap: Map[Int, Int], 
  largeArray: Array[Int]
)

通过基准测试，通过查看 -Xprof 的输出，它看起来像更新 someState.copy（innocentField = 42）实际上执行深层拷贝，当我增加 largeMap 和 largeArray 的大小时，我观察到显着的性能下降。我以某种方式期望新构造的实例共享原始状态的对象引用，因为内部的引用应该被传递给构造函数。我可以以某种方式强制或禁用默认的复制的深层复制行为？

By benchmarking and also by looking at the output of -Xprof it looks like updating someState.copy(innocentField = 42) actually performs a deep copy and I observe a significant performance drop when I increase the size of largeMap and largeArray. I was somehow expecting that the newly constructed instance shares the object references of the original state, since internally the reference should just get passed to the constructor. Can I somehow force or disable this deep copy behaviour of the default copy?

在思考复制写的问题，我想知道FP是否有更多的一般解决方案，它以一种渐进的方式（在收集更新或收集更改）的意义上存储不可变数据的变化。令我惊讶的是我找不到任何东西，所以我尝试了以下内容：

While pondering on the copy-on-write issue, I was wondering whether there are more general solutions to this problem in FP, which store changes of immutable data in a kind of incremental way (in the sense of "collecting updates" or "gathering changes"). To my surprise I could not find anything, so I tried the following:

// example state with just two fields
trait State {
  def getName: String
  def getX: Int

  def setName(updated: String): State = new CachedState(this) {
    override def getName: String = updated
  }
  def setX(updated: Int): State = new CachedState(this) {
    override def getX: Int = updated
  }

  // convenient modifiers
  def modName(f: String => String) = setName(f(getName))
  def modX(f: Int => Int) = setX(f(getX))

  def build(): State = new BasicState(getName, getX)
}

// actual (full) implementation of State
class BasicState(
  val getName: String, 
  val getX: Int
) extends State


// CachedState delegates all getters to another state
class CachedState(oldState: State) extends State {
  def getName = oldState.getName
  def getX    = oldState.getX
}

现在这样做可以这样做：

Now this allows to do something like this:

var s: State = new BasicState("hello", 42)

// updating single fields does not copy
s = s.setName("world")
s = s.setX(0)

// after a certain number of "wrappings"
// we can extract (i.e. copy) a normal instance
val ns = s.setName("ok").setX(40).modX(_ + 2).build()

我现在的问题是：你对这个设计有什么看法？这是我不知道的某种FP设计模式（除了与Builder模式的相似性）？由于我没有找到类似的东西，我想知道这种方法是否存在一些重大问题？还是有更多的标准方法来解决不写入不变性的复制瓶颈？

My question now is: What do you think of this design? Is this some kind of FP design pattern that I'm not aware of (apart from the similarity to the Builder pattern)? Since I have not found anything similar, I'm wondering if there is some major issue with this approach? Or are there any more standard ways to solve the copy-on-write bottleneck without giving up immutability?

是否有可能统一get / set / mod函数在某些方面？

Is there even a possibility to unify the get/set/mod functions in some way?

编辑：

我假设 copy 执行深层拷贝确实是错误的。

My assumption that copy performs a deep copy was indeed wrong.

推荐答案

这与视图基本相同是一种懒惰的评价;这种类型的策略或多或少是Haskell中的默认值，并且在Scala中使用一个公平的位（参见例如mapValues在地图上，分组在集合上，几乎任何在Iterator或Stream上返回另一个Iterator或Stream等等）。

This is basically the same as views and is a type of lazy evaluation; this type of strategy is more or less the default in Haskell, and is used in Scala a fair bit (see e.g. mapValues on maps, grouped on collections, pretty much anything on Iterator or Stream that returns another Iterator or Stream, etc.). It is a proven strategy to avoid extra work in the right context.

但我认为你的前提有些错误。

But I think your premise is somewhat mistaken.

case class Foo(bar: Int, baz: Map[String,Boolean]) {}
Foo(1,Map("fish"->true)).copy(bar = 2)

实际上不会使地图被深深地复制。它只是设置引用。字节码证明：

does not in fact cause the map to be copied deeply. It just sets references. Proof in bytecode:

62: astore_1
63: iconst_2   // This is bar = 2
64: istore_2
65: aload_1
66: invokevirtual   #72; //Method Foo.copy$default$2:()Lscala/collection/immutable/Map;
69: astore_3   // That was baz
70: aload_1
71: iload_2
72: aload_3
73: invokevirtual   #76; //Method Foo.copy:(ILscala/collection/immutable/Map;)LFoo;

让我们看看那个 copy $ default $ 2 事情：

0:  aload_0
1:  invokevirtual   #50; //Method baz:()Lscala/collection/immutable/Map;
4:  areturn

只需返回地图。

和复制本身？

0:  new #2; //class Foo
3:  dup
4:  iload_1
5:  aload_2
6:  invokespecial   #44; //Method "<init>":(ILscala/collection/immutable/Map;)V
9:  areturn

只需调用常规构造函数。没有克隆的地图。

Just calls the regular constructor. No cloning of the map.

所以当你复制时，你创建一个对象 - 你正在复制的一个新的副本，填写的字段如果你有大量的字段，您的视图将更快（因为您必须创建一个新对象（如果您使用函数应用程序版本，则需要两个），因为您还需要创建函数对象），但它只有一个字段）。否则应该是大致相同的。

So when you copy, you create exactly one object--a new copy of what you're copying, with fields filled in. If you have a large number of fields, your view will be faster (as you have to create one new object (two if you use the function application version, since you need to create the function object also) but it has only one field). Otherwise it should be about the same.

所以，是的，好的想法可能，但是仔细地进行基准测试，以确保在你的情况下是值得的 - 你必须写一个手工编写一些代码，而不是让案例类为您做所有这些。

So, yes, good idea potentially, but benchmark carefully to be sure it's worth it in your case--you have to write a fair bit of code by hand instead of letting the case class do it all for you.

这篇关于Scala：收集不变状态的更新/更改的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！