Starting to understand functional programming


I am currently undertaking the online course “Functional programming principles in Scala” and I thought I’d share what I’ve discovered. I am definitely a beginner in this topic and what I say might be totally wrong but that’s one of the points of this blog, which is opening myself up to criticism so that I can learn.

Coming from an imperative programming background, it can be tricky to get programming in a functional style. Using the latter, it is imperative to undertand that functions are first class citizens and one of the consequences is the fact that you can pass functions as parameters. The implications of this are very profound because, amongst the benefits associated with functional programming (FP) and which I can see are better:

  • Composability and hence testability
  • Separation of concerns

I am not going into how and why of the above as that’s not the main purpose of this post. Instead, I want to discuss the passing of functions as parameters instead.

In the current assignment I’m currently doing for the course, I came across the following problem description:

—————————–

We will work with sets of integers.

  1. 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.
  2. 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.
  3. Therefore, we choose to represent a set by its characterisitc function and define a type alias for this representation:
    type Set = Int => Boolean
  4. 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)
  5. 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

—————————–

When I read this I thought to myself “What the hell!!!” but that’s because this assignment is rooted in I believe Set theory and being unfamiliar with both the latter and FP made the assignment that bit more difficult. However, if you break down what is is required and what they are trying to say, things get a bit simpler.

So in parts 1 and 2 of the problem, a short description of number and set theory is given. Now in part 2, we are told that we can, in Scala, represent the set of negative numbers as the following anonymous function (if you’re new to this term, this simply means that the function doesn’t have a name but instead is declared inline as you’ll see later when we pass in the anonymous function as a parameter to another function):

(x: Int) => x < 0

In other words, given an input x of type Int, x is part of the set of negative numbers if the actual value of x is less than 0.

Thus in order to represent the sets of positive numbers and even odd numbers respectively using anonymous functions would be:

(x: Int) => x > 0

(x: Int) => x % 2 == 1

Now notice that there is a pattern emerging i.e. for a given input of simple type Int the output is a Boolean. Hence, that’s what part 3 of the problem description is saying:

type Set = Int => Boolean

So to reiterate what was explained in the problem descripton, a set is represented by its characteristic function (denoted in sky blue above). In other words in order to find out if an Int x is part of a given set, it will have to satisfy the boolean expression.

Moving on to part 4 we are told that the following function tests for the presence of a value in a set

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

That to me was very confusing because I was/am still in the imperative programming frame of mind. In the latter mode of thinking, in order to test whether a number is part of a set(collection in the C# world), I’d expect to see a concrete set s through which I’d be able to iterate through and see if the element elem was part of that collection. In FP, we don’t do this and that’s where there is a need for us to forget the thought patterns we are so familiar with in imperative programming. However, what you should understand is that the function will return whether or not an elem of type Int is part of the Set s.

I will not be answering the question in part 5 of the problem description because that would be violating the code of honour I had to actually sign up to for taking the online course. However, the following should help in shaping the answer. Let’s assume that you are given:

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

and instead of being asked to define the singletonSet, you are asked to define the function for the set of even numbers so that the following would return true

contains(???, 2)

contains(???, 18)

where ??? represents the function to be defined.

Similar to the anonymous function for the set of odd numbers, we can define the anonymous function for the set of even numbers as:

(x: Int) => x % 2 == 0

In other other words, we can replace the ??? with the anonymous function above as follows:

contains((x: Int) => x % 2 == 0, 2)
contains((x: Int) => x % 2 == 0, 18)

We might want to resuse the definition for the set of even numbers and so we can define a function e.g.

def evenSet(x: Int): Set = x => x % 2 == 0

Notice again how the definition of the set of even numbers matches the defnition of the type Set defined above i.e.

type Set = Int => Boolean

Now I would like to backtrack a bit and show how the function contains is getting evaluated. So, if we look at the function definition for contains which we then call with appropriate values:

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

contains((x: Int) => x % 2 == 0, 2)

what we are doing in the function body s(elem)is:

s(2)

where s is defined as:

(x: Int) => x % 2 == 0

This can be expanded as:

2 => 2 % 2 == 0

Without giving the actual answer away for part 5, singletonSet should also take the same form as eventSet

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

By the way FP is not easy. Even after writing this blog post, I find it hard to give the answer to part 5 quickly and easily because it’s so alien. Hopefully, with practice, I’ll be able to write in a more funcational manner. I may be wrong but the way I’m currently conceptualising passing of functions is like passing a block of templated code around instead of simple data and object types.

Advertisements
Posted in Functional programming, Scala
One comment on “Starting to understand functional programming
  1. Atul says:

    nice explanation, DavidS

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: