Using type parameters in scala

Question

I'm attempting to convert a stack of Strings into a generic Stack .

Here is the Stack of String implementation :

class LinkedStackOfStrings {

  var first : Node = _

  def isEmpty : Boolean  = {
    first == null
  }

  def push(itemName : String) = {
    val oldFirst = first
    first = new Node(itemName , oldFirst)
  } 

  def pop = {
    first = first.next

    first.itemName

  }

}

  class Node(val itemName : String , val next : Node) {}

Here is my Stack of Generic types implementation :

class LinkedStackGeneric[T] {

  var first : NodeGeneric[T] = _

  def isEmpty : Boolean  = {
    first == null
  }

  def push(itemName : T) = {
    val oldFirst = first
    first = new NodeGeneric(itemName , oldFirst)
  } 

  def pop = {
    first = first.next

    first.itemName

  }

}

  class NodeGeneric[T](val itemName : T , val next : NodeGeneric[T]) {}

When I attempt to initialse my new generic class with data :

   val generic = new LinkedStackGeneric
   generic.push("test")

I receive this syntax error :

type mismatch; found : String("test") required: Nothing

What am I doing wrong ? Since I'm using a type parameter should I not be able to add data of any type including String to method 'push' ?

You misunderstand type parameters. T can only be exactly 1 type after you instantiate. It does not mean you can put any element in your stack. It means that you can create instances for any 1 type. — Felix
– Felix, Commented Apr 18, 2013 at 7:47

Eastsun · Accepted Answer · 2013-04-18 02:33:00Z

4

You can fix this issue by making the Stack object immutable:

object ImmutableStack {
  trait ImmutableStack[+A] {
    def isEmpty: Boolean
    def push[B >: A](item: B): ImmutableStack[B] = new <<(this, item)
    def pop: (ImmutableStack[A], Option[A])
    def <<[B >: A](item: B) = push(item)
  }
  case class <<[+A](init: ImmutableStack[A], last: A) extends ImmutableStack[A] {
    override def isEmpty = false
    override def pop: (ImmutableStack[A], Option[A]) = (init, Some(last))
    override def toString = "" + init + " << " + last
  }
  case object Nst extends ImmutableStack[Nothing] {
    override def isEmpty = true
    override def pop = (Nst, None)
    override def toString = "Nst"
  }
}

Then we have:

scala> import ImmutableStack._
import ImmutableStack._

scala> val intStack = Nst << 5 << 4 << 3 << 2 << 1
intStack: ImmutableStack.ImmutableStack[Int] = Nst << 5 << 4 << 3 << 2 << 1

scala> intStack.pop
res0: (ImmutableStack.ImmutableStack[Int], Option[Int]) = (Nst << 5 << 4 << 3 << 2,Some(1))

scala> val firstItems << lastItem = intStack
firstItems: ImmutableStack.ImmutableStack[Int] = Nst << 5 << 4 << 3 << 2
lastItem: Int = 1

scala> val strStack = Nst << "A" << "B" << "C"
strStack: ImmutableStack.ImmutableStack[String] = Nst << A << B << C

scala> val fs << lt = strStack
fs: ImmutableStack.ImmutableStack[String] = Nst << A << B
lt: String = C

scala> val anyStack = Nst << 1 << "Str" << 'Z'
anyStack: ImmutableStack.ImmutableStack[Any] = Nst << 1 << Str << Z


scala> val st << x1 << x2 << x3 = anyStack
st: ImmutableStack.ImmutableStack[Any] = Nst
x1: Any = 1
x2: Any = Str
x3: Any = Z

edited Apr 18, 2013 at 2:33

answered Apr 18, 2013 at 2:26

Eastsun

18.9k7 gold badges60 silver badges87 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

nadavwr Over a year ago

@user470184, this is your answer. The covariance (Stack[+A]) and type lower bound (def push[B >: A](b: B): Stack[B]) are the key. To read more on type variance (both class-level and method-level) take a look here. There's a very nice walk-through of an immutable stack, along with explanation on why it allows for more flexible typing than a mutable stack.

Jose Cabrera Zuniga Over a year ago

What means [+A]?

Larsenal · Accepted Answer · 2013-04-18 05:18:43Z

4

At first glance I wouldn't expect what you're trying to work.

The type inference has no basis for inferring the type when you instantiate the object. It's not smart enough to see that on the next line you push a String. As a result, you have to do this:

val generic = new LinkedStackGeneric[String]
generic.push("test")

I'd love to be proven wrong.

edited Apr 18, 2013 at 5:18

answered Apr 17, 2013 at 20:27

Larsenal

51.5k43 gold badges155 silver badges224 bronze badges

6 Comments

blue-sky Over a year ago

this limits to just adding of type String. To add any type I could use : 'val generic = new LinkedStackGeneric[Any]' ?

Nick H Over a year ago

You can do that, but then what was the point of having the type parameter?

blue-sky Over a year ago

@Nick if I don't make it generic then I cannot instantiate with 'val generic = new LinkedStackGeneric[Any]' . I don't think I fully understand your point....

Nick H Over a year ago

I just mean if you use a type of [Any], you may as well not use a type parameter at all because you can store any objects in there. If you're just using it as an example and still intend to use more specific types with your stack then that makes sense, and I guess I just misread your comment.

Brian Hsu Over a year ago

I think what @Nick means is that if all you want is store Any object in your stack, you just need a class Node(val item: Any, val next: Node). A main point of generic is to specify what kind (type) of object could be store in that stack you create using new keyword according to your need. So typically we wouldn't use Stack[Any] as example, since this could be achieved by just declare that class Node(val item: Any, val next: Node).

|

Chirlo · Accepted Answer · 2013-04-17 21:20:22Z

Scala's type inference engine is notorious for inferring Nothing in cases like yours. To put it briefly, Scala's type hierarchy has both a top (Any) and a bottom (Nothing) that all other types must exist between. All types have a super-type of Any, and Nothing is a common sub-type to all types.

What does this mean for you? Well, when you instantiate your LinkedStackGeneric instance, you omit any type for the type parameter T. This indicates to Scala that it needs to infer the type (as, being a statically typed language, it must determine a type for everything at compile time). In this case, Scala's type inference engine picks poorly (from a user expectation perspective), and selects the bottom type (Nothing) as the type of the parameter T. With this in place, where you go to add your value "test", the Scala compiler (rightly) complains that String cannot be added to a LinkedStackGeneric[Nothing], as even though all Nothings are Strings, not all (or perhaps not any) Strings are Nothings.

A few more notes for the curious. Nothing is actually what is called an uninhabited type, meaning that there can never be an instance of type Nothing. So, even though I said not all Strings are Nothings, it is in fact impossible for a String to be a Nothing.

Collectives™ on Stack Overflow

Using type parameters in scala

3 Answers 3

2 Comments

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related