Scala compiler cannot infer insert type to match pattern

Question

I have a precedent for algebraic groups over finite sets of permutations. Since I would like to use the group for various classes of permutations that would otherwise not be related to each other, I would like to do this as a sign of confusion. Here is an excerpt from my attempt

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 } } } 

At some point in time, I would like to call a simplification method to simplify the expression of group operations using algebraic axioms. Using pattern matching seems to make sense, since there are many axioms that need to be evaluated, and the syntax is concise. However, if I compile the code, I get:

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

I don’t understand why the compiler cannot deduce the type correctly, and I don’t know how to help it. In fact, the type of the parameter P does not matter when matching patterns in this case. If p is any Sum of permutations, the pattern must match. The return type is still P because the conversion is done exclusively by calling the + operator on P.

So, in the second attempt, I replace the missing version with unapply. However, after this, I get an assertion error from the compiler (2.8.2):

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

Any hints how can I get the compiler to accept this?

Thanks in advance!

Answer 1

After breeding for two days, I finally found a solution that compiles without warning and passes my specification test. Below is a compilation excerpt from my code to show what is required. Note, however, that the code is no-op because I did not use parts to perform the permutations:

 /** * 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 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 } 

As you can see, the solution is to determine the types and objects of the extractor that are local to the simplifyTop method.

I also included a small example of how to apply such a mix to the Foo class. As you can see, Foo is a little more than a factory for compound permutations of its type. This is a big benefit if you have many classes that are otherwise unrelated.

pompous

However, I can’t help but say that a system like Scala is insanely complicated! I am an experienced Java library developer and very good at Java Generics. However, it took me two days to figure out six lines of code with three definitions of types and objects! If it were not for educational purposes, I would give up this approach.

I am currently tempted by the oracle that Scala will NOT be the next big thing in terms of programming languages ​​because of this complexity. If you are a Java developer who feels a little uncomfortable with Java generics now (and not me), then you will hate a system like Scala because it adds invariants, covariants and contravariants to the concept of Java generics, to say the least.

An all-in-one system, Scala seems to concern more scientists than developers. From a scientific point of view, it's nice to talk about the type of program security. From the point of view of developers, the time taken to clarify these details is wasted because it keeps them from the functional aspects of the program.

Nevermind, I will continue with Scala for sure. The combination of pattern matching, mixing, and high-order features is just too strong to miss. However, I feel that Scala will be a much more productive language without an overly complex type system.

</ & bombastic GT;