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()因为它的作用是将函数（第一个参数）应用于一个值（第二个参数）。只有名字contains可以告诉读者作者可能想说什么。是不是太抽象了，也许吧？

4

2 回答 2

7

在上面显示的代码片段中，任何集合S都由所谓的特征函数表示，即，给定一些整数的函数i检查是否i包含在集合中S。因此，您可以将这样的特征函数想象成f一个集合，即

{ i| i为}f i的所有整数true

如果您想到任何类型Int => Boolean为 set 的函数（由 type synonym 表示Set = Int => Boolean），那么您可以描述contains为

给定一个集合f和一个整数i，contains(f, i)检查是否i是一个元素f。

一些示例集可能会使这个想法更加明显：

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

集合（在数学上和在计算机表示的上下文中）可以用各种不同的方式表示。使用特征函数是一种可能性。这个想法是给定全集 U 的子集 S 完全由函数 f:U-->{true,false}（称为子集的特征函数）确定。很简单，因为您可以将 f(u) 视为回答“u 是 S 中的元素吗？”的问题。

与其他方法相比，任何特定的表示集选择都有优点和缺点。特别是，某些表示更适合用函数式语言建模，而不是用命令式语言建模。如果我们将管理集合作为特征函数与（排序或未排序）列表（或数组）进行比较，那么，例如，创建联合、交集和集合差异对于特征函数非常有效，但对于列表则效率不高。检查元素是否存在就像使用特征函数计算 f(-) 一样简单，而不是搜索列表。但是，使用列表可以立即打印出集合中的元素，但可能需要使用特征函数进行大量计算。

话虽如此，一个根本的区别是，使用特征函数可以模拟无限集，而使用数组则不可能。当然，没有集合实际上是无限的，但是像 (x: BigInt) x => (x % 2) == 0 这样的集合真正代表了所有偶数的集合，并且实际上可以用它计算（只要你不要尝试打印所有元素）。

因此，每种表示形式都有优点和缺点（duh）。

于 2013-09-25T08:21:41.493 回答