2
$\begingroup$

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?

$\endgroup$
0
0
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ This is the generic advice you have given, I am interested in functions. $\endgroup$ – CodeYogi Aug 20 '16 at 2:22
  • 1
    $\begingroup$ @CodeYogi Your question is expressly asking for generic advice. With functional programming especially, it is helpful to write something that works, and then rewrite it until it looks pretty. I think this is great advice. $\endgroup$ – Eric Thoma Aug 24 '16 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.