2

FPコース から：

type Set = Int => Boolean  // Predicate

  /**
   * Indicates whether a set contains a given element.
   */
  def contains(s: Set, elem: Int): Boolean = s(elem)

なぜそれが理にかなっているのですか？

assert(contains(x => true, 100))

基本的にそれが行うことは100、関数に値を提供することx => trueです。つまり、100 を指定するとtrueが返されます。

しかし、これはセットとどのように関連していますか?

何を入れても、 が返されますtrue。その意味はどこにありますか？

提供された値がセット内にある (またはセットでない) という事実を表すパラメーターとして、独自のセットの実装/関数を提供できることを理解しています-(のみ) この実装により、contains関数は何らかの意味/意味/ロジックで満たされます。 /機能。

しかし、これまでのところ、ナンセンスな関数のように見えます。名前が付けられcontainsていますが、名前はロジックを表していません。apply()関数 (第 1 引数) を値 (第 2 引数) に適用するため、これを呼び出すことができます。名前だけでcontains、作者が何を言いたいのかを読者に伝えることができます。抽象的すぎませんか？

4

2 に答える 2

7

上に示したコード スニペットでは、任意のセットは、その特性関数Sと呼ばれるもの、つまり、指定された整数がセットに含まれているかどうかをチェックする関数によって表されます。したがって、そのような特性関数をセットのように考えることができます。つまり、iiSf

{ i| }iであるf iすべての整数true

型が設定された関数Int => Boolean(型シノニムで示されます) を考えた場合、次のようにSet = Int => Boolean記述できます。contains

setfと integeriを指定すると、 が の要素であるcontains(f, i)かどうかをチェックします。if

いくつかの例のセットは、アイデアをより明白にするかもしれません:

Set                                Characeristic Function
 empty set                          x => false
 universal set                      x => true
 set of odd numbers                 x => x % 2 == 1
 set of even numbers                x => x % 2 == 0
 set of numbeers smaller than 10    x => x < 10

例:セット {1, 2, 3} は次のように表すことができます。

val S: Set = (x => 0 <= x && x <= 3)

ある数値がこのセットに含まれているかどうかを知りたい場合nは、次のことができます

contains(S, n)

しかし、もちろん (既に観察したように) 直接実行しても同じ結果が得られます。

S(n)

これは短いですが、前者の方が読みやすいかもしれません (意図がある程度明白であるため)。

于 2013-09-25T05:36:55.887 に答える
2

集合は (数学的にもコンピュータ表現の文脈においても) さまざまな方法で表すことができます。特徴的な関数を使用することは 1 つの可能性です。アイデアは、与えられた普遍集合 U の部分集合 S が関数 f:U-->{true,false} (部分集合の特性関数と呼ばれる) によって完全に決定されるというものです。f(u) を「u は S の要素ですか?」という質問に答えるものとして扱うことができるからです。

セットを表現する特定の選択には、他の方法と比較して利点と欠点があります。特に、一部の表現は、命令型言語よりも関数型言語でモデル化する方が適しています。特性関数としての管理集合と (ソート済みまたは非ソートの) リスト (または配列) としての管理集合を比較すると、たとえば、共用体、積集合、集合差分の作成は、特性関数では非常に効率的ですが、リストではそれほど効率的ではありません。リストを検索するのではなく、特性関数を使用して f(-) を計算するのと同じくらい簡単に、要素の存在を確認できます。ただし、リストを使用するとセット内の要素をすぐに出力できますが、特性関数を使用すると多くの計算が必要になる場合があります。

そうは言っても、基本的な違いは、特性関数を使用すると無限集合をモデル化できるのに対し、配列では不可能であるということです。もちろん、セットは実際には無限ではありませんが、 (x: BigInt) x => (x % 2) == 0 のようなセットは、すべての偶数の整数のセットを真に表し、実際にそれを使用して計算できます (すべての要素を印刷しようとしないでください)。

したがって、すべての表現には長所と短所があります (当然)。

于 2013-09-25T08:21:41.493 に答える