Geek Answers Handbook

Queue3 Chapter 19 in Programming in Scala 2nd edition Question

I am reviewing the code for the Queue3 example in a Program in Scala 2nd edition by Odersky et al. And I think I'm stuck.

Here's the code: 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) } }

Therefore, he is trying to implement the queue in functional programming at a speed similar to the imperative method.

To do this, he will split the queue into two parts so that we can add an end to the constant speed. The whole line is mainly:

 leading ::: trailing.reverse

The book says that the worst case scenario is when the beginning is empty.

So if the code does this

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

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

Therefore, when I call q.head, the book says that since the lead is empty, the mirror copies everything from the trailing, reverses it and sets it as the lead.

The problem is that I don’t think this works because it is a method? Therefore, it is not persisted through the state. Since I made the code properties publicly available and checked q.leading and q.trailing, and the value will be the same. What I expect after q.head:

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

But it is not, am I missing something? Is this some kind of FP paradigm I'm missing? Since I think this can work the way I think, it should work if the head and tail methods change to var.

Thank you for your time.

Edit property publication:

private val: List [T], private val trailing: List [T]

edit: chapter 19 in 1st edition: http://www.artima.com/pins1ed/type-parameterization.html

+4
source share
1 answer

The problem is that the head and tail methods do not return a new Queue . And you check the old one. Check out the head and tail versions. Now they return the new Queue to the tuple.

 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) }

As you can see, mirror works fine.

 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) }

Output:

 Queue(1, 2) leading: List() trailing: List(2, 1) 1 leading: List(1, 2) trailing: List()
+5
source

More articles:


All Articles