Problem with type clash on a set of sets in StandardML

I am perusing the online book "Computational Category Theory" http://www.cs.man.ac.uk/~david/categories/book/book.pdf and I am having some problems with problem 2.10 in this book. Particularly, with the definition of the 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) =开发者_如何学JAVA 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

The powerset function is given from the answers in Appendix D. I then create the powerset of a set:

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

Why can I calculate the cardinality of a set of integers, but not of a set of sets of integers? Am I doing something wrong?

The trouble lies in how you count the cardinality of the set.

In order to count the cardinality of the set, you go through each element, remove it as well as all further occurrences of the same element, increasing the count by one for each such removal.

In particular, the "as well as all further occurrences of the same element" part is what is failing.

The int type is an equality type, so in that case comparing two integers to see if they're the same works out well.

The int Set type, however, is not an equality type. This means, the list_remove call will not work, as it cannot compare two int Sets.

Why is this, you might ask? Well, consider the following:

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

These two sets both represent the same set, however the internal representations differ:

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

So, if you allowed the standard equality operator to work directly on these, you'd get that they'd be different, even though they represent the same set. That's no good.

One way of remedying this could be ensuring that a set always is represented by its "canonical representation" whenever you return a result from a set operation. I'm not sure if this is possible to do in general, however.