Taming the Scala type system

Question

I don't seem to understand the Scala type system. I'm trying to implement two base traits and a trait for a family of algorithms to work with them. What am I doing wrong in the below?

The base traits for moves & states; these are simplified to just include methods that expose the problem.

trait Move
trait State[M <: Move] {
    def moves: List[M]
    def successor(m: M): State[M]
}

Here's the trait for the family of algorithms that makes use of above. I'm Not sure this is right! There might be some +M / -S stuff involved...

trait Algorithm {
    def bestMove[M <: Move, S <: State[M]](s: S): M
}

Concrete move and state:

case class MyMove(x: Int) extends Move
class MyState(val s: Map[MyMove,Int]) extends State[MyMove] {
    def moves = MyMove(1) :: MyMove(2) :: Nil
    def successor(p: MyMove) = new MyState(s.updated(p, 1))
}

I'm on very shaky ground regarding the below, but the compiler seems to accept it... Attempting to make a concrete implementation of the Algorithm trait.

object MyAlgorithm extends Algorithm {
    def bestMove(s: State[Move]) = s.moves.head
}

So far there are no compile errors; they show up when I try to put all the parts together, however:

object Main extends App {
    val s = new MyState(Map())
    val m = MyAlgorithm.bestMove(s)
    println(m)
}

The above throws this error:

error: overloaded method value bestMove with alternatives:
  (s: State[Move])Move <and>
  [M <: Move, S <: State[M]](s: S)M
 cannot be applied to (MyState)
    val m = MyAlgorithm.bestMove(s)
                        ^

Update: I changed the Algorithm trait to use abstract type members, as suggested. This solved the question as I had phrased it but I had simplified it a bit too much. The MyAlgorithm.bestMove() method must be allowed to call itself with the output from s.successor(m), like this:

trait Algorithm {
    type M <: Move
    type S <: State[M]
    def bestMove(s: S): M
}

trait MyAlgorithm extends Algorithm {
    def score(s: S): Int = s.moves.size
    def bestMove(s: S): M = {
        val groups = s.moves.groupBy(m => score(s.successor(m)))
        val max = groups.keys.max
        groups(max).head
    }
}

The above gives now 2 errors:

Foo.scala:38: error: type mismatch;
 found   : State[MyAlgorithm.this.M]
 required: MyAlgorithm.this.S
            val groups = s.moves.groupBy(m => score(s.successor(m)))
                                                               ^
Foo.scala:39: error: diverging implicit expansion for type Ordering[B]
starting with method Tuple9 in object Ordering
            val max = groups.keys.max
                                  ^

Do I have to move to an approach using traits of traits, aka the Cake pattern, to make this work? (I'm just guessing here; I'm thoroughly confused still.)

I'd suggest you to think of a better title. This one is too general. — Petr
@PetrPudlák - I'm open for suggestions of improvements, but it was what I could come up with that best described what I was trying to do... — Stig Brautaset
@sschaef because I want MyAlgorithm to be generic and work for many concrete implementations of M and S. — Stig Brautaset

stew stew · Accepted Answer · 2012-11-14T03:16:13

You declare MyAlgorithm#bestMove explicitly as taking a State[Move] parameter, but inside Main you are trying to pass it a MyState, which is a State[MyMove] not a State[Move].

You have a couple of options to resolve this. One would be to not constrain the types in MyAlgorithm:

object MyAlgorithm extends Algorithm {
    def bestMove[M <: Move, S <: State[M]](s: S) : M = s.moves.head
}

Unfortunately, the scala type inference isn't smart enough to figure these types out for you, so at the call site, you have to declare them, making the call to MyAlgorithm#bestMove look like this:

val m = MyAlgorithm.bestMove[MyMove, MyState](s)

Another option use abstract type members of the Algorithm trait:

trait Algorithm {
  type M <: Move
  type S <: State[M]
    def bestMove(s: S): M
}

And resolve the abstract types in the concrete implementation:

object MyAlgorithm extends Algorithm {
  type M = MyMove
  type S = MyState
  def bestMove(s: S) : M = s.moves.head
}

Then the call site gets to return to your original version, without mentioning the types:

val m = MyAlgorithm.bestMove(s)

You may want to keep MyAlgorithm unaware of the actual types, and leave the determining of those types to the 'clients' of that object, in which case, change the object to a trait:

trait MyAlgorithm extends Algorithm {
  def bestMove(s: S) : M = s.moves.head
}

Then in your Main class, you instantiate a MyAlgorithm with the concrete types:

val a = new MyAlgorithm {
  type M = MyMove
  type S = MyState
}
val m = a.bestMove(s)

Your comment "There might be some +M / -S stuff involved" was a good guess, but It won't work for you here. You might hope that the covariant type modifier "+" might help here. If you had declared the type parameter on State as

State[+M]

This would indicate that State[M] <:< State[N] if M <:< N. (read <:< as "is a subtype of"). Then you would have no problem passing in a State[MyMove] where a State[Move] was expected. However, you cannot use the covariant modifier on M here because it appears in the contravariant position as an argument to the successor function.

Why is this a problem? Your declaration of successor says that it will take an M and return a State. The covariant annotation says that a State[M] is also a State[Any]. So we should allow this assignment:

val x : State[Any] = y : State[MyMove]

Now if we have a State[Any], then x.successor is what type? Any => MyMove. Which cannot be correct, since your implementation is expecting a MyMove, not an Any

Taming the Scala type system

2 Answers

Solution 0

Solution 1

Solution 2

Solution 3

Conclusion