Constructor (trait) can't be applied to (class extending trait)

Question

I've got a trait "Value" and an extending class "Equation", like so:

trait Value {
    def apply(in: Input): Int
}

class Equation ( eq: Array[Array[Value]] ) extends Value {
    override def apply (in: Input) = {
        eq.map(addend => addend.map( _(in) ).fold(1)(_ * _) ).fold(0)(_ + _)
    }

    def this(eq: String) = {
        this( eq.replace("-", "+-").split('+').map( _.split('*').map(s => Value(s)) ) )
    }
}

(For my purposes division isnt necessary, subtraction is solved by adding the negative version of something. I intend to remove the auxillary constructor here once I have the full string parser done, it's a quick solution that doesn't handle parentheses)

In the process of trying to parse a string into an equation, I've created an Array[Array[Equation]], because Equations inside Equations let me handle order of operations for parentheses. Since an Equation is a Value, I expected that I could pass this Array[Array[Equation]] into Equation's constructor, but then I get the following error:

overloaded method constructor Equation with alternatives:
[error]   (eq: String)spekular.misc.Equation <and>
[error]   (eq: Array[Array[spekular.misc.Value]])spekular.misc.Equation
[error]  cannot be applied to (Array[Array[spekular.misc.Equation]])

Any idea what I'm doing wrong? I tried rewriting the constructor for an Equation (see below), but that got me more errors and seems more complex than necessary:

class Equation [T <: Value] ( eq: Array[Array[T]] ) extends Value { ... }

Answer 1

The issue that you observe boils down to the fact that Array in Scala is invariant. For example:

trait Base
class Derived extends Base

val bases: Array[Base] = Array[Derived](new Derived)

The error message produced by this code is a bit more clear:

type mismatch;
 found   : Array[Derived]
 required: Array[Base]
Note: Derived <: Base, but class Array is invariant in type T.

You can find more information on variance e.g. here. The idea is, basically, that if some type Collection[T] is invariant in its type argument T, it means that you cannot assign a value of type Collection[Derived] to a variable/parameter of expected type Collection[Base], and vice versa.

There are very good reasons for arrays to be invariant: an array is mutable, and if it wasn't invariant and was e.g. covariant, then it would be possible to violate the typing guarantees:

trait Base
class Derived1 extends Base
class Derived2 extends Base

val derived1s: Array[Derived1] = Array(new Derived1)
val bases: Array[Base] = derived1s
bases(0) = new Derived2  // putting Derived2 in an array of Derived1
val derived1: Derived1 = derived1s(0)  // type mismatch

Naturally, for "nested" type constructors invariance is propagated, so you cannot assign Array[Array[Equation]] to Array[Array[Value]].

The simplest way to fix this would be to use some covariant collection (which is necessarily immutable):

class Equation(eq: Vector[Vector[Value]]) extends Value {
  ...
}

Vector[T], being an immutable collection, is covariant in its type argument, so it is possible to assign Vector[Derived] to Vector[Base]. Therefore, your code will work.