不可变数据结构概述

Question

我正在学习Scala，作为一个好学生，我试图遵守所有规则。

其中一条规则是：不可变性！因此，我尝试使用不可变的数据结构和val来编写所有代码，有时这确实很困难。

但今天我想到了一件事：唯一重要的是对象/类不应该有可变状态。我不必强制在不可变风格下编写所有方法，因为这些方法彼此不影响。

我的问题是：我是正确的，还是有任何我没有看到的问题/劣势？ 编辑： aishwarya的代码示例：

def logLikelihood(seq: Iterator[T]): Double = {
  val sequence = seq.toList
  val stateSequence = (0 to order).toList.padTo(sequence.length,order)
  val seqPos = sequence.zipWithIndex

  def probOfSymbAtPos(symb: T, pos: Int) : Double = {
    val state = states(stateSequence(pos))
    M.log(state( seqPos.map( _._1 ).slice(0, pos).takeRight(order), symb))
  }

  val probs = seqPos.map( i => probOfSymbAtPos(i._1,i._2) )

  probs.sum
}  

解释：这是一种计算变阶同质马尔科夫模型对数似然的方法。状态的apply方法获取所有先前的符号和即将到来的符号，并返回执行此操作的概率。

正如您所看到的：整个方法只是乘以一些概率，使用vars会更容易。

- peri4n

---

一个数据结构怎么可能没有状态？ - Lasse V. Karlsen

选定的答案是错误的。请查看我的评论并参考答案。引用透明甚至不是可交换的。 - Shelby Moore III

让我来评论一下，Shelby Moore III最后发表的那条评论正在进行激烈讨论。 - Blaisorblade

Answer 1

这个规则实际上并不是不可变性，而是引用透明度(referential transparency)。使用本地声明的可变变量和数组是完全可以的，因为对于整个程序的任何其他部分来说，这些效果都是不可观测的。

引用透明性（RT）原则如下：

如果对于所有程序p，表达式e在p中的每一个出现都可以被其求值结果替换，而不影响p的可观测结果，则表达式e是引用透明的。

需要注意的是，如果e创建并修改了一些本地状态，它也不会违反RT，因为没有人可以观察到这种情况的发生。

话虽如此，我非常怀疑您的实现是否真的比使用变量更直接。

- Apocalisp

---

是的，你要找的是一些原则，遵循它可以给你带来一些好处。你提到了“不可变性”，这很接近，但过于限制。更普遍的原则是“引用透明性”，我认为这就是你要找的原则。 - Apocalisp

请注意，您正在寻找的原则不是“适度”。即“一点点”可变状态是可以接受的想法。 - Apocalisp

@Apocalisp 我同意你所说的原则，但我觉得它并不完全准确。使用内部突变仍然意味着你在本地实现中违反了引用透明性。如果本地范围足够大且复杂，这可能会带来同样的问题（但通常不应该）。只是通过使用具有引用透明接口的编程，你可以获得大部分好处。你似乎在暗示引用透明性是仅适用于接口的属性，这是不正确的。 - Ben

@Apocalisp 噢，那我们是意见一致的。我读了你的帖子，认为如果你选择"引用透明性无处不在"而不是"不变性无处不在"，那么你可能会自然地得到纯接口和可能是不纯的本地实现。虽然我相信一个函数在界面上是引用透明的，但在内部使用可变性时，可能会在并发时失败。如果这是正确的，那么并非所有的"本地可变性"的使用方式都是真正不可观察的。 - Ben

如果并发可以影响结果，那么这个表达式显然不是引用透明的。@Ben说。 - Apocalisp

Answer 2

函数式编程的优点在于代码简洁，使用更数学化的方法。这可以减少错误的可能性，使您的代码更小且更易读。至于是否更容易，它确实要求您用不同的方式思考问题。但是一旦您习惯了使用函数式模式进行思考，很可能函数式比更加命令式的风格更容易掌握。

完全遵循函数式编程并拥有零可变状态是非常困难的，但是拥有最小的可变状态非常有益。需要记住的是，所有事情都需要平衡而不是极端。通过减少可变状态的数量，您会发现编写具有意外后果的代码变得更加困难。一个常见的模式是具有可变变量但其值是不可变的。这样身份（命名变量）和值（可分配给变量的不可变对象）是分离的。

