El compilador de Scala no puede inferir el tipo de mezcla para la coincidencia de patrones

Question

Tengo un caso de uso para grupos algebraicos sobre conjuntos de permutación finitos. Como me gustaría usar el grupo para varias clases de permutación que de otra manera no están relacionadas, me gustaría hacer esto como un rasgo de mezcla. He aquí un extracto de mi intento

trait Permutation[P <: Permutation[P]] { this: P => 
    def +(that: P): P 

    //final override def equals(that: Any) = ... 
    //final override lazy val hashCode = ... 

    // Lots of other stuff 
} 

object Permutation { 
    trait Sum[P <: Permutation[P]] extends Permutation[P] { this: P => 
    val perm1, perm2: P 

    // Lots of other stuff 
    } 

    private object Sum { 
    def unapply[P <: Permutation[P]](s: Sum[P]): Some[(P, P)] = Some(s.perm1, s.perm2) 
    //def unapply(s: Sum[_ <: Permutation[_]]): Some[(Permutation[_], Permutation[_])] = Some(s.perm1, s.perm2) 
    } 

    private def simplify[P <: Permutation[P]](p: P): P = { 
    p match { 
     case Sum(a, Sum(b, c)) => simplify(simplify(a + b) + c) 

     // Lots of other rules 

     case _ => p 
    } 
    } 
} 

En algún momento en el tiempo, me gustaría llamar al método simplificar el fin de, así, simplificar una expresión de las operaciones del grupo utilizando los axiomas algebraicos. Usar la coincidencia de patrones parece tener sentido ya que hay muchos axiomas que evaluar y la sintaxis es concisa. Sin embargo, si puedo compilar el código, me sale:

error: inferred type arguments [P] do not conform to method unapply's type parameter bounds [P <: Permutation[P]] 

No entiendo por qué el compilador no puede deducir el tipo correcto y no saber cómo ayudar a él. En realidad, el tipo de parámetro de P es irrelevante cuando se combinan patrones en este caso. Si p es cualquier suma de permutaciones, el patrón debe coincidir. El tipo de retorno sigue siendo una P porque la transformación se realiza únicamente llamando al operador + en P.

Así que en un segundo intento cambio la versión comentada de una aplicación. Sin embargo, a continuación, me sale un error de aserción del compilador (2.8.2):

assertion failed: Sum((a @ _), (b @ _)) ==> Permutation.Sum.unapply(<unapply-selector>) <unapply> ((a @ _), (b @ _)), pt = Permutation[?>: Nothing <: Any] 

Alguna pista de cómo puedo hacer que el compilador acepta esto?

¡Gracias de antemano!

Answer 1

Después de criar esto durante dos días, finalmente encontré una solución que se compila sin previo aviso y pasa mi prueba de especificación. Lo que sigue es un fragmento compilable de mi código para mostrar lo que se requiere. Tenga en cuenta sin embargo, que el código es un no-op porque he dejado de lado las partes para llevar a cabo realmente las permutaciones:

/** 
* A generic mix-in for permutations. 
* <p> 
* The <code>+</code> operator (and the apply function) is defined as the 
* concatenation of this permutation and another permutation. 
* This operator is called the group operator because it forms an algebraic 
* group on the set of all moves. 
* Note that this group is not abelian, that is the group operator is not 
* commutative. 
* <p> 
* The <code>*</code> operator is the concatenation of a move with itself for 
* <code>n</code> times, where <code>n</code> is an integer. 
* This operator is called the scalar operator because the following subset(!) 
* of the axioms for an algebraic module apply to it: 
* <ul> 
* <li>the operation is associative, 
*  that is (a*x)*y = a*(x*y) 
*  for any move a and any integers x and y. 
* <li>the operation is a group homomorphism from integers to moves, 
*  that is a*(x+y) = a*x + a*y 
*  for any move a and any integers x and y. 
* <li>the operation has one as its neutral element, 
*  that is a*1 = m for any move a. 
* </ul> 
* 
* @param <P> The target type which represents the permutation resulting from 
*  mixing in this trait. 
* @see Move3Spec for details of the specification. 
*/ 
trait Permutation[P <: Permutation[P]] { this: P => 
    def identity: P 

    def *(that: Int): P 
    def +(that: P): P 
    def unary_- : P 

    final def -(that: P) = this + -that 
    final def unary_+ = this 

    def simplify = this 

    /** Succeeds iff `that` is another permutation with an equivalent sequence. */ 
    /*final*/ override def equals(that: Any): Boolean // = code omitted 
    /** Is consistent with equals. */ 
    /*final*/ override def hashCode: Int // = code omitted 

    // Lots of other stuff: The term string, the permutation sequence, the order etc. 
} 

