在Stanford课程中,我遇到了以下任务:
练习1-集合为函数:
在本练习中,我们将集合表示为从Ints到Booleans的函数:
type Set = Int => Booleana)编写一个函数" Set“,该函数接受Int参数并返回包含该Int的集合。
( b)编写一个函数“包含”,该函数以Set和Int作为参数,如果Int在Set中,则返回true,否则返回false。
( c)编写以两个集合为参数并返回一个集合的函数"union“、"intersect”和“减号”。
( d)你能写一个函数“子集”,它以两个集合作为参数,如果第一个子集是第二个子集,则返回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)但这可能不是正确的方法。
发布于 2011-08-06 01:03:27
我认为不迭代所有整数是不可能的。对于伪防伪,请查看所需的类型:
def subset: (a: Set, b: Set): Boolean不知何故,当我们只需要处理类型为Boolean的集合(a、b)和整数相等(Int, Int) => Boolean时,我们就必须生成一个Int => Boolean。从这些原语中,获得Boolean值的唯一方法是从Int值开始。由于我们手中没有任何特定的Int,所以唯一的选择就是遍历它们。
如果我们有一个神奇的神谕,isEmpty: Set => Boolean,故事将是不同的。
最后一个选项是将"false“编码为空集,将"true”编码为任何其他内容,从而将所需类型更改为:
def subset: (a: Set, b: Set): Set使用此编码,逻辑“或”对应于设置的联合操作,但我不知道逻辑“和”或“不”可以很容易地定义。
发布于 2015-03-14 16:56:13
我们有
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)发布于 2011-08-06 04:12:38
我同意Kipton的观点,您必须检查Ints的所有值,因为您想证明forall x, a(x) implies b(x)。
关于它的优化,我可能会写:
def subset(a: Set, b: Set) = Int.MinValue to Int.MaxValue exists(i => !a(i) || b(i))因为!a(i) || b(i)等同于a(i) implies b(i)
https://stackoverflow.com/questions/6963792
复制相似问题