CODEWITHSUNDEEP
scala
Steven Shaw
Steven Shaw

Reputation: 6249

What's going on here with scala.collection.immutable.Stack.+: (prepend)?

I noticed that the ScalaDoc for immutable Stack refers to a method prepend with the following signature:

class Stack[A+] ...
  def +: (elem: A): Stack[A]

That method signature looked wrong to me because Stack is covariant in the A type parameter (so the type of elem should be a compiler error). What's more, Scaladoc says that the definition of this method is in GenSeqLike but it doesn't appear to be there.

SeqLike has an implementation of +: that I imagine is the one that's being used by Stack.

trait SeqLike[+A, +Repr] ...
  def +:[B >: A, That](elem: B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
    val b = bf(repr)
    b += elem
    b ++= thisCollection
    b.result
  }

This doesn't look to be as efficient as Stack.push.

When I try to provide my own implementation of +: (as push), I do get the expected compiler errors that the method I'm overriding doesn't exist and about the covariance issue.

class Stack2[+A] extends Stack[A] {
  override def +: (elem: A): Stack[A] = this push elem
}

scalac Stack2.scala gives:

Stack2.scala:4: error: method +: overrides nothing
  override def +: (elem: A): Stack[A] = this push elem
               ^
Stack2.scala:4: error: covariant type A occurs in contravariant position in type A of value elem
  override def +: (elem: A): Stack[A] = this push elem
                   ^
two errors found

Is it possible to implement +: efficiently using push?

Upvotes: 4

Views: 133

Answers (1)

Rex Kerr
Rex Kerr

Reputation: 167891

The documentation is a little confusing here. You'll notice that that method is marked as a use case. The actual signature is this one:

def +: [B >: A, That] (elem: B)(implicit bf: CanBuildFrom[Stack[A], B, That]): That
Prepends an element to this immutable stack

The use case is just showing a typical way you might use it (and even though the real signature changed in SeqLike, the use case didn't change from GenSeqLike, hence the apparently incorrect attribution).

You're correct that the implementation of +: is not efficient, though you couldn't tell this for certain given the code that you posted. b ++= thisCollection could notice that the rest of it is just a stack and push elem on the front. But it doesn't; b is just an ArrayBuffer underneath the hood.

So use a list instead, like the doc suggests.

Upvotes: 7

Related Questions