scala Scala集合函数

Scala set function

提问by Grozz

In Stanford Scala course I've come across the following assignment:

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

Exercise 1 – Sets as Functions:

练习 1 – 设置为函数：

In this exercise we will represent sets as functions from Ints to Booleans:

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

type Set = Int => Boolean

a) Write a function "set" that takes an Int parameter and returns a Set containing that Int.

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

b) Write a function "contains" that takes a Set and an Int as parameters and returns true if the Int is in the Set and false otherwise.

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

c) Write the functions "union", "intersect", and "minus" that take two Sets as parameters and return a Set.

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

d) Can you write a function "subset" which takes two Sets as parameters and returns true if the first is a subset of the second and false otherwise?

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

Solutions to the a, band care fairly trivial:

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)

But is there any elegant solution for d? Of course, strictly speaking, the answer to dis "yes", as I can write something like:

但是d有什么优雅的解决方案吗？当然，严格来说，d的答案是“是”，因为我可以这样写：

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

but that's probably not the right way.

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

采纳答案by Kipton Barros

I don't think it's possible without iterating through all the integers. For a pseudo-proof, look at the desired type:

我认为不遍历所有整数是不可能的。对于伪证明，请查看所需的类型：

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

Somehow, we've got to produce a Booleanwhen all we have to work with are sets (a, b) of type Int => Boolean, and integer equality (Int, Int) => Boolean. From these primitives, the only way to get a Booleanvalue is to start with Intvalues. Since we don't have any specific Int's in our hands, the only option is to iterate through all of them.

不知何故，Boolean当我们需要处理的只是类型的集合 ( a, b)Int => Boolean和整数相等时，我们必须生成 a (Int, Int) => Boolean。从这些原语中，获取Boolean值的唯一方法是从值开始Int。由于我们Int手中没有任何特定的's，唯一的选择是遍历所有这些。

If we had a magical oracle, isEmpty: Set => Boolean, the story would be different.

如果我们有一个神奇的神谕，isEmpty: Set => Boolean故事就会不同。

A final option is to encode"false" as the empty set and "true" as anything else, thus changing the desired type to:

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

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

With this encoding, logical "or" corresponds to the set union operation, but I don't know that logical "and" or "not" can be defined easily.

使用这种编码，逻辑“或”对应于集合联合操作，但我不知道逻辑“与”或“非”可以轻松定义。

回答by Ronak Agrawal

We have

我们有

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.

Isn't Set A is equivalent to Set B

Set A 不等于 Set B

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

回答by Roman Kazanovskyi

Here is another version of it using contains function:

这是使用 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)

回答by Carlos López-Camey

I agree with Kipton Barros, you would have to check all values for Ints since you want to prove that forall x, a(x) implies b(x).

我同意 Kipton Barros 的观点，您必须检查 Ints 的所有值，因为您想证明forall x, a(x) implies b(x).

Regarding the optimization of it, I'd probably write:

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

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

since !a(i) || b(i)is equivalent to a(i) implies b(i)

因为!a(i) || b(i)等价于a(i) implies b(i)

回答by Carlos López-Camey

Later on in the Coursera exercises bounded sets are introduced and then forall() and exists() as universal and existential quantifiers over the bounds. subset() was not in the exercises but is similar to forall. Here is my version of subset():

稍后在 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)
}

回答by Icoder

If there are two sets A and B, then A intersect B is a subset of A and B. Mathematically proven: A ∩ B ? A and A ∩ B ? B. Function can be written like this:

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

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

Or

或者

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