Scala设置功能

Question

在斯坦福斯卡拉课程中,我遇到了以下任务:

练习1 - 设置为函数:

在本练习中,我们将表示集合作为从Ints到Booleans的函数:

type Set = Int => Boolean

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

b)编写一个函数"contains",它将Set和Int作为参数,如果Int在Set中则返回true,否则返回false.

c)编写函数"union","intersect"和"minus",它们将两个Sets作为参数并返回一个Set.

d)你能编写一个函数"subset",它将两个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

不知何故,我们必须生成一个Boolean我们必须使用的是类型的集合(a,b)Int => Boolean和整数相等(Int, Int) => Boolean.从这些原语中,获取Boolean值的唯一方法是从值开始Int.由于我们Int手中没有任何特定的东西,唯一的选择是迭代所有这些.

如果我们有一个神奇的神谕,isEmpty: Set => Boolean故事会有所不同.

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

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

使用此编码,逻辑"或"对应于集合并操作,但我不知道可以轻松定义逻辑"和"或"不".