Scala type inference on an existential type

Question

Consider the following code snippet, which is a reduced version of my original problem:

case class RandomVariable[A](values: List[A])
case class Assignment[A](variable: RandomVariable[A], value: A)

def enumerateAll(vars: List[RandomVariable[_]], evidence: List[Assignment[_]]): Double = 
  vars match {
    case variable :: tail =>
      val enumerated = for {value <- variable.values
        extendedEvidence = evidence :+ Assignment(variable, value)
      } yield enumerateAll(tail, extendedEvidence)
      enumerated.sum
    case Nil => 1.0
  }

This fails with the compile-time error that variable was inferred to have type RandomVariable[_0] when Assignment required type Any. Why is value not also inferred to have type _0? I tried giving the existential type a name in order to give a hint to the compiler by using case (variable: RandomVariable[T forSome {type T}]) :: tail => but that also would not compile (saying it could not find type T, which I'd be interested in an explanation for as well).

For further motivation, consider when we capture the type parameter as follows:

case variable :: tail =>
  def sum[A](variable: RandomVariable[A]): Double = {
    val enumerated = for {value <- variable.values
      extendedEvidence = evidence :+ Assignment(variable, value)
      } yield enumerateAll(tail, extendedEvidence)
    enumerated.sum
  }
  sum(variable)

This compiles without warnings/errors. Is there something I can modify in the first example to not require this extra function?

EDIT: To be more explicit, I want to know why value is not inferred to be of type _0 even though variable is of type _0 and every value comes from a List[_0] in variable. Also I would like to know if there are any additional ways to tell the compiler of this fact (aside from capturing the type in a function as I gave above).

Also, this could potentially be fixed by changing the type parameters to type members and using path dependent types, however this question is more to understand how inference works with type parameters. — Alex DiCarlo, Jan 10 '13 at 04:29
Ok, then do not mind about my comment. I'm now interested in see how this whole inference work as well. — Claudio, Jan 10 '13 at 04:43
This isn't really a complete answer, but it's worth noting that `List[RandomVariable[_]]` is equivalent to `List[RandomVariable[T] forSome { type T }]`, while what you want is probably for the existential to scope over the list—i.e. `List[RandomVariable[T]] forSome { type T }`, which does at least compile without complaints. — Travis Brown, Jan 10 '13 at 12:22
To clarify, the first case is actually what I want, a list of random variables whose type can be anything, not necessarily a list of one specific type of `RandomVariable`. The distinction is subtle, and I probably should have been more clear in the original post. — Alex DiCarlo, Jan 10 '13 at 16:26

Alex DiCarlo · Accepted Answer · 2013-01-10T06:13:31.083

Another compiling solution, that is cleaner(?) than using a function to capture the type. However, it makes it even more puzzling as to why type inference fails in the original case.

def enumerateAll(vars: List[RandomVariable[_]], evidence: List[SingleAssignment[_]]): Double = vars match {
  case (variable@RandomVariable(values)) :: tail =>
    val enumeration = for {value <- values
      assignment = SingleAssignment(variable, value)
      extendedEvidence = evidence :+ assignment
    } yield enumerateAll(tail, extendedEvidence)
    enumeration.sum
  case Nil => 1.0
}

It also returns the following warning:

scala: match may not be exhaustive.
It would fail on the following input: List((x: questions.RandomVariable[?] forSome x not in questions.RandomVariable[?]))
  def enumerateAll(vars: List[RandomVariable[_]], evidence: List[SingleAssignment[_]]): Double = vars match {

Which I'm unable to decipher as of this posting. Also, running it with a few test cases produces the desired result without a match error using RandomVariables of int, double, and string in the parameter list.

score 0 · Answer 2 · answered Jan 10 '13 at 04:21

0

Shouldn't you bind the types of RandomVariable and Assignment together?

 def [A] enumerateAll(vars: List[RandomVariable[A]], evidence: List[Assignment[A]]): Double =

actually, you can be more permissive and just say

 def [A] enumerateAll(vars: List[RandomVariable[A]], evidence: List[Assignment[_ <: A]]): Double =

answered Jan 10 '13 at 04:21

Claudio

1,848
12
26

No, I have a list of random variables of any type and a list of assignments of any type, however that does provide me a clue as to where `Any` is being inferred, most likely from `evidence :+`. Edit: and it's not, adding an additional `assignment = Assignment(variable, value)` did not fix the issue. – Alex DiCarlo Jan 10 '13 at 04:26
What about forcing the type of RandomVariable to be at least Any. def enumerateAll[A <: Any](vars: List[RandomVariable[A]], evidence: List[Assignment[_]]):Double = ... it might be a workaround – Claudio Jan 10 '13 at 04:39
@pedrofuria I was wondering the same thing, Claudio seemed a bit confused on how existential types are being used in my particular example, but I'm not sure that's worthy of a down vote when he was just trying to help. – Alex DiCarlo Jan 10 '13 at 05:24

score 0 · Answer 3 · edited May 23 '17 at 10:24

The error code gives some indication of a solution.

<console>:15: error: type mismatch;
 found   : RandomVariable[_0] where type _0
 required: RandomVariable[Any]
Note: _0 <: Any, but class RandomVariable is invariant in type A.
You may wish to define A as +A instead. (SLS 4.5)
           extendedEvidence = evidence :+ Assignment(variable, value)

It's telling you that it saw a more specific type than it inferred and even suggested to make RandomVariable allow a covariant A. This would allow it to vary the type downward when required.

case class RandomVariable[+A](values: List[A])

Alternatively, you can explicitly set the generic type in enumerateAll for both parameters. In that way it can infer the appropriate type instead of being forced to infer Any. This definition doesn't require the RandomVariable covariant change as both parameters are of the same type.

def enumerateAll[A](vars: List[RandomVariable[A]], evidence: List[Assignment[A]]): Double =

This question may help with the explanation. Why doesn't the example compile, aka how does (co-, contra-, and in-) variance work?

As to the first solution, in my case `RandomVariable[A]` must be invariant in `A`. See comments in Claudio's answer for why the second solution does not work. Additionally, this does not answer my question as to *why inference fails in this case*, but thank you for suggesting ways to fix the issue at hand. — Alex DiCarlo, Jan 10 '13 at 05:48
Sorry about that. Actually there's a better third answer alluded to by [this article](http://www.drmaciver.com/2008/03/existential-types-in-scala/). case class Assignment[A](variable: RandomVariable[A] forSome {type A}, value: A) I'll leave it at that as I didn't originally answer the question properly. — Avilo, Jan 11 '13 at 06:19

Scala type inference on an existential type

3 Answers3

Linked