StandardML의 세트 집합에 충돌이 발생하는 문제

Question

온라인 도서 "전산 범주 이론"http://www.cs.man.ac.uk/~david/categories/book/book.pdf을 잘 읽고 있는데이 책의 2.10 문제점에 몇 가지 문제가 있습니다. 특히, 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 

:

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에 대한 답변에서 주어진다 정수들의 집합? 내가 뭔가 잘못하고 있는거야?

Answer 1

문제는 세트의 카디널리티를 계산하는 방법에 있습니다.

집합의 카디널리티를 계산하려면 각 요소를 살펴보고 동일한 요소의 모든 추가 항목을 제거하고 각 제거에 대해 개수를 하나씩 늘리십시오.

특히 "동일한 요소의 모든 추가 발생"부분은 실패한 부분입니다.

유형이 동등 유형이므로 두 정수를 비교하여 동일한 정수인지 확인하십시오. 그러나 int Set 유형은 동등 유형이 아닙니다. 즉, int Set을 비교할 수 없기 때문에 list_remove 호출이 작동하지 않습니다.

왜 이런 질문을 할 수 있습니까? 음, 다음 사항을 고려 :

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

이 두 세트 모두 동일한 집합을 표현하지만 내부 표현이 다른 : 허용 된 경우

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

따라서, 표준 항등 연산자는 이들에 직접 작업, 당신은 그들이 같은 세트를 대표한다고해도 그들은 다를 것이라고 생각할 것입니다. 그건 좋지 않아.

이 문제를 해결하는 한 가지 방법은 집합 연산의 결과를 반환 할 때마다 집합이 항상 "표준 표현"으로 표현되도록하는 것입니다. 그러나 이것이 일반적으로 할 수 있는지 확실하지 않습니다.