title: Baking a Scala Cake with shared types
body: <p>I'm trying to build a very general solver system. My goal is to make it easy to mixin different problem spaces (graph coloring, knapsack packing, etc.) with various abstract solvers (branch-and-bound, local search), and various concrete strategies (like the specific "goodness" function). I can sort of make it work with generics, but it's hard to pull together all the configuration into one place. My theory is that a cake and abstract types would be better here.</p>
  
  <p>Consider a Baker who wants to make a cake.</p>
  
  <pre><code>val ingredients: Set[Ingredient] = shopper.shop
  val cake: Cake = baker.bake(ingredients)
  shipper.ship(cake)
  </code></pre>
  
  <p><code>Ingredient</code> and <code>Cake</code> are unknown types, and could be absolutely anything. What we do know is that  shop() returns ingredients, bake() will convert them to a cake, and ship() will accept that cake. I'm trying to do it like this (I'm not certain that I'm using self-types correctly): </p>
  
  <pre><code>override def main(args: Array[String]): Unit = {
    val shopper = new IntShopper
    val baker = new IntBaker
  
    val ingredients = shopper.shop
    val cake = baker.bake(ingredients)
    ...
  }
  
  trait Bakery {
    type Cake
    type Ingredient
    type Recipe &lt;: bakery.Recipe
  }
  
  trait IntBakery extends Bakery {
    override type Recipe = SummingRecipe
    override type Ingredient = Int
    override type Cake = Long
  }
  
  trait Shopper {
    self: Bakery =&gt;
    def shop: Set[Ingredient]
  }
  
  class IntShopper extends Shopper {
    self: IntBakery =&gt;
    override def shop: Set[Ingredient] = Set(1,2,3)
  }
  
  trait Recipe {
    self: Bakery =&gt;
    def combine(is: Set[Ingredient]): Cake
  }
  
  trait Baker {
    self: IntBakery =&gt;
    def bake(ingredients: Set[Ingredient]): Cake = (new Recipe).combine(ingredients)
  }
  
  [...]
  </code></pre>
  
  <p>This is where it breaks down. There are multiple path-dependent versions of <code>Ingredient</code>, and I don't see how I design this so that they're all unified.</p>
  
  <p>My ultimate goal is to be able to mixin several concrete pieces like this:</p>
  
  <pre><code> val shopper = new Shopper with IntShopping with Jeep
   val baker = new Baker with IntBaking with SummingRecipe with WoodfireStove with PlasticSpoon
  </code></pre>
  
  <p>(or more specifically:)</p>
  
  <pre><code> val solver = new Solver with GraphColoring with LocalSearch with ColorReduction with RandomChanges
  </code></pre>
  
  <p>Where Solver needs a problem space (GraphColoring) which needs a solver (LocalSearch) which needs a strategy (ColorReduction) which needs a particular way of creating new state (RandomChanges). It feels like this is what abstract types are for, but I can't quite get there.</p>
  
  <hr>
  
  <p>Regarding @mrhobo's question, it's possible that's the correct way to go, and it's how I do it right now. It just doesn't feel as flexible. I currently have:</p>
  
  <pre><code>trait Solver[InputData, Solution]
  
  trait LocalSearchSolver[InputData, Solution] extends Solver[InputData, Solution] {
    val firstSolver: SingleSolver[InputData, Solution]
    ...
  }
  
  trait GCSolver extends Solver[InputData, Solution]
  
  class GCMaxMinSolver extends GCSolver with LocalSearchSolver[InputData, Solution] {
    override val firstSolver = new GCGreedySolver
  }
  
  class GCGreedySolver extends GCSolver with SingleSolver[InputData, Solution]
  
  trait SingleSolver[InputData, Solution] extends Solver[InputData, Solution]
  </code></pre>
  
  <p>First, there seems a lot of repeated "InputData, Solution", and I can't figure out how to mixin the <code>firstSolver</code>. LocalSearch needs a helper-solver, but other solvers don't. I tried this:</p>
  
  <pre><code>trait LocalSearchSolver[InputData, Solution, FirstSolver &lt;: SingleSolver[InputData, Solution] ] extends Solver[InputData, Solution] {
  </code></pre>
  
  <p>But it complains that it can't resolve FirstSolver for <code>new FirstSolver</code>.</p>
  
  <hr>
  
  <p>Ahh, now I think I'm getting somewhere:</p>
  
  <pre><code>class GCMaxMinSolver(val firstSolver: GCSolver with SingleSolver[InputData, Solution]) 
    extends GCSolver with LocalSearchSolver[InputData, Solution] {
  </code></pre>
  
  <p>Now the mixin looks like:</p>
  
  <pre><code>val solver = new GCMaxMinSolver(new GCGreedySolver)
  </code></pre>
  
  <p>That's not bad, and could be hoisted out into a separate object to capture a full configuration. Maybe this is the right approach.</p>