0

我正在阅读在线书籍“计算类别理论” http://www.cs.man.ac.uk/~david/categories/book/book.pdf，我在这本书的问题 2.10 上遇到了一些问题。特别是，与幂集的定义。

abstype 'a Set = set of 'a list
  with val emptyset = set([])
    fun is_empty(set(s)) = length(s)=0
    fun singleton(x) = set([x])
    fun disjoint_union(set(s),set(nil))=set(s) | 
      disjoint_union(set(s),set(t::y))=
      if list_member(t,s) then disjoint_union(set(s),set(y)) 
      else disjoint_union(set(t::s),set(y))
    fun union(set(s),set(t)) = set(append(s,t))
    fun member(x,set(l)) = list_member(x,l)
    fun remove(x,set(l)) = set(list_remove(x,l))
    fun singleton_split(set(nil)) = raise empty_set
      | singleton_split(set(x::s)) =(x,remove(x,set(s)))
    fun split(s) = let val (x,s') = singleton_split(s) in (singleton(x),s') end
    fun cardinality(s) = if is_empty(s) then 0 else
      let val (x,s') = singleton_split(s) in 1 + cardinality(s') end
    fun image(f)(s) = if is_empty(s) then emptyset else
      let val (x,s') = singleton_split(s) in
      union(singleton(f(x)),image(f)(s')) end
    fun display(s)= if is_empty(s) then [] else
      let val (x,s') = singleton_split(s) in x::display(s') end
    fun cartesian(set(nil),set(b))=emptyset | 
      cartesian(set(a),set(b)) = let val (x,s') = singleton_split(set(a)) 
      in union(image(fn xx => (x,xx))(set(b)),cartesian(s',set(b))) end
    fun powerset(s) = 
      if is_empty(s) then singleton(emptyset) 
      else let 
      val (x,s') = singleton_split(s) 
      val ps'' = powerset(s') 
      in union(image(fn t => union(singleton(x),t))(ps''),ps'') end
end

powerset 函数来自附录 D 中的答案。然后我创建了一个集合的 powerset：

val someset=singleton(3); (*corresponds to the set {3}*)
val powerset=powerset(someset); (* should result in {{},{3}} *)
val cardinality(someset); (*returns 1*)
val cardinality(powerset); (*throws an error*)

! Type clash: expression of type
!    int Set Set
! cannot have type
!    ''a Set

为什么我可以计算一组整数的基数，而不是一组整数的基数？难道我做错了什么？

4

1 回答 1

0

问题在于如何计算集合的基数。

为了计算集合的基数，您遍历每个元素，删除它以及相同元素的所有进一步出现，每次删除时将计数增加一。

特别是，“以及同一元素的所有进一步出现”部分是失败的。

该int类型是相等类型，因此在这种情况下比较两个整数以查看它们是否相同效果很好。

但是，该int Set类型不是相等类型。这意味着，list_remove调用将不起作用，因为它无法比较两个int Sets。

为什么会这样，你可能会问？好吧，考虑以下几点：

val onlythree = singleton 3; (* {3} *)
val onlythree_2 = union (onlythree, onlythree); (* {3} U {3} = {3} *)

这两个集合都代表同一个集合，但是内部表示不同：

onlythree   = set [3]
onlythree_2 = set [3, 3]

因此，如果您允许标准相等运算符直接处理这些，您会发现它们会有所不同，即使它们代表相同的集合。那不好。

解决此问题的一种方法是确保无论何时从集合操作返回结果，集合始终由其“规范表示”表示。但是，我不确定这是否可以做到。

于 2011-08-08T20:11:41.143 回答