2

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?

Gesar
  • 389
  • 1
  • 7

2 Answers2

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
}
Dmytro Mitin
  • 48,194
  • 3
  • 28
  • 66
  • Thanks, that does get around the problem. However, the inheritance is important for integration with other bits which I did not replicate here. For example a typeclass which acts on Pizza. You couldn't use that here since we have lost the information about `Mod <: Meal`. Do you have any idea why this inheritance breaks everything - or how to trick the compiler into re-inferring the inheritance based on the `<:<` typeclass? I'm drawing a blank – Gesar Oct 05 '18 at 16:03
  • 1
    I slightly updated my answer. I replaced `implicit val veganPizzaModifiedMeal: ModifiedMeal.Aux[Pizza, Vegan, CheeselessPizza] = null` with `def mkAux[Meal, D <: DietaryRequirement, Mod](implicit ev: Mod <:< Meal): Aux[Meal, D, Mod] = null` `implicit val veganPizzaModifiedMeal: ModifiedMeal.Aux[Pizza, Vegan, CheeselessPizza] = mkAux` – Dmytro Mitin Oct 06 '18 at 10:01
  • 1
    I'm not sure I understand why you think that we loose information about `Mod <: Meal`. I guess we don't, we just check it not via type inference but via implicit resolution. – Dmytro Mitin Oct 06 '18 at 10:02
  • The compiler has lost information, I think. `Mod <: Meal` implies `Mod <:< Meal`, but the implication does not go both ways. (I have tried, I got weird failures). If you have a further typeclass to include in the chain inside `dishOfTheDayModification` which depends on inheritance rather than `<:<` you would also have to change this one. This would not necessarily be possible in all cases. – Gesar Oct 06 '18 at 10:18
  • If we had some typeclass though which took a `A <:< B` and generated an inner-Aux type `C <: B` where `C =:= A`, we would have re-constructed the `<:` relationship and I THINK it would bypass the weird inheritance problem in my original question, in combination with your solution. However I failed in writing such a typeclass – Gesar Oct 06 '18 at 10:19
  • 1
    Do you mean this type class https://gist.github.com/DmytroMitin/03e3dd24fe5b0241eb62b34452dbb9bd ? – Dmytro Mitin Oct 06 '18 at 10:56
  • That looks to be exactly what I was trying to do. Thank you very much, I'll try plugging it in to my problem – Gesar Oct 06 '18 at 12:33
  • Actually I found the way to fix your original version of code. In `dishOfTheDayModification` replace `implicit d: DishOfTheDay[Meal], impl: ModifiedMeal.Aux[Meal, Req, Mod]` with `implicit impl: ModifiedMeal.Aux[Meal, Req, Mod], d: DishOfTheDay[Meal]`. The order of implicits is significant. – Dmytro Mitin Oct 06 '18 at 12:51
  • When you debug implicits switch on `scalacOptions += "-Xlog-implicits"` in `build.sbt`. The warning was: `Information:ModifiedMeal.veganPizzaModifiedMeal is not a valid implicit value for ModifiedMeal.Aux[Pizza,Vegan,Mod] because: type parameters weren't correctly instantiated outside of the implicit tree: inferred type arguments [ModifiedMeal.veganPizzaModifiedMeal.Mod] do not conform to method dishOfTheDayModification's type parameter bounds [Mod <: Meal]`. – Dmytro Mitin Oct 06 '18 at 12:53
  • 1
    Unfortunately swapping the implicit order does not work if there is more than one meal modification (ie, PotRoast and NutRoast as the vegan version, to continue with the pattern). The dish of the day has to go first to fix `Meal`. I have just discovered though that the original code compiles in scala 2.13.0-M3 (though not M4 or M5) so I'll be hanging out in M3 for a while :) – Gesar Oct 06 '18 at 14:55
  • https://stackoverflow.com/questions/75762318/in-scala-3-is-it-possible-to-make-covariant-contravariant-type-constructor-to-h – Dmytro Mitin Mar 17 '23 at 16:25
0

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.

osxhacker
  • 121
  • 1
  • 3
  • 1
    Unfortunately this fails if there are multiple `ModifiedMeal.Aux` instances. Ie, another instance with type `ModifiedMeal.Aux[PotRoast, Vegan, NutRoast]` causes failure – Gesar Oct 06 '18 at 15:29
  • Assuming the same general type definitions used in your example, having both a `implicit val veganPizzaModifiedMeal` and `implicit val veganPotRoastModifiedMeal` defined in `object ModifiedMeal` leads to multiple satisfying implicits being available to the compiler when resolving `DishOfTheDayModification.Aux[Req, Mod]`. I'd recommend a type-class approach to resolve the ambiguity if possible. – osxhacker Oct 06 '18 at 15:50