Is my understanding of below scala code correct?

After watching the lecture video on "Currying", I believe that Paolo's solution expressed in a more verbose manner is :

    def singletonSet(elem: Int): Set = {
    def innerFunction (givenElement: Int) = 
      if (elem == givenElement) true
      else false
      innerFunction
  }

Plesae correct me if I am wrong!


Let's read sort of backwards, in logical order.

Say you have a finite set of integers: 0, 1, 2, 3, 5, 8 for instance

One way to describe this set of integers is through a function (its characteristic or indicator function) that, for each integer, returns true if the integer is in the set, false if it is not. The signature for this function, as we described it, must always be Int => Boolean ("give me an integer, I will tell you if it's in the set"), while its implementation will vary depending on the specific set.

For the set in my example above you could write this function simply as:

val mySet: Int => Boolean = x => Array(0,1,2,3,5,8) contains x

or recognize that the ints in the set are the first ones of the Fibonacci sequence and define f in a slightly more sophisticated way (which I won't do here...). Note that the "contains" I've used is defined for all scala collections. In any case, now you have a function that tells you what is in the set and what is not. Let's try it in the REPL.

scala> val mySet: Int => Boolean = x => Array(0,1,2,3,5,8) contains x
mySet: Int => Boolean = <function1>

scala> mySet(3)
res0: Boolean = true

scala> mySet(9)
res1: Boolean = false

Now, mySet has type Int => Boolean, which we can make more readable if we define it as a type alias.

scala> type Set = Int => Boolean
defined type alias Set

Besides readability, defining Set as an alias of Int => Boolean is making it explicit that in a way a Set is its characteristic function. We can redefine mySet in a more concise (but otherwise equivalent) way with the Set type alias:

scala> val mySet: Set = x => Array(0,1,2,3,5,8) contains x
mySet: Int => Boolean = <function1>

Now for the last piece of this long answer. Let's define a characteristic function to describe this Singleton set: 3. Easy:

val Singleton3 : Set = set => set == 3

for a Singleton set containing only 4, it would be:

val Singleton4 : Set = set => set == 4

So, let's generalize the creation of these functions and write a method that returns a Singleton function that, for any integer, describes the set containing only that integer:

def singletonSet(elem: Int): Set = set => set == elem

APPENDIX:

I skipped this part, because it wasn't really needed: def contains(set: Set, elem: Int): Boolean = set(elem)

I think it's sort of pointless and (without more context) it looks just like a contrived example to demonstrate how you can pass a function around as an argument, just like any other type in scala. It takes the Int => Bool function and the Int and just applies the function to the Int so you can do

scala> contains(mySet, 3)
res2: Boolean = true

which is like calling mySet(3) directly.


To answer your question - But what logic is performed to determine if the Int 'elem' is a member of Set 's'

This is performed when you make the actual function call. Consider the following function call.

contains(singletonSet(1), 1)

Now singletonSet is defined as def singletonSet(elem: Int): Set = x => x == elem (I choose to use the identifier x for clarity sake). The return type of the singletonSet is the function of type Set which takes an Int argument and returns Boolean. So the above calling function's first argument singletonSet(1) equates to the function x => x == 1 as elem here is 1. So we get

contains((x => x == 1),1)

Now considering the definition of contains function def contains(f: Set, elem: Int): Boolean = f(elem). The first argument in the call above is the function x => x == 1 which substitutes formal parameter f and second argument 1 substitutes formal parameter elem. The return value of contains is the function f(elem) which equates to f(1). Since f(x) is defined as (x == 1), f(1) equates to (1 == 1) which returns true.

Going by the same logic, a function call like contains(singletonSet(1), 2) would finally equate to (1 == 2) which will return false.

Tags:

Scala

Recent Posts