Scala集合函数 [英] Scala set function

问题描述

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

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

练习 1 – 设置为函数:

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

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

type Set = Int => Boolean

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

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

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

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.

c) 编写函数union"、intersect"和minus"，以两个 Set 作为参数并返回一个 Set.

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

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

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?

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

Solutions to the a, b and c are fairly trivial:

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 的答案是是"，因为我可以这样写:

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

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

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

but that's probably not the right way.

推荐答案

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

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

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

Somehow, we've got to produce a Boolean when 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 Boolean value is to start with Int values. Since we don't have any specific Int's in our hands, the only option is to iterate through all of them.

如果我们有一个神奇的预言机，isEmpty: Set =>布尔，故事会有所不同.

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

最后一个选项是编码假"为空集，真"为其他任何东西，从而将所需的类型更改为:

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

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.

这篇关于Scala集合函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！