有选择地禁用 Scala 中的包含吗？ （正确输入 List.contains）

Question

List("a").contains(5)

由于 Int 永远不能包含在 String 列表中，因此应该在编译时生成错误，但事实并非如此。

它浪费且默默地测试列表中包含的每个 String 是否等于 5，这永远不可能是真的（"5" 永远不等于 >5（Scala 中）。

此问题被命名为““包含”问题”。并且一些暗示如果类型系统无法正确键入此类语义，那么为什么要花费额外的精力来强制类型呢？所以我认为这是一个需要解决的重要问题。

List.contains 的类型参数化 B >: A 输入任何类型，该类型是类型 A 的超类型（元素的类型）包含在列表中）。

trait List[+A] {
   def contains[B >: A](x: B): Boolean
}

这种类型参数化是必要的，因为 +A 声明列表是 类型 A 上的协变，因此 A 不能用于逆变位置，即作为输入参数的类型。协变列表（必须是不可变的）对于扩展来说比不变列表更强大（这可以是可变的）。

在上面有问题的示例中，A 是一个 String，但 Int 不是 String 的超类型，所以发生了什么？ Scala 中的隐式包含决定 Any 是 String 和 Int 的共同超类型。

Scala 的创建者 Martin Odersky 建议修复将输入类型 B 限制为仅具有 Any 没有的 equals 方法的类型。

trait List[+A] {
   def contains[B >: A : Eq](x: B): Boolean
}

但这并不能解决问题，因为两种类型（其中输入类型不是列表元素类型的超类型）可能具有共同的超类型，它是 Any 的子类型，即也是 Eq 的子类型。因此，它将正确编译，并且错误类型的语义将保留。

在每个地方禁用隐式包含也不是一个理想的解决方案，因为隐式包含包含是下面的 Any 包含示例起作用的原因。当接收站点（例如作为函数参数传递）具有正确类型化的共同超类型语义（甚至可能不是 Any）时，我们不希望被迫使用类型转换。

trait List[+A] {
   def ::[B >: A](x: B): List[B]
}

val x : List[Any] = List("a", 5) // see[1]

[1] List.apply 调用 :: 运算符。

所以我的问题是解决这个问题的最佳方法是什么？

我的初步结论是，应该在定义站点上关闭隐式包含，否则语义将无法正确键入。我将提供一个答案，展示如何在方法定义站点关闭隐式包含。有替代解决方案吗？

请注意，这个问题是普遍存在的，并不是孤立的列表问题。

更新：我已提交了改进请求并且发起了一个关于此问题的 scala 讨论帖。我还在 Kim Stebel 和 Peter Schmitz 的答案下添加了评论，表明他们的答案具有错误的功能。因此没有解决办法。同样在上述讨论线程中，我解释了为什么我认为 soc 的答案不正确。

Answer 1

这在理论上听起来不错，但在我看来在现实生活中却行不通。

equals 不是基于类型的，而 contains 是建立在类型之上的。

这就是为什么像 1 == BigInt(1) 这样的代码可以工作并返回大多数人期望的结果。

在我看来，让 contains 比 equals 更严格是没有意义的。

如果 contains 变得更加严格，像 List[BigInt](1,2,3) contains 1 这样的代码将完全停止工作。

顺便说一句，我认为“不安全”或“类型不安全”在这里不是正确的术语。

Answer 2

为什么不使用相等类型类？

scala> val l = List(1,2,3)
l: List[Int] = List(1, 2, 3)

scala> class EQ[A](a1:A) { def ===(a2:A) = a1 == a2 } 
defined class EQ

scala> implicit def toEQ[A](a1:A) = new EQ(a1)
toEQ: [A](a1: A)EQ[A]

scala> l exists (1===)
res7: Boolean = true

scala> l exists ("1"===)
<console>:14: error: type mismatch;
 found   : java.lang.String => Boolean
 required: Int => Boolean
              l exists ("1"===)
                           ^

scala> List("1","2")
res9: List[java.lang.String] = List(1, 2)

scala> res9 exists (1===)
<console>:14: error: type mismatch;
 found   : Int => Boolean
 required: java.lang.String => Boolean
              res9 exists (1===)

Answer 3

我认为你误解了Martin的解决方案，它不是B <: Eq，它是B : Eq，这是

def Contains[B >: A](x: B)(implicit ev: Eq[B])

And Eq[X]< 的缩写/code> 然后将包含一个方法，

def areEqual(a: X, b: X): Boolean

这与将 Any 的 equals 方法移到层次结构中稍低的位置不同，这确实无法解决将其放在 Any 中的任何问题。

Answer 4

在我的库扩展中，我使用：

class TypesafeEquals[A](val a: A) {
  def =*=(x: A): Boolean = a == x
  def =!=(x: A): Boolean = a != x
}
implicit def any2TypesafeEquals[A](a: A) = new TypesafeEquals(a)


class RichSeq[A](val seq: Seq[A]) { 
  ...
  def containsSafely(a: A): Boolean = seq exists (a =*=)
  ...
}
implicit def seq2RichSeq[A](s: Seq[A]) = new RichSeq(s)

所以我避免调用 contains。

Answer 5

这些示例使用 L 而不是 List 或 SeqLike，因为此解决方案要应用于预先存在的 contains 方法这些集合，需要更改现有的库代码。目标之一是实现平等的最佳方式，而不是与当前库互操作的最佳折衷方案（尽管需要考虑向后兼容性）。此外，我的另一个目标是这个答案通常适用于任何出于任何原因想要选择性禁用 Scala 编译器的隐式包含功能的方法函数，不一定与相等语义相关。

case class L[+A]( elem: A )
{
   def contains[B](x: B)(implicit ev: A <:< B) = elem == x
}

上面的代码会根据需要生成错误，假设 List.contains 所需的语义是输入应等于所包含元素的和超类型。

L("a").contains(5)
error: could not find implicit value for parameter ev: <:<[java.lang.String,Int]
       L("a").contains(5)
                      ^

当不需要隐式包含时，不会生成错误。

scala> L("a").contains(5 : Any)
defined class L

scala> L("a").contains("")
defined class L

这通过要求输入参数类型 B 与作为输入传递的参数类型相同（即不能隐式包含 A< /code>），然后分别需要隐式证据证明B是a，或者具有隐式可归纳的, 超类型A.]

---

更新2012年5月3日：上面的代码并不完整，如下所示，在方法定义站点关闭所有包含并没有给出所需的结果结果。

class Super
defined class Super
class Sub extends Super
defined class Sub

L(new Sub).contains(new Super)
defined class L

L(new Super).contains(new Sub)
error: could not find implicit value for parameter ev: <:<[Super,Sub]
       L(new Super).contains(new Sub)
                            ^

获得所需形式的包容的唯一方法是也在方法（调用）使用站点进行强制转换。

L(new Sub).contains(new Super : Sub)
error: type mismatch;
 found   : Super
 required: Sub
       L(new Sub).contains(new Super : Sub)
                           ^

L(new Super).contains(new Sub : Super)
defined class L

---

根据 soc 的回答，List.contains 的当前语义是输入应该等于，但是不一定是所包含元素的超类型。这假设 List.contains 承诺任何匹配项仅等于并且不需要是输入实例的（子类型或）副本。当前通用的相等接口 Any.equals : Any => Boolean 是统一的，因此相等不会强制执行子类型关系。如果这是 List.contains 所需的语义，则无法使用子类型关系来优化编译时语义，例如禁用隐式包含，并且我们会陷入潜在的语义低效，从而降低运行时性能List.contains 的性能。

虽然我将更多地研究和思考平等和包含，但我的答案对于在方法定义站点有选择地禁用隐式包含的一般目的仍然有效。

我的思考过程也在全面地思考最佳的平等模式。

---

更新：我在soc的回答下面添加了一条评论，所以我现在认为他的观点不相关。平等应始终基于子类型关系，这是 Martin Odersky 所提议的对于新的平等改革（另请参阅他的 包含的版本）。任何临时多态等价（例如BitInt(1) == 1）都可以通过隐式转换来处理。我在下面的评论中解释了didierd的回答，如果没有我下面的改进，afaics Martin提出的contains将会有一个语义错误，相互隐式包含的超类型（Any 除外）将选择错误的 Eq 隐式实例（如果存在，否则会出现不必要的编译器错误）。我的解决方案禁用此方法的隐式包含，这是 Eq.eq 子类型参数的正确语义。

trait Eq[A]
{
   def eq(x: A, y: A) = x == y
}

implicit object EqInt extends Eq[Int]
implicit object EqString extends Eq[String]

case class L[+A]( elem: A )
{
   def contains[B](x: B)(implicit ev: A <:< B, eq: Eq[B]) = eq.eq(x, elem)
}
L("a").contains("")

注意 Eq.eq 可以选择性地替换为隐式对象（不会被覆盖，因为没有虚拟继承，见下文）。

请注意，根据需要，L("a").contains(5 : Any) 不再编译，因为不再使用 Any.equals。

我们可以缩写。

case class L[+A]( elem: A )
{
   def contains[B : Eq](x: B)(implicit ev: A <:< B) = eq.eq(x, elem)
}

---

添加：x == y必须是虚拟继承调用，即x.==应声明override，因为 Eq 类型类中没有没有虚拟继承。类型参数A是不变的（因为A在逆变位置用作Eq.eg的输入参数）。然后我们可以在接口上定义一个隐式对象（又名trait）。

因此，Any.equals 重写仍必须检查输入的具体类型是否匹配。编译器无法消除该开销。

Answer 6

我认为我至少对这里发布的一些问题有一个合法的解决方案 - 我的意思是 List("1").contains(1) 的问题：
https://docs.google.com/document/d/1sC42GKY7WvztXzgWPGDqFukZ0smZFmNnQksD_lJzm20/edit