Scala设置功能 [英] Scala set function

问题描述

在斯坦福大学斯卡拉大学的课程中，我遇到了以下任务：

练习1 - 设置为函数：

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

  type Set = Int =>布尔
  

a ）编写一个函数set并返回一个包含该Int的Set。

b ）编写一个函数contains，它将Set和Int作为参数并返回true如果Int在Set中，则返回false，否则返回false。

c ）编写函数union，intersect和minus这两个集合作为参数并返回一个集合。

d ）您可以编写一个函数subset如果第一个是第二个子集，则返回true，否则返回false？ a ， b 和 c 是相当平凡的：

  def set（i：Int）：Set = n => ; n == i 
 $ b $ def包含（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子集（a：Set，b：Set）= Int.MinValue为Int.MaxValue过滤器（a）forall（b）
   b 
 
 
但这可能不是正确的方法。
解决方案
认为没有遍历所有整数是可能的。对于一个伪证明，看看所需的类型： 
 
 
  def子集：（a：Set，b：Set）：Boolean 
  
不知何故，我们必须产生布尔值类型的集合（ a ， b ）时， Int =>布尔和整数相等（Int，Int）=>布尔。从这些原语中，获取布尔值值的唯一方法是以 Int 值开始。由于我们手中没有任何特定的 Int '，唯一的选择就是遍历所有这些。
 
 
 
如果我们有一个神奇的oracle， isEmpty：Set =>布尔，故事会有所不同。
 
 
 
最后一个选项是将 false编码为空集和true作为其他内容，因此将所需类型更改为： 
 
 
  def子集：（a：Set，b：Set ）：设置
  
使用此编码，逻辑或对应于设置的联合操作，但我不不知道逻辑和或不是可以很容易地定义。
 
In Stanford Scala course I've come across the following assignment:

Exercise 1 – Sets as Functions:

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.

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) Write the functions "union", "intersect", and "minus" that take two Sets as parameters and return a 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?

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)
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
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.

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屋！