object Permutation { 
    trait Identity[P <: Permutation[P]] extends Permutation[P] { this: P => 
    final override def identity = this 

    // Lots of other stuff. 
    } 

    trait Product[P <: Permutation[P]] extends Permutation[P] { this: P => 
    val perm: P 
    val scalar: Int 

    final override lazy val simplify = simplifyTop(perm.simplify * scalar) 

    // Lots of other stuff. 
    } 

    trait Sum[P <: Permutation[P]] extends Permutation[P] { this: P => 
    val perm1, perm2: P 

    final override lazy val simplify = simplifyTop(perm1.simplify + perm2.simplify) 

    // Lots of other stuff. 
    } 

    trait Inverse[P <: Permutation[P]] extends Permutation[P] { this: P => 
    val perm: P 

    final override lazy val simplify = simplifyTop(-perm.simplify) 

    // Lots of other stuff. 
    } 

    private def simplifyTop[P <: Permutation[P]](p: P): P = { 
    // This is the prelude required to make the extraction work. 
    type Pr = Product[_ <: P] 
    type Su = Sum[_ <: P] 
    type In = Inverse[_ <: P] 
    object Pr { def unapply(p: Pr) = Some(p.perm, p.scalar) } 
    object Su { def unapply(s: Su) = Some(s.perm1, s.perm2) } 
    object In { def unapply(i: In) = Some(i.perm) } 
    import Permutation.{simplifyTop => s} 

    // Finally, here comes the pattern matching and the transformation of the 
    // composed permutation term. 
    // See how expressive and concise the code is - this is where Scala really 
    // shines! 
    p match { 
     case Pr(Pr(a, x), y) => s(a*(x*y)) 
     case Su(Pr(a, x), Pr(b, y)) if a == b => s(a*(x + y)) 
     case Su(a, Su(b, c)) => s(s(a + b) + c) 
     case In(Pr(a, x)) => s(s(-a)*x) 
     case In(a) if a == a.identity => a.identity 
     // Lots of other rules 

     case _ => p 
    } 
    } ensuring (_ == p) 

    // Lots of other stuff 
} 

/** Here's a simple application of the mix-in. */ 
class Foo extends Permutation[Foo] { 
    import Foo._ 

    def identity: Foo = Identity 
    def *(that: Int): Foo = new Product(this, that) 
    def +(that: Foo): Foo = new Sum(this, that) 
    lazy val unary_- : Foo = new Inverse(this) 

    // Lots of other stuff 
} 

object Foo { 
    private object Identity 
    extends Foo with Permutation.Identity[Foo] 

    private class Product(val perm: Foo, val scalar: Int) 
    extends Foo with Permutation.Product[Foo] 

    private class Sum(val perm1: Foo, val perm2: Foo) 
    extends Foo with Permutation.Sum[Foo] 

    private class Inverse(val perm: Foo) 
    extends Foo with Permutation.Inverse[Foo] 

    // Lots of other stuff 
} 

Como se puede ver, la solución es definir los tipos y objetos extractores que son locales a la Método simplifyTop.

También he incluido un pequeño ejemplo de cómo aplicar tal mezcla en la clase Foo. Como puede ver, Foo es poco más que una fábrica de permutaciones compuestas de su propio tipo. Eso es un gran beneficio si tienes muchas clases como esta que de otra manera no están relacionadas.

<diatriba>

Sin embargo, no me resisto a decir que el sistema de tipo de Scala es increíblemente compleja! Soy un experimentado desarrollador de bibliotecas Java y me siento muy hábil con Java Generics. Sin embargo, me llevó dos días descubrir las seis líneas de código con las tres definiciones de tipo y objeto. Si esto no fuera por propósitos educativos, habría abandonado el enfoque.

En este momento, tengo la tentación de pensar que Scala NO será la próxima gran cosa en términos de lenguajes de programación debido a esta complejidad. Si usted es un desarrollador de Java que se siente un poco incómodo con los genéricos de Java ahora (no yo), odiaría el sistema de tipos de Scala porque agrega invariantes, covariantes y contravariantes al concepto de genéricos de Java, por decir lo menos.

En general, el sistema de tipo de Scala parece dirigirse a más científicos que desarrolladores. Desde un punto de vista científico, es bueno razonar sobre el tipo de seguridad de un programa. Desde el punto de vista de los desarrolladores, el tiempo para descubrir estos detalles se desperdicia porque los mantiene alejados de los aspectos funcionales del programa.

No importa, continuaré con Scala con seguridad. La combinación de combinación de patrones, mezclas y funciones de alto orden es demasiado poderosa para perderse. Sin embargo, creo que Scala sería un lenguaje mucho más productivo sin su sistema de tipos demasiado complejo.

</diatriba >