Проблема с типом столкновения на множестве множеств в StandardML - PullRequest
Новая
       12

Проблема с типом столкновения на множестве множеств в StandardML

0 голосов
/ 29 июля 2011

Я просматриваю онлайн книгу "Теория вычислительных категорий" 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

Функция 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

Почему я могу вычислить мощность набора целых чисел, но не набора множеств целых чисел? Я что-то не так делаю?

1 Ответ

0 голосов
/ 09 августа 2011

Беда в том, как вы считаете мощность множества.

Чтобы подсчитать количество элементов множества, вы просматриваете каждый элемент, удаляете его, а также все последующие вхождения того же элемента, увеличивая количество на единицу для каждого такого удаления.

В частности, часть «а также все последующие вхождения того же элемента» - это то, что терпит неудачу.

Тип 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]

Итак, если вы позволите стандартному оператору равенства работать непосредственно с ними, вы получите, что они будут другими, даже если они представляют один и тот же набор. Это не хорошо.

Одним из способов исправить это может быть обеспечение того, чтобы множество всегда представлялось его «каноническим представлением» всякий раз, когда вы возвращаете результат из операции над множеством. Однако я не уверен, что это вообще возможно.

...