var acc: List[Int] = Nil
// lots of complex stuff that adds values
acc ::= 1
acc ::= 2
acc ::= 3
// do loop current list
acc foreach { i => /* do stuff that mutates acc */ acc ::= i * 10 }
println( acc ) // List( 1, 2, 3, 10, 20, 30 )

foreach循环是在我们开始foreach时遍历acc的值。对acc的任何更改都不会影响到循环。这比Java中典型的迭代器要安全得多，因为列表可以在迭代过程中发生变化。

还存在并发问题。不可变对象非常有用，因为JSR-133内存模型规范断言对象的最终成员的初始化将发生在任何线程可以看到这些成员之前，无论如何！如果它们不是final，则它们是“可变的”，没有正确初始化的保证。

Actor是放置可变状态的完美位置。表示数据的对象应该是不可变的。接下来是一个例子。

object MyActor extends Actor {
  var acc: List[Int] = Nil
  def act() {
    loop {
      react {
        case i: Int => acc ::= i
        case "what is your current value" => reply( acc )
        case _ => // ignore all other messages
      }
    }
  }
}

在这种情况下，我们可以发送acc的值（即List），并且不必担心同步，因为List是不可变的，也就是说，List对象的所有成员都是final。此外，由于它是不可变的，我们知道没有其他角色可以更改已发送的基础数据结构，因此没有其他角色可以更改此角色的可变状态。

- Neil Essy

Answer 3

由于 Apocalisp 已经 提到 我要引用的内容，所以我将讨论代码。你说这只是简单的乘法，但我没有看到这一点——它引用了至少三个重要的在外部定义的方法：order、states 和 M.log。我可以推断出 order 是一个 Int，而 states 返回一个函数，该函数接受一个 List[T] 和一个 T 并返回一个 Double。

还有一些奇怪的事情发生...

def logLikelihood(seq: Iterator[T]): Double = {
  val sequence = seq.toList

sequence只被用来定义seqPos，那么为什么要这样做？

  val stateSequence = (0 to order).toList.padTo(sequence.length,order)
  val seqPos = sequence.zipWithIndex

  def probOfSymbAtPos(symb: T, pos: Int) : Double = {
    val state = states(stateSequence(pos))
    M.log(state( seqPos.map( _._1 ).slice(0, pos).takeRight(order), symb))

实际上，您可以在这里使用sequence代替seqPos.map( _._1 )，因为它只是撤销了zipWithIndex。此外，slice(0, pos)就是take(pos)。

  }

  val probs = seqPos.map( i => probOfSymbAtPos(i._1,i._2) )

  probs.sum
}

现在，由于缺少方法，很难确定这个应该如何以函数式风格编写。保留神秘的方法将产生以下结果：

def logLikelihood(seq: Iterator[T]): Double = {
  import scala.collection.immutable.Queue
  case class State(index: Int, order: Int, slice: Queue[T], result: Double)

  seq.foldLeft(State(0, 0, Queue.empty, 0.0)) {
    case (State(index, ord, slice, result), symb) =>
      val state = states(order)
      val partial = M.log(state(slice, symb))
      val newSlice = slice enqueue symb
      State(index + 1, 
            if (ord == order) ord else ord + 1, 
            if (queue.size > order) newSlice.dequeue._2 else newSlice,
            result + partial)
  }.result
}

我怀疑state/M.log的东西也可以成为State的一部分。我写成这样后，注意到了其他的优化。你使用的滑动窗口让我想起了sliding。

seq.sliding(order).zipWithIndex.map { 
  case (slice, index) => M.log(states(index + order)(slice.init, slice.last))
}.sum

这将只从第order个元素开始，因此需要进行一些适应。不过并不难。所以让我们再次重写它：

def logLikelihood(seq: Iterator[T]): Double = {
  val sequence = seq.toList
  val slices = (1 until order).map(sequence take) ::: sequence.sliding(order)
  slices.zipWithIndex.map { 
    case (slice, index) => M.log(states(index)(slice.init, slice.last))
  }.sum
}

我希望能够看到 M.log 和 states... 我敢打赌我可以将那个 map 转化为 foldLeft 并且不再需要这两个方法。而且我怀疑由 states 返回的方法可以接受整个切片而不是两个参数。

不过...还不错，对吧？

- Daniel C. Sobral