Aux pattern with inherited types fails inference

Question

I have a convoluted toy algorithm I wish to represent purely at the typelevel: that of selecting a modification for a dish of the day based on a dietary requirement. Apologies for the convolution but I think we need each layer in order to get to the final interface I want to work with.

There's a problem with my code, where if we express a type constraint on an Aux-pattern-generated type based on another generic type, it fails type inference.

These are the meals, in reality there would be many varieties of pizza and many base meals:

trait Pizza
trait CheeselessPizza extends Pizza

Dietary requirements:

sealed trait DietaryRequirement
trait Vegan extends DietaryRequirement

A dish of the day typeclass:

sealed trait DishOfTheDay[Meal]

object DishOfTheDay {
  implicit val dishOfTheDay: DishOfTheDay[Pizza] = null
}

This would change meal every day, independently of the rest of the program.

A ModifiedMeal typeclass, which takes a meal and a dietary requirement and generates a submeal that satisfies the requirements. The subtyping is important here:

// <: Meal is important
sealed trait ModifiedMeal[Meal, D <: DietaryRequirement] { type Mod <: Meal }

object ModifiedMeal {

  type Aux[Meal, D <: DietaryRequirement, Mod0 <: Meal] = ModifiedMeal[Meal, D] { type Mod = Mod0 }

  // Only one instance so far, Vegan Pizza = CheeselessPizza
  implicit val veganPizzaModifiedMeal: ModifiedMeal.Aux[Pizza, Vegan, CheeselessPizza] = null

}

And here's our final typeclass which does the calculation for us:

// Given a dietary requirement, give us a dish of the day which satisfies it
// if one exists
trait DishOfTheDayModification[Req <: DietaryRequirement] { type Out }

object DishOfTheDayModification {

  type Aux[Req <: DietaryRequirement, Out0] = DishOfTheDayModification[Req] { type Out = Out0 }

  // Find the dish of the day, then find a ModifiedMeal of it
  // <: Meal is important here so we pick up ONLY pizzas and not some other meal
  implicit def dishOfTheDayModification[Meal, Req <: DietaryRequirement, Mod <: Meal](
    implicit d: DishOfTheDay[Meal],
    impl: ModifiedMeal.Aux[Meal, Req, Mod]
  ): DishOfTheDayModification.Aux[Req, Mod] = null

}

And here is the testing:

object MealTesting {
  def veganDishOfTheDay[Mod](implicit d: DishOfTheDayModification.Aux[Vegan, Mod]): Mod = ???

  // Does not compile but it should
  veganDishOfTheDay: CheeselessPizza
}

The problem is calling this method does not compile, but it should.

If you copy the entire program but remove the <: Meal requirements from the generated meal, it compiles. Here is the whole thing again, but 'working':

trait Pizza
trait CheeselessPizza extends Pizza

sealed trait DietaryRequirement
trait Vegan extends DietaryRequirement

sealed trait DishOfTheDay[Meal]

object DishOfTheDay {
  implicit val dishOfTheDay: DishOfTheDay[Pizza] = null
}

sealed trait ModifiedMeal[Meal, D <: DietaryRequirement] { type Mod }

object ModifiedMeal {

  type Aux[Meal, D <: DietaryRequirement, Mod0] = ModifiedMeal[Meal, D] { type Mod = Mod0 }

  implicit val veganPizzaModifiedMeal: ModifiedMeal.Aux[Pizza, Vegan, CheeselessPizza] = null

}

trait DishOfTheDayModification[Req <: DietaryRequirement] { type Out }

object DishOfTheDayModification {

  type Aux[Req <: DietaryRequirement, Out0] = DishOfTheDayModification[Req] { type Out = Out0 }

  implicit def dishOfTheDayModification[Meal, Req <: DietaryRequirement, Mod](
    implicit d: DishOfTheDay[Meal],
    impl: ModifiedMeal.Aux[Meal, Req, Mod]
  ): DishOfTheDayModification.Aux[Req, Mod] = null

}

object MealTesting {
  def veganDishOfTheDay[Mod](implicit d: DishOfTheDayModification.Aux[Vegan, Mod]): Mod = ???

  // DOES compile
  veganDishOfTheDay: CheeselessPizza
}

But we don't want this, because it allows us to generate dishes which AREN'T a subtype of the dish of the day.

Does anyone know why the inheritance in the Aux pattern causes the failure, or how I might structure the program with intermediate implicits to try and get around the problem?

Answer 1

Your original approach was very close to not having an issue, and only needs a minor adjustment in the 1 dishOfTheDayModification signature for it to compile successfully using Scala v2.12.

For reference, in the original DishOfTheDayModification object definition was this:

// Find the dish of the day, then find a ModifiedMeal of it
// <: Meal is important here so we pick up ONLY pizzas and not some other meal
implicit def dishOfTheDayModification[Meal, Req <: DietaryRequirement, Mod <: Meal](
  implicit
     // vvvvvv - Here's the problem
     d: DishOfTheDay[Meal],
     impl: ModifiedMeal.Aux[Meal, Req, Mod]
  ): DishOfTheDayModification.Aux[Req, Mod] = null

Switching the order to instead be:

implicit def dishOfTheDayModification[Meal, Req <: DietaryRequirement, Mod <: Meal](
  implicit
     impl: ModifiedMeal.Aux[Meal, Req, Mod],
     d: DishOfTheDay[Meal]
): DishOfTheDayModification.Aux[Req, Mod] = null

Allows the compiler to unify Meal and Mod successfully for impl before resolving d.

Answer 2

Try to replace bound on generic with evidence:

trait Pizza
trait CheeselessPizza extends Pizza

sealed trait DietaryRequirement
trait Vegan extends DietaryRequirement

sealed trait DishOfTheDay[Meal]

object DishOfTheDay {
  implicit val dishOfTheDay: DishOfTheDay[Pizza] = null
}

sealed trait ModifiedMeal[Meal, D <: DietaryRequirement] { type Mod <: Meal }

object ModifiedMeal {
  type Aux[Meal, D <: DietaryRequirement, Mod0 /*<: Meal*/] = ModifiedMeal[Meal, D] { type Mod = Mod0 }

  //implicit val veganPizzaModifiedMeal: ModifiedMeal.Aux[Pizza, Vegan, CheeselessPizza] = null

  def mkAux[Meal, D <: DietaryRequirement, Mod](implicit ev: Mod <:< Meal): Aux[Meal, D, Mod] = null

  implicit val veganPizzaModifiedMeal: ModifiedMeal.Aux[Pizza, Vegan, CheeselessPizza] = mkAux
}

trait DishOfTheDayModification[Req <: DietaryRequirement] { type Out }

object DishOfTheDayModification {
  type Aux[Req <: DietaryRequirement, Out0] = DishOfTheDayModification[Req] { type Out = Out0 }

  implicit def dishOfTheDayModification[Meal, Req <: DietaryRequirement, Mod /*<: Meal*/](implicit 
    d: DishOfTheDay[Meal],
    impl: ModifiedMeal.Aux[Meal, Req, Mod],
    ev: Mod <:< Meal
  ): DishOfTheDayModification.Aux[Req, Mod] = null
}

object MealTesting {
  def veganDishOfTheDay[Mod](implicit d: DishOfTheDayModification.Aux[Vegan, Mod]): Mod = ???

  veganDishOfTheDay: CheeselessPizza
}