在没有可变类型的情况下,是否存在不变类型参数的情况


Java数组不是完全类型安全的,因为它们是协变的:ArrayStoreException可能出现在别名数组上。另一方面,Java集合的类型参数是不变的:例如,List<Thread>不是List<Runnable>的子类型(这可能有点违反直觉)。动机似乎与Lists和其他集合是可变的有关,因此为了保持类型系统的健全,它们的类型参数必须是不变的。

如果一种编程语言只支持不可变的类型,那么类型参数是协变或逆变(但从不不变)的类型系统能工作吗?换句话说,要使用Scala的方差表达方式,可以有List[+E]Function[-T, +R]Map[+K, +V]等。我知道有些较老的语言(例如GNU Sather)似乎只支持协变/逆变参数类型。

我的一般问题是:在一个完全不可变的数据类型的世界里,有没有一种情况会特别需要一个不变的参数类型(而不是协变或反变)?有没有一些不可变数据结构的例子,只有使用不变类型参数才能正确?

所以,每个类型系统要么允许一些不健全的程序,要么禁止一些健全的程序(这是Rice定理的结果),所以一个很好的工作假设是,是的,你提出的任何限制都必然会排除一些原本允许的健全程序。另一方面,人类是无限聪明的,所以从另一个意义上说,答案是否定的:如果你像你描述的那样加上一个狭窄的地方,那没关系,人们会在需要的时候想办法绕过它。(当然,有时他们会想出一个你不喜欢的变通办法,比如放弃你的语言。)

但我认为你真正想要的是一个令人信服的案例:一个现实的例子,在直接支持该例子和坚持你的建议要求所有类型参数都是协变或反变之间做出选择,你的直觉会告诉你放弃该建议,这样你就可以直接支持该示例。

由于您已经确定了类型参数不能协变的各种情况和类型参数不能逆变的各种情况(例如,函数[-t,+R]很好,但反过来则完全不健全),因此一个好的方法是搜索同一类型参数使用两次的情况,一次是以不可能协变的方式,一次是不可能逆变的方式。一个微不足道的例子是UnaryOperator[T]<:函数[T,T],类似于Java的Java.util.Function.UnaryOperator<T> ,其"apply"方法返回的类型与其接受的类型相同。UnaryOperator[String]不能用作UnaryOperator[Object](因为你不能给它传递任意Object),但UnaryOperators[Object]也不能用作Unary Operator[String](因为即使你给它传递String,它也可能返回一些不同的Object)。

对于一个更加充实的现实例子。想象一个二进制搜索树TreeMap[K,+V]<:Map[K,V],类似于Java的Java.util.TreeMap<K、 V>。据推测,我们希望支持诸如"firstKey"、"floorEntry"one_answers"迭代器"等方法(或者至少是其中的一些方法),所以我们不能使K相反:TreeMap[Object,Foo]不能用作TreeMap[String,Foo],因为当我们检索密钥时,密钥可能不是String。

由于它是一个二进制搜索树,它内部需要一个Comparator[K],这立即使K变为协变变得很棘手:如果你使用TreeMap[String,Foo]作为TreeMap[Object,Foo],那么你隐含地使用Comparator[String]作为Comparator[Object],这是不起作用的。现在,由于映射肯定只包含String键,所以"get"方法可能可以通过在使用Comparator[String]调用之前预先检查键的类型来解决这个问题;但"floorEntry"one_answers"ceilingEntry"方法仍然是一个问题:什么条目出现在无法与映射中的键进行比较的任意对象的"之前"或"之后"?

即使你已经说过你的映射是不可变的,你可能仍然想要某种"put"方法,只是一个纯粹的函数方法,它返回映射的修改副本。(纯函数的红黑树支持与可变树相同的不变量和最坏情况下的渐近时间复杂性,所以除了键入system之外,这当然是一件合理的事情。)但是,如果TreeMap[String,Foo]可以用作TreeMap[Object,Foo],那么它的"put"方法需要支持返回一个包含non-String键的二进制搜索树—即使它的Comparator[String]没有定义这样的键的排序。

(在一条评论中,你提到Scala实际上用不变的键类型定义了Map[K,+V]。我从未使用过Scala,但我敢打赌这正是原因。)

相关内容

最新更新