Mathematically, we call the function which takes an integer as argument and which returns a boolean indicating whether the given integer belongs to a set, the

*characteristic*function of the set. For example, we can characterize the set of negative integers by the characteristic function`(x: Int) => x < 0`

.
Therefore, we choose to represent a set by its characterisitc function and define a type alias for this representation:

`type Set = Int => Boolean`

Using this representation, we define a function that tests for the presence of a value in a set:

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

## 2.1 Basic Functions on Sets

Let’s start by implementing basic functions on sets.

- Define a function which creates a singleton set from one integer value: the set represents the set of the one given element. Its signature is as follows:
`def singletonSet(elem: Int): Set`

Now that we have a way to create singleton sets, we want to define a function that allow us to build bigger sets from smaller ones. - Define the functions
`union`

,`intersect`

, and`diff`

, which takes two sets, and return, respectively, their union, intersection and differences.`diff(s, t)`

returns a set which contains all the elements of the set`s`

that are not in the set`t`

. These functions have the following signatures:`def union(s: Set, t: Set): Set def intersect(s: Set, t: Set): Set def diff(s: Set, t: Set): Set`

- Define the function
`filter`

which selects only the elements of a set that are accepted by a given predicate`p`

. The filtered elements are returned as a new set. The signature of`filter`

is as follows:`def filter(s: Set, p: Int => Boolean): Set`

## 2.2 Queries and Transformations on Sets

In this part, we are interested in functions used to make requests on elements of a set. The first function tests whether a given predicate is true for all elements of the set. This

`forall`

function has the following signature:`def forall(s: Set, p: Int => Boolean): Boolean`

Note that there is no direct way to find which elements are in a set.

`contains`

only allows to know whether a given element is included. Thus, if we wish to do something to all elements of a set, then we have to iterate over all integers, testing each time whether it is included in the set, and if so, to do something with it. Here, we consider that an integer `x`

has the property `-1000 <= x <= 1000`

in order to limit the search space.- Implement
`forall`

using linear recursion. For this, use a helper function nested in`forall`

. Its structure is as follows (replace the`???`

):`def forall(s: Set, p: Int => Boolean): Boolean = { def iter(a: Int): Boolean = { if (???) ??? else if (???) ??? else iter(???) } iter(???)`

} - Using
`forall`

, implement a function`exists`

which tests whether a set contains at least one element for which the given predicate is true. Note that the functions`forall`

and`exists`

behave like the universal and existential quantifiers of first-order logic.`def exists(s: Set, p: Int => Boolean): Boolean`

- Finally, write a function
`map`

which transforms a given set into another one by applying to each of its elements the given function.`map`

has the following signature:`def map(s: Set, f: Int => Int): Set`

Coursera Scala course week 2 homework. The original question can be found here.

The question asks as two define an object Set, which has a characteristic function that projects an integer to a boolean.

1. define Singleton

This question requires us to create a set with one integer, i.e., given an integer, projects it to a boolean to claim the set contains the integer:

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

This means projects an integer

*x*to if

*x*equals given parameter elem. It can also be considered as given any integer, if

*x*equals

*elem*, then set contains

*x*, which defines the singleton set that it only contains

*elem*.

2. define Union, Intersect and Difference

```
def union(s: Set, t: Set): Set = (x: Int) => s(x) || t(x)
def intersect(s: Set, t: Set): Set = (x: Int) => s(x) && t(x)
def diff(s: Set, t: Set): Set = (x: Int) => s(x) && !t(x)
```

*s(x)*indicates

*contains*. Thus, for union, it means either for any

*x*, if it satisfies the condition that either

*s*contains

*x*or

*t*contains

*x*, then

*x*is in

*union*. For intersect, the condition becomes both

*s*and

*t*should contains

*x*. For difference, it means

*s*should contain

*x*but

*t*should not.

3. define filter

`def filter(s: Set, p: Int => Boolean): Set = (x: Int) => s(x) && p(x)`

filter is a set that for any

*x*in

*filter*, it should satisfies that

*s*contains

*x*and

*x*satisfies predicate

*p*.

4. forall (∀ )

```
val bound = 1000
def forall(s: Set, p: Int => Boolean): Boolean = {
def iter(a: Int): Boolean = {
if (a > bound) true
else if (s(a) && !p(a)) false
else iter(a+1)
}
iter(-bound)
}
```

This is nothing special. Starts from

*-bound*, if any

*a*in

*s*doesn't satisfy

*p*, then return false. Iterate until bound, then return true.

5. exists(∃ )

```
def exists(s: Set, p: Int => Boolean): Boolean = !forall(s, x => !p(x))
```

This one is tricky. The solution means not all elements in s satisfies !p, which in turn indicates there is at least one element in s satisfies p.

6. map

```
def map(s: Set, f: Int => Int): Set = (y: Int) => exists(s, x => f(x) == y)
```

This is similar as how we define a singleton set: For any

*y*, if there exists an element

*x*in

*s*that satisfies the condition

*f(x)*equals

*y*, then

*y*is in new Set

*map*.

Source on git.

Hi, I am just a beginner in Scala. Your code helped me a lot. Thanks for sharing

ReplyDeleteShirley, You are welcome to give as many hints as possible, but you should not give away the solutions! That's breaking 'Code of Honor' that all attendees of Coursera sign up to.

ReplyDeleteAwesome intro.....please keep up the great work.

ReplyDeletehttp://islamguzelahlaktir.blogspot.com/

ReplyDeleteThank you so much for this blog. I'm auditing the Scala course and I'd be lost without you.

ReplyDeleteI have a feeling that 99.99% of the people that complete the Scala course broke the honor code. That course is brutal difficult. I'm grateful that the solutions are out there.

ReplyDelete这个exists想了半天……

ReplyDelete