0

私はオンラインブック "Computational Category Theory" 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

パワーセット関数は、付録 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

整数のセットの基数を計算できるのに、整数のセットの基数を計算できないのはなぜですか? 私は何か間違ったことをしていますか？

4

1 に答える 1

0

問題は、セットのカーディナリティをどのように数えるかにあります。

セットのカーディナリティを数えるには、各要素を調べて、それを削除するだけでなく、同じ要素のそれ以降のすべての出現を削除し、そのような削除ごとにカウントを 1 増やします。

特に、「同じ要素のそれ以降のすべての出現と同様に」の部分が失敗しています。

型は等価型なので、そのint場合は 2 つの整数を比較して同じかどうかを確認するとうまくいきます。

ただし、int Set型は等価型ではありません。これは、list_remove2 つの を比較できないため、呼び出しが機能しないことを意味しint Setます。

これはなぜですか？さて、次のことを考慮してください。

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

これら 2 つのセットは両方とも同じセットを表しますが、内部表現は異なります。

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

したがって、標準の等価演算子をこれらに直接作用させると、同じセットを表しているにもかかわらず、それらが異なることがわかります。それは良くないね。

これを改善する 1 つの方法は、セット操作から結果を返すときはいつでも、セットが常にその「正規表現」によって表されるようにすることです。ただし、これが一般的に可能かどうかはわかりません。

于 2011-08-08T20:11:41.143 に答える