So here's the code:
package week4
object expr {
abstract class Expr[T] {
def eval:T = this match {
case Number(x) => x
case Sum(e1, e2) => e1.eval + e2.eval
}
def show: String = this match {
case Number(x) => "" + x
case Sum(e1, e2) => "(" + e1.show + "+" + e2.show + ")"
}
}
case class Number[T](val value: T) extends Expr {
}
case class Sum[T](val e1: Expr[T], val e2: Expr[T]) extends Expr {
}
}
except I get the error on all for case comparisons that:
constructor cannot be instantiated to expected type; found : week4.expr.Number[T(in class Number)] required: week4.expr.Expr[T(in class Expr)] Note: Nothing <: T (and week4.expr.Number[T] <: week4.expr.Expr[Nothing]), but class Expr is invariant in type T. You may wish to define T as +T instead.
What am i doing wrong?
There are mainly two errors in your code:
Expr you forgot to pass the type parameterSum branch of your pattern matching you are trying to sum two Ts, without giving enough evidence to the compiler of the fact that the + operator is defined on the type T.Here is a revised solution that works:
object expr {
abstract class Expr[T](implicit evidence: Numeric[T]) {
def eval: T = this match {
case Number(x) => x
case Sum(e1, e2) => evidence.plus(e1.eval, e2.eval)
}
def show: String = this match {
case Number(x) => "" + x
case Sum(e1, e2) => "(" + e1.show + "+" + e2.show + ")"
}
}
case class Number[T : Numeric](val value: T) extends Expr[T]
case class Sum[T : Numeric](val e1: Expr[T], val e2: Expr[T]) extends Expr[T]
}
Here is an example run in the Scala shell:
scala> import expr._
import expr._
scala> Sum(Sum(Number(2), Number(3)), Number(4))
expression: expr.Sum[Int] = Sum(Sum(Number(2),Number(3)),Number(4))
scala> println(expression.show + " = " + expression.eval)
((2+3)+4) = 9
I'm sure the missing type parameter for the type constructor Expr is just a distraction and it doesn't need further explanation.
The code in my example introduces an implicit parameter evidence and the usage of the Numeric type class. In Scala, a type class is a pattern that leverages traits and implicit parameters to define capabilities for classes with a certain degree of flexibility.
In order to sum two generic values, the compiler has to have a way to know that the two Ts know how be summed. However the numeric types are not in a type hierarchy that can be leveraged by saying that T is a subtype of an hypothetic class Number (by writing something like abstract class Expr[T <: Number]).
The Scala standard library however has introduced the Numeric type class, which is basically a trait that defines a set of operations that make sense for all numeric types (hence the name). The plus method is a left unimplemented for whoever wants to adhere to this trait.
The Scala standard library implements this traits for various numeric types, thus allowing you to effortlessly use this same generic implementation with various types.
Here is an example:
scala> val expression = Sum(Sum(Number(2.0), Number(3.0)), Number(4.0))
expression: expr.Sum[Double] = Sum(Sum(Number(2.0),Number(3.0)),Number(4.0))
scala> println(expression.show + " = " + expression.eval)
((2.0+3.0)+4.0) = 9.0
Specifying an implicit evidence like this can be done explicitly (as in abstract class Expr[T](implicit evidence: Numeric[T])) or by using the so called "context bound" notation (as in case class Number[T : Numeric]), which is basically syntactic sugar for the explicit variant that foregoes to explicitly reference a type class instance. I used the explicit variant in the first case because I needed to reference the type class instance in my code to actually sum the two values (evidence.plus(e1.eval, e2.eval)) but I used the "context bound" notation in the latter case as I feel it more natural and readable.
If you so wish, you can also implement Numeric[T] for your own classes (e.g.: Numeric[Rational]) without having to deal with a static type hierarchy.
This of course is a very rushed explanation of type classes: for a more thorough explanation I suggest you this very good blog post on the topic.