# Developing functional thinking.

I am taking this course on Scala, at first it seemed easy with trivial exercises but gradually its becoming more of a mathematical course which seems to require an experienced mathematical mind. Giving an example of one of the exercises:

Quoting from the exercise:

Representation

We will work with sets of integers.

As an example to motivate our representation, how would you represent the set of all negative integers? You cannot list them all… one way would be so say: if you give me an integer, I can tell you whether it’s in the set or not: for 3, I say ‘no’; for -1, I say yes.

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


Code:

type Set = Int => Boolean

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

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

def union(s1:Set, s2:Set): Set =
(elem) => contains(s1, elem) || contains(s2, elem)

def intersect(s1:Set, s2:Set): Set =
(elem) => contains(s1, elem) && contains(s2, elem)

def diff(s1:Set, s2:Set): Set =
(elem) => contains(s1, elem) && !contains(s2, elem)

def filter(s1:Set, p: Int => Boolean): Set =
(elem) => contains(s1, elem) && p(elem)

def forall(s: Set, p: Int => Boolean): Boolean = {
def inforall(lo: Int): Boolean = {
if (lo > 1000) true
else if (contains(s, lo))
p(lo) && inforall(lo + 1)
else
inforall(lo + 1)
}
inforall(-1000) // [-1000, 1000]
}

def negate(p: Int => Boolean): Int => Boolean =
(x) => !p(x)

// A predicate is true for some elements of the set but
// its not false for all of them.
def exists(s: Set, p: Int => Boolean): Boolean =
// negative predicate should not be true forall elems
forall(s, negate(p)) != true

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


Having said this much, I need to commit that I couldn't solve the exists and map and I took help from Google, but I know the issues I faced while solving the above exercise:

1. Functions like union, intersect felt like magic I was able to write them without thinking much but when I tried to understand them my head started spinning, it felt like a paradox when you can solve the problem without thinking less about it.
2. Functions like exists and map felt like a non-trivial task to me even after seeing their solution I doubt that I could have thought like that.

My question is how to develop thinking habit to solve problems like these what are the sources that could help me? Is there any mental model that could help me visualize the solution or thinking process, or at least what not to do while solving problem in this domain?