Scala编程第二版第19章问题

Question

我正在为Odersky等人编写的Programming in Scala第2版中的Queue3示例做代码审查。我想我被困住了。

代码如下:http://booksites.artima.com/programming_in_scala_2ed/examples/type-parameterization/Queues3.scala

object Queues3 {
  class Queue[T](
    private val leading: List[T], 
    private val trailing: List[T] 
  ) {
    private def mirror = 
      if (leading.isEmpty)
        new Queue(trailing.reverse, Nil)
      else
        this
    def head = mirror.leading.head
    def tail = { 
      val q = mirror 
      new Queue(q.leading.tail, q.trailing) 
    }
    def enqueue(x: T) = 
      new Queue(leading, x :: trailing)
    override def toString = 
      leading ::: trailing.reverse mkString ("Queue(", ", ", ")")
  }
  object Queue {
    // constructs a queue with initial elements `xs'
    def apply[T](xs: T*) = new Queue[T](xs.toList, Nil)
  }
  def main(args: Array[String]) {
    val q = Queue[Int]() enqueue 1 enqueue 2
    println(q)
  }
}

因此，它试图以函数式编程的方式实现队列，其速度与命令式方式相似。

因此，为了做到这一点，它会将队列分成两部分，以便我们可以以恒定的速度向末尾添加。整个队列基本上是:

leading ::: trailing.reverse

书上说最坏的情况是前导为空。

如果代码这样做

val q = Queue[Int]() enqueue 1 enqueue 2

,q.leading是List()， q.trailing是List(2,1)

所以当我调用q.head时，书上说因为leading是空的，mirror会从trailing复制所有内容，将其反转并设置为leading。

问题是我不认为这工作，因为它是一个方法?所以它不是通过状态保存的。因为我使代码属性公开，并检查了q.leading和q.trailing，值是相同的。在我执行q.head之后，我期望的是:

q.leading is List(1,2) and q.trailing is List()

但它不是，我错过了什么?这是我遗漏的一些FP范例吗?因为我认为它可以按照我认为的方式工作，如果头和尾方法改为var。

感谢您的宝贵时间。

编辑使属性公开:

private val leading: List[T];private val trailing: List[T]

编辑:第一版第十九章:http://www.artima.com/pins1ed/type-parameterization.html

Answer 1

您的问题是head和tail方法不返回新的Queue。而你在检查旧的。签出head和tail的这个版本。现在它们返回一个元组中的新Queue。

def head: (T, Queue[T]) = {
    val q = mirror
    (q.leading.head, q)
  }
def tail: (Queue[T], Queue[T]) = {
  val q = mirror
  (new Queue(q.leading.tail, q.trailing), q)
}

可以看到，mirror工作得很好。

val q = Queue[Int]() enqueue 1 enqueue 2
println(q)
printLT(q)
val q1 = q.head
println(q1._1)
printLT(q1._2)
def printLT[A](q: Queue[A]) {
  println("leading: " + q.leading)
  println("trailing: " + q.trailing)
}

输出:

Queue(1, 2)
leading: List()
trailing: List(2, 1)
1
leading: List(1, 2)
trailing: List()