Scala编译器无法推断模式匹配的混合类型 [英] Scala compiler cannot infer mix-in type for pattern matching

问题描述

我有一个关于有限置换集上的代数群的用例.因为我想将该组用于本来就不相关的各种排列类，所以我希望以此作为混合特性.这是我的尝试摘录

I have a use case for algebraic groups over finite permutation sets. Because I would like to use the group for various permutation classes which are otherwise unrelated, I would like to do this as a mix-in trait. Here's an excerpt of 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
    }
  }
}

在某个时间点，我想调用simple方法，以便使用代数公理简化组运算的表达式.使用模式匹配似乎很有意义，因为有许多要评估的公理且语法简洁.但是，如果我编译代码，则会得到:

At some point in time, I would like to call the simplify method in order to, well, simplify an expression of group operations using the algebraic axioms. Using pattern matching seems to make sense as there are a lot of axioms 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's type parameter bounds [P <: Permutation[P]]

我不明白为什么编译器无法正确推断类型，也不知道如何提供帮助.实际上，在这种情况下，与模式匹配时，P的参数类型无关紧要.如果p是任何排列总和，则模式应匹配.返回类型仍然是P，因为转换完全是通过在P上调用+运算符完成的.

I do not understand why the compiler cannot infer the type correctly and I don't know how to help it. Actually, the parameter type of P is irrelevant when pattern matching in this case. If p is any Sum of permutations, the pattern should match. The return type is still a P because the transformation is solely done by calling the + operator on P.

因此，在第二次尝试中，我换成了未应用的注释掉版本.但是，然后我从编译器(2.8.2)中收到一个断言错误:

So in a second attempt I swap in the commented out version of unapply. However, then 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 clues how I can make the compiler accept this?

提前谢谢！

推荐答案

经过两天的繁殖，我终于找到了一个无需警告即可编译并通过我的规格测试的解决方案.以下是我的代码的可摘录片段，以显示所需内容.但是请注意，该代码是禁止操作的，因为我省略了实际执行排列的部分:

After breeding over this for two days, I have finally found a solution which compiles without warning and passes my specification test. Following is a compilable excerpt of my code to show what is required. Note however, that the code is a no-op because I have left out the parts to actually 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'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
}

如您所见，解决方案是定义对simpleTop方法本地的类型和提取器对象.

As you can see, the solution is to define types and extractor objects which are local to the simplifyTop method.

我还提供了一个有关如何将此类混入应用于Foo类的小例子.如您所见，Foo只是一个用于构造自己类型的组合排列的工厂.如果您有很多这样的类，这些类本来是不相关的，那将是一个很大的好处.

I have also included a little example of how to apply such a mix-in to the class Foo. As you can see, Foo is little more than a factory for composed permutations of its own type. That's a big benefit if you have many classes like this which are otherwise unrelated.

< rant>

<rant>

但是，我不能拒绝说Scala的类型系统非常复杂！我是一位经验丰富的Java库开发人员，并且对Java泛型非常精通.然而，我花了两天的时间才弄清了具有三种类型和对象定义的六行代码！如果这不是出于教育目的，我会放弃这种方法.

However, I cannot resist to say that Scala's type system is insanely complex! I'm a seasoned Java library developer and feel very proficient with Java Generics. Yet it took me two days to figure out the six lines of code with the three type and object definitions! If this were not for educational purposes, I would have ditched the approach.

现在，我很想知道，由于这种复杂性，Scala不会成为编程语言的下一件大事.如果您是现在对Java泛型感到不舒服的Java开发人员(不是我)，那么您会讨厌Scala的类型系统，因为它至少在Java泛型概念中增加了不变量，协变量和对变量.

Right now, I am tempted to 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 about Java generics now (not me), then you would hate Scala's type system because it adds invariants, covariants and contravariants to the concept of Java generics, to say the least.

总的来说，Scala的类型系统似乎比开发人员涉及更多的科学家.从科学的角度来看，可以很好地推断出程序的类型安全性.从开发人员的角度来看，浪费这些细节的时间是因为它使它们远离程序的功能方面.

All-in-all, Scala's type system seems to address more scientists than developers. From a scientific point of view, it's nice to reason about the type safety of a program. From a developers point of view, the time to figure out these details is wasted because it keeps them away from the functional aspects of the program.

没关系，我肯定会继续使用Scala.模式匹配，混入和高阶功能的组合实在太强大了，不容错过.但是，如果没有过于复杂的类型系统，我觉得Scala将会是一种生产力更高的语言.

Nevermind, I will continue with Scala for sure. The combination of pattern matching, mix-ins and high-order functions is just too powerful to miss. However, I feel Scala would be a much more productive language without it's overly complex type system.

</rant>

</rant>

这篇关于Scala编译器无法推断模式匹配的混合类型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！