StandardML中一組套件上類型衝突的問題

Question

我正在閱讀在線書籍「計算分類理論」http://www.cs.man.ac.uk/~david/categories/book/book.pdf，本書中存在問題2.10的一些問題。特別是隨着powerset的定義。

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 

的冪函數是從答案在附錄D我再創建一個集的冪給出：

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 

爲什麼我可以計算一個整數集的基數，但不一組整數？難道我做錯了什麼？

Answer 1

麻煩在於如何計算該集合的基數。

爲了計算集合的基數，可以遍歷每個元素，刪除它以及同一元素的所有更多事件，爲每次刪除都增加一個計數。

特別是，「以及所有進一步發生的同一元素」部分是失敗的。

int類型是一個相等類型，所以在這種情況下，比較兩個整數以查看它們是否相同。但是，int Set類型不是相等類型。這意味着，list_remove呼叫將不起作用，因爲它無法比較兩個int Set s。

爲什麼這樣，你可能會問？那麼，考慮以下因素：

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

這兩組都代表了同一組，但是內部表示有所不同：

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

所以，如果你允許的標準平等的經營者直接在這些工作，你會發現他們會有所不同，即使他們代表了同一組。這不好。

糾正此問題的一種方法可能是確保每當您返回set操作的結果時，set總是由其「規範表示形式」表示。不過，我不確定這是否可以實現。