Developing functional thinking.

Question

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?

Answer 1

I'm not very good at coding, and I have been trying to get better. While watching videos and such is helpful, it is not always helpful when I am trying to solve a problem. I have found that Project Euler has helped me learn how to solve a problem (and when I have a problem with my code, I google python syntax or ask a question and keep going). I also try to solve problems on here that I think I could take a crack at with code. The more problems I solve, the more commands I have enough of a command of to think of using on the next problem, and so I'm able to try harder problems.

The other thing that has been important for me is the way of thinking about the problem. I try to start by making sure I understand the problem, and then I try to define the constants (variables) and equations I'll need. Then I try to work on the method I want to use to get the result, and then, if necessary, I'll make it look pretty. I guess that's my "mental model".

Hope this helps!