Union of two sets in Scala

问题:

From the question linked here, I found this implementation of Union in Scala:

def union(a: Set, b: Set): Set = i => a(i) || b(i)

And Set is a function of type:

type Set = Int => Boolean

Now I understand that in Scala, a function is mapped from Int to Boolean here, and I further understand how this statement is executed:

a(i) || b(i)

But what I don't understand is what is 'i' here. Where does it come from? And when it finds a match between to sets, it returns true, if it indeed does, where do I filter it?

回答1:

Let say we have object called SoSet given by

object SoSet {
    type Set = Int => Boolean
    val a : Set = ???
    val b : Set = ???
    def isItem(item : Int) = a(item) || b(item)
}

The signature of isItem is given by Int => Boolean which is a Set. So far so good.

But now we just want to return the function isItem (i.e. a Set).

So lets define union function for this (There are no parameters right now. We will add it later).

object SoSet {
    //..   
     def union : Set = isItem // returns the function isItem
}

Now lets refactor the isItem into a anonymous function.

object SoSet {
    //..   
    def union : Set = {
      (item : Int) => a(item) || b(item)
    }
}

Lets move Set a and b from object SoSet to parameters of def union. Refactor item to i.

object SoSet { 
   type Set = Int => Boolean
   def union(a : Set, b : Set) : Set = (i : Int) => a(i) || b(i)
}

UPDATE

 val s1 = Set(1, 2, 3)                           
 val s2 = Set(2, 3, 4)     
 val s3 = union(s1, s2) //  returns the function..  Int => Boolean = <function1>
 s3(2)  // invokes the function & checks if 2 is present in the union     

回答2:

The Set (which is just a function) that gets returned from union takes some integer as a parameter; you must give it an arbitrary name so that you can refer to it in the function body. It may make more sense if you write the function like this:

def union(a: Set, b: Set): Set = {
  (i) => a(i) || b(i)
}

It may make even more sense if you write it like this:

def union(a: Set, b: Set): Set = {
  // The union of two sets is a new function that takes an Int...
  def theUnion(i: Int): Boolean = {
    // and returns true if EITEHR of the other functions are true
    a(i) || b(i)
  }

  // Now we want to return the NEW function
  theUnion
}

Again, i is arbitrary and could be replaced with any variable:

def union(a: Set, b: Set): Set = item => a(item) || b(item)

[Update]

Because we're representing sets as functions, there's no need to iterate to see if they contain a number. For example, here's a set that contains any number below -5:

val belowNegFive: Set = (i) => i < -5

When we call that function with a number, it will tell us if that number is in the set. Note that at no time did we actually tell it the specific numbers that were in the set:

scala> belowNegFive(10)
res0: Boolean = false

scala> belowNegFive(-100)
res1: Boolean = true

scala> belowNegFive(-1)
res2: Boolean = false

Here's another set that includes any number between 50 and 100:

val fiftyToHundred: Set = (i) => i >= 50 && i <= 100

scala> fiftyToHundred(50)
res3: Boolean = true

scala> fiftyToHundred(100)
res4: Boolean = true

scala> fiftyToHundred(75)
res5: Boolean = true

scala> fiftyToHundred(49)
res6: Boolean = false

Now, a union of the sets belowNegFive and fiftyToHundred would contain any number that is either below -5 or between 50 and 100. We can easily represent this in code by returning a new function which itself returns true if either of the other two functions returns true.

scala> val unionOfBoth: Set = (i) => belowNegFive(i) || fiftyToHundred(i)
unionOfBoth: Int => Boolean = <function1>

scala> unionOfBoth(-10)
res7: Boolean = true

scala> unionOfBoth(50)
res8: Boolean = true

scala> unionOfBoth(0)
res9: Boolean = false

The union function from your question is just a way of applying this pattern generically over any two sets.

回答3:

And when it finds a match between to sets, it returns true, if it indeed does, where do I filter it?

union does not find a match between two sets, it creates a new set which contains the values of both sets. Example:

val a = (i) => i == 2 // a contains 2 as a(2) == True
val b = (i) => i == 5 // b contains 5 as b(5) == True
val u = union(a, b)   // u contains 2 and 5 as u(2) == True and u(5) == True

So the 'filtering' just happens on the way. This function is not iterating over each set, filtering specific things out, it just returns a combination of two functions which then can executed later to query for the actual values.

Example of querying the values of a union:

val a = (i) => i == 2
val b = (i) => i == 5
val u = union(a, b)

for(i <- 1 to 10 if u(i)) yield i     // returns Vector(2, 5)

And yes, this is not an optimal way of storing values in sets as you have to check values by guessing but it is a good way to demonstrate how combining functions adds complex functionality without writing very complex code.

回答4:

You can implement a union function like this:

def union[A](set1: Set[A], set2:Set[A]):Set[A] = {
    set1.foldLeft(set2)((set, elem) => set + elem)
}

or

def union[A](set1: Set[A], set2:Set[A]):Set[A] = {
    set1.flatMap(elem => set2 + elem)
}

These will be generic so you can use it for sets of any type