Type class and dependent types

Question

First off, I don't know how to properly label my problem. This might also be the reason why I didn't find helpful resources. Any hints are highly appreciated.

trait Context[T]
{
    self =>

    trait Rule
    {
        def apply( value: T ): Boolean
    }

    implicit class RichRule[A <: Rule]( a: A )
    {
        def and[B <: Rule]( b: B ): and[A, B] = self.and( a, b )
        def or[B <: Rule]( b: B ): or[A, B] = self.or( a, b )
    }

    sealed trait Group[A <: Rule, B <: Rule] extends Rule
    {
        def a: A

        def b: B

        override def apply( value: T ) = ???
    }

    case class and[A <: Rule, B <: Rule]( a: A, b: B ) extends Group[A, B]
    case class or[A <: Rule, B <: Rule]( a: A, b: B ) extends Group[A, B]
}

Given the above code, I can now define and chain Ruless in this fashion:

new Context[String]
{
    class MyRule extends Rule
    {
        override def apply( value: String ) = true
    }

    case class A() extends MyRule
    case class B() extends MyRule

    val x1: A and B or A = A() and B() or A()
}

This works as I intended but now comes the tricky part. I want to introduce a Type Class Combination that explains how to join two rules.

trait Combination[-A <: Rule, -B <: Rule]
{
    type Result <: Rule

    def combine( a: A, b: B ): Result
}
trait AndCombination[-A <: Rule, -B <: Rule] extends Combination[A, B]
trait OrCombination[-A <: Rule, -B <: Rule] extends Combination[A, B]

This Type Class should now be passed with the operators.

implicit class RichRule[A <: Rule]( a: A )
{
    def and[B <: Rule]( b: B )( implicit c: AndCombination[A, B] ): and[A, B] = ???
    def or[B <: Rule]( b: B )( implicit c: OrCombination[A, B] ): or[A, B] = self.or( a, b )
}

Which is still working after some tweaks.

implicit val c1 = new Combination[MyRule, MyRule]
{
    type Result = MyRule

    def combine( a: A, b: B ): MyRule = a
}

val x: A and B = A() and B()

But if it gets more complicated, things are falling apart.

A() and B() and A()

Will raise an implicit missing error: Combination[and[A, B], A] is missing. But I want it to use the result of the implicit combination of and[A, B] (type Result = MyRule) which it already knows how to handle (Combination[and[A, B]#Result, A]).

It is important for me to keep the type information of combined rules val x: A and B or A, folding them together to a final result type is easy, but not what I want.

This is as close as I could get, it fails compilation, though.

trait Context[T]
{
    self =>

    trait Rule

    trait Value extends Rule

    trait Group[A <: Rule, B <: Rule] extends Rule
    {
        def a: A

        def b: B

        implicit val resolver: Resolver[_ <: Group[A, B]]
    }

    case class and[A <: Rule, B <: Rule]( a: A, b: B )( implicit val resolver: Resolver[and[A, B]] ) extends Group[A, B]

    implicit class RichRule[A <: Rule]( a: A )
    {
        def and[B <: Rule]( b: B )( implicit resolver: Resolver[and[A, B]] ) = self.and[A, B]( a, b )
    }

    trait Resolver[-A <: Rule]
    {
        type R <: Value

        def resolve( a: A ): R
    }
}

object O extends Context[String]
{
    implicit val c1 = new Resolver[A and A]
    {
        override type R = A

        override def resolve( a: O.and[A, A] ) = ???
    }

    implicit def c2[A <: Value, B <: Value, C <: Value]( implicit r1: Resolver[A and B] ) = new Resolver[A and B and C]
    {
        override type R = C

        override def resolve( a: A and B and C ): C =
        {
            val x: r1.R = r1.resolve( a.a )
            new c2( x )
            ???
        }
    }

    class c2[A <: Value, B <: Value]( val a: A )( implicit r2: Resolver[A and B] ) extends Resolver[A and B]
    {
        override type R = B

        override def resolve( a: O.and[A, B] ) = a.b
    }

    case class A() extends Value

    val x: A and A and A = A() and A() and A()
}

Answer 1

The reason while your code can't compile is that at the instruction

 new c2( x )

The compiler need to resolve a implicit r2: Resolver[A and B] from x and the only type information available is the type of x, which is r1.R.

This sort of problems requires making more type information available to the compiler and adding some implicit parameter. When you require a Resolver[A and B], you can't use its R type to resolve another Resolver[r1.R and C].

type ResolverAux[-A<:Rule,B] = Resolver[A] { type R = B }

With this available, you can rewrite the signature of your c2

implicit def c2[A <: Value, B <: Value, C <: Value,D<:Value]( implicit r1: ResolverAux[A and B,D], r2:Resolver[D and C] ):Resolver[A and B and C] = new Resolver[A and B and C]
  {
    override type R = C

    override def resolve( a: A and B and C ): C =
    {
      val x: r1.R = r1.resolve( a.a )
      new c2[r1.R,C]( x )
      ???
    }
  }

Notice that by using the type alias and introducing an additional generic parameter, I can express the relation r1.R1 = D which is then used to resolve the second implicit r2