user701254 - 1 year ago 80

Scala Question

I'm just trying to understand the below code :

Here a new type alias Set is declared which is a function that takes an Int

parameter and returns a boolean

`type Set = Int => Boolean`

Here a new method 'contains' is declared, which takes two parameters of type Set and Int

which returns a boolean. The boolean is set to the function declared in earlier

('type Set = Int => Boolean')

But what logic is performed to determine if the Int 'elem' is a member of Set 's'

`def contains(set: Set, elem: Int): Boolean = set(elem)`

Here a method is defined which returns a set which returns a function ?

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

Complete code with comments :

`/**`

* We represent a set by its characteristic function, i.e.

* its `contains` predicate.

*/

type Set = Int => Boolean

/**

* Indicates whether a set contains a given element.

*/

def contains(set: Set, elem: Int): Boolean = set(elem)

/**

* Returns the set of the one given element.

*/

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

Answer Source

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 => Bool`

("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.