Resolving types in F-bounded polymorphism

Question

I have these models:

trait Vehicle[T <: Vehicle[T]] { def update(): T }
class Car extends Vehicle[Car] { def update() = new Car() }
class Bus extends Vehicle[Bus] { def update() = new Bus() }

If I obtain an instance of a Vehicle[Car] and invoke update(), I will get a Car. Since Car extends Vehicle[Car] (or simply put, Car is a Vehicle[Car]), I can safely set the type of the result explicitly to Vehicle[Car]:

val car = new Car
val anotherCar = car.update()
val anotherCarAsVehicle: Vehicle[Car] = car.update() // works as expected

But if I want to, say, put instances of Car and Bus together into one list, then I have to set the list type to Vehicle[_ <: Vehicle[_]] (having a list of simply Vehicle[_] and invoking update() on an element would yield Any, but I want to be able to use update() so I have to use the F-bounded type). Using existential types screws up the type relationships, because once I fetch the underlying car/bus from the Vehicle, I can no longer cast it to Vehicle because... well, it's just some existential type:

val seq = List[Vehicle[_ <: Vehicle[_]]](new Car, new Bus)
val car = seq.head.update()
val carAsVehicle: Vehicle[_ <: Vehicle[_]] = seq.head.update() // fails to compile

So, Vehicle is parameterized with some type T which is a subtype of Vehicle[T]. When I rip out the T (by using update()), in case of concrete types it's ok - e.g. if I rip out the Car, I can safely claim that I ripped out a Vehicle[Car] because Car <: Vehicle[Car]. But if I rip out an existential type, I can't do anything with it. Earlier example worked because Car is a Vehicle[Car], but in this case _ is not a Vehicle[_].

To specify my concrete question: for models given above (Vehicle, Car, Bus), is there a way to achieve this?

def sameType[T, U](a: T, b: U)(implicit evidence: T =:= U) = true

val seq = List[Vehicle[_ <: Vehicle[_]]](new Car, new Bus)

sameType(seq.head.update +: seq.tail, seq) // true 

Note that you can change the given traits, classes and type of seq, but there's one restriction: update() must return T, not Vehicle[T].

I know that using shapeless HList would solve the problem as I wouldn't have to use existential types (I would simply have a list of a car and a bus, and that type information would be preserved). But I'm wondering for this particular use case with a simple List.

EDIT:

@RomKazanova yes, that would work of course, but I need to retain the same type before and after update() (here's an upvote for the effort though ;)).

I believe that it's not possible without HList or similar data structure, because unifying cars and buses forces us to use the vehicle type which loses info about whether its underlying type was Car, Bus or something else (all we can know is that it was some type _ <: Vehicle). But I want to check with you guys.

Answer 1

I'm not very good with existential types, so I can't explain too much about this :-p But when you change the type of seq to List[Vehicle[T] forSome {type T <: Vehicle[T]}] everything seems to "work out". Mind you have to pass the type to the List constructor/apply method.

scala> val seq = List[Vehicle[T] forSome {type T <: Vehicle[T]}](new Car, new Bus)
seq: List[Vehicle[T] forSome { type T <: Vehicle[T] }] = List(Car@31e53802, Bus@54d569e7)

scala> sameType(seq.head.update +: seq.tail, seq)
res3: Boolean = true

scala> seq.head.update
res4: T forSome { type T <: Vehicle[T] } = Car@79875bd2

scala> seq.head.update.update
res5: T forSome { type T <: Vehicle[T] } = Car@6928c6a0

scala> new Car +: seq
res6: List[Vehicle[T] forSome { type T <: Vehicle[T] }] = List(Car@51f0a09b, Car@31e53802, Bus@54d569e7)

I think the main thing to get out of this answer is that this lets you spell out the recursive nature of the Vehicle type constructor.

I'm not sure I would recommend this though...