blue-sky
blue-sky

Reputation: 53916

Using type parameters in scala

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' ?

Upvotes: 3

Views: 1117

Answers (3)

Larsenal
Larsenal

Reputation: 51196

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.

Upvotes: 4

Eastsun
Eastsun

Reputation: 18869

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

Upvotes: 4

Ben Kyrlach
Ben Kyrlach

Reputation: 379

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.

Upvotes: 2

Related Questions