Scala 集合函数

Question

在斯坦福 Scala 课程中，我遇到了以下作业：

练习 1 – 集合作为函数：

在本练习中，我们将把集合表示为从整数到布尔值的函数：

type Set = Int => Boolean

a）编写一个函数“set”，它接受一个 Int 参数并返回一个包含该 Int 的 Set。

b) 编写一个“包含”函数，将 Set 和 Int 作为参数，如果 Int 在 Set 中则返回 true，否则返回 false。

c) 编写函数“union”、“intersect”和“minus”，它们将两个 Set 作为参数并返回一个 Set。

d) 你能写一个函数“subset”，它接受两个 Sets 作为参数，如果第一个 Sets 是第二个 Sets 的子集，则返回 true，否则返回 false？

a、b 和 c 的解决方案相当简单：

def set(i: Int): Set = n => n == i

def contains(s: Set, i: Int) = s(i)

def union(a: Set, b: Set): Set = i => a(i) || b(i)

def intersect(a: Set, b: Set): Set = i => a(i) && b(i)

def minus(a: Set, b: Set): Set = i => a(i) && !b(i)

但是对于 d 是否有任何优雅的解决方案？ 当然，严格来说，d 的答案是“是”，因为我可以写这样的内容：

def subset(a: Set, b: Set) = Int.MinValue to Int.MaxValue filter(a) forall(b)

但这可能不是正确的方式。

Answer 1

我认为如果不迭代所有整数就不可能实现。对于伪证明，请查看所需的类型：

def subset: (a: Set, b: Set): Boolean

不知何故，当我们需要处理的只是集合 (a, a, >b) 类型为 Int =>;布尔值，和整数相等(Int, Int) =>布尔值。从这些原语中，获取 Boolean 值的唯一方法是从 Int 值开始。由于我们手中没有任何特定的 Int，唯一的选择就是迭代所有它们。

如果我们有一个神奇的神谕，isEmpty: Set =>;布尔，故事会有所不同。

最后一个选项是将“false”编码为空集，将“true”编码为其他内容，从而将所需类型更改为：

def subset: (a: Set, b: Set): Set

使用此编码，逻辑“或”对应于集合并集运算，但我不知道逻辑上的“与”或“非”可以轻易定义。

Answer 2

我们有

Set A = 
    Returns the intersection of the two given sets,
    the set of all elements that are both in `s` and `t`.

Set B = 
    Returns the subset of `s` for which `p` holds.

不是集合 A 等于集合 B

def filter(s: Set, p: Int => Boolean): Set = intersect(s, p)

Answer 3

我同意 Kipton Barros 的观点，您必须检查 Ints 的所有值，因为您想证明对于所有 x，a(x) 意味着 b(x)。

关于它的优化，我可能会写：

  def subset(a: Set, b: Set) = Int.MinValue to Int.MaxValue exists(i => !a(i) || b(i))

since !a(i) || b(i) 等价于 a(i) 暗示 b(i)

Answer 4

稍后在 Coursera 练习中介绍了有界集，然后介绍了 forall() 和exists() 作为边界上的通用量词和存在量词。 subset() 不在练习中，但与 forall 类似。这是我的子集（）版本：

// subset(s,p) tests if p is a subset of p returning true or false
def subset(s: Set, p: Set): Boolean = {
  def iter(a: Int): Boolean = {
    if (a > bound) { true
    } else if (contains(p, a)) {
        if (contains(s, a)) iter(a + 1) else false
    } else iter(a+1)
  }
  iter(-bound)
}

Answer 5

这是使用 contains 函数的另一个版本：

def union(s: Set, t: Set): Set = x => contains(s,x) || contains(t,x)

def intersect(s: Set, t: Set): Set = x => contains(s,x) && contains(t,x)

def diff(s: Set, t: Set): Set = x => contains(s,x) && !contains(t,x)

def filter(s: Set, p: Int => Boolean): Set = x =>  contains(s, x) && p(x)

Answer 6

如果有两个集合 A 和 B，则 A 与 B 相交是 A 和 B 的子集。数学证明：A ∩ B ⊆ A 和 A ∩ B ⊆ B。函数可以这样写：

def filter(s: Set, p: Int => Boolean): Set = x => s(x) && p(x)

或者

def intersect(s: Set, t: Set): Set = x => s(x) && t(x)
def filter(s: Set, p: Int => Boolean): Set = intersect(s,p)