Functional Programming with Scala part#1

Welcome,

In this brief article, I will introduce you to some basic knowledge about Functional Programming, along with some examples and use cases in Scala. But if you are not interested in Scala or you prefer to use another language, you can just focus on the basic concepts and search for the implementation afterward in your own language.

So let's begin with a definition:

1) What is Functional Programming?

Let's take a look at Wikipedia:

"In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that each return a value, rather than a sequence of imperative statements which change the state of the program or world."

As you can see, there are some highlighted terms which are essential for the definition.

First, functional programming is a programming paradigm, meaning a style or a set of rules to write code, and it's a declarative paradigm. What does that mean?

Well, for ages we used to write imperative code, in which we write sequences of instructions (statements) to solve problems. This has its background in the Von Neumann computer architecture and how the machine executes our code instruction by instruction, putting data in memory, reading that data, etc. So we focus on how to solve the problem with one function or a procedure.

Let's take an example: suppose that we have an array of integers and we want to extract an array of even numbers out of it.

In the usual imperative approach, we do something like this — loop through the list, and each time we find an even number, we save it into our newly created array. (code below)

So we define the full engineering of the solution in one function.

What about the declarative approach?

We can do the same in just one line of code.

As you can see, we break our solution into a bunch of functions and chain them (here, the filter function gets an anonymous callback). So here we define what we want to do first, not how, and as a result, the code expresses itself at first glance.

Besides this, FP has some other principles like Purity and immutability, which we will explain further in this article.

2) Origins Functional Programming

Functional programming has its foundations in lambda calculus... Lambda what?! 😕

Lambda calculus is a computation model developed by mathematician Alonzo Church in the 1930s. It combines the abstraction of problems into functions with the application and computation of these functions.

Here's an example: the identity function,λx. x

So the character beside the lambda symbol is the parameter (or the binding), and the part after the "." (point) is the core of the function. In the lambda calculus system, everything is a function (from the mathematical perspective), and each lambda expression can be one of the following forms:

1. A simple variable (a constant function), for example: x or 2
2. λx. M : a function or un abstraction (binding + the core), example:

λx. x + y * 2

1. M N : An application (an abstraction concatenated with another expression) in this case we can apply that expression (the N part) into the first abstraction (M) as we can see next. example:

(λx. x) λy. y + 1      // M = λx. x, N = λy. y + 1

Beta Reduction

In the Lambda system, we have what we call “beta reduction”, it’s simply like executing the function for what it comes after it.

Let’s take an example:

λ x.x 2 -β-> 2

We have lambda x.x 2 so we apply 2 on the function we get 2.

Another example:

(λx.λy.y x)(λz.u)  -β->  λy.y(λz.u) -β->  λz.u

So as you can see we have a system calculus system that is very straightforward and proved by mathematicians,

Note: in modern programming languages, lambda function refers to the anonymous function which is a type of functions ****without a name that can be treated as values (passed as a parameter, returned by another function…) . For example, take the increment() function:

λx. x+1  ==>  val fun = x => x+1 (Scala)

3) Main Principles of FP

Functional Programming has two main rules:

Purity + Immutability

Rule 1: Purity, "All functions must be pure"

What is a pure function?

Well, it’s a function that gives you always the same value in return for the same arguments, like the following add() function, which calculates and returns the sum of 2 numbers (you may be saying,

well that sounds ridiculous ! why should a function gives me something I didn’t expect, well, keep reading you will know why 🙂

There’s a principle called “referential transparency” and it’s inherited from the declarative paradigm. It says that for each possible input value if we can replace the function call inside a program by it’s assumed value, we don’t change the whole behavior of that program so this function is referential transparent and thus it’s pure,

(More about referential transparency: **https://www.sitepoint.com/what-is-referential-transparency/**)

If you don’t bother yourself with those theoretical aspects, keep this in mind: “A pure function is a function with no side effects”

Here we have some examples of side effects:

1. First one, a function “counter” that uses a global variable. That’s not allowed in Pure FP because the result of this function doesn’t depend only on its parameter so it may give us different results for the same input!

1. Another form of side effects, the operations that may fail at any time, like making an input/output operation, a database operation, an http call a logging to the command line system … etc.

But you may be wondering, so how can we make this kind of work with FP way? well the answer is not that simple 🤓, and we will see how in the next article.

 Rule 2: Immutability, "No to state mutability (No variables)"

In functional programming like in maths, we don’t change the value of variables, instead we create new instances as much as we need.

var a = 2

a = a + b

Here, we declared a variable “a”, and then we changed its value by adding “b”, that’s not allowed in FP.

Instead, we create a new variable “c” and we affect the new result to it,

( In scala, because it’s a multi-paradigms language, it allows us mutate the value of a variable but it must be var not val, when we use val it’s like a lock to the variable to prevent future changes)

But you may ask me why should I care about that I have the same result anyway 😕, well, there is at least 3 reasons for that:

1. Changing value => memory access => side effects
2. Clean code like algebra ex: val c = h(g(f(x)))
3. Another very important reason is that Mutating state is not good for parallel processing ex: multi-threads share the same variable.

... Next, you may say "OK no mutating state, only constant values, but how can I make a loop?", well that’s a good question..

And the immediate answer will be: Use Recursion. And simply recursive function is a function that calls itself for different input values.

It’s true that recursion is more complex for programmers and more ressource consuming then loops, but functional programming languages are designed to simplify that and optimize the generated code machine to fit the needs, So all good 😉

Here’s an example, we want a function that returns the product of a list of numbers. If we do it, the old way: it may look like that, a test for empty lists, the a loop through the list, to calculate the product,

Simple hein? 🤓

Now let’s do the same with pure functional Scala:

You may not understand the code if you are new to scala, it’s a pattern match that allow us check the form or the type of the input list, called “ints”, it’s like a switch but on Type not on value, and Nil is a subtype of List which represents the empty list. x :: tail means x: the first element, and tail, the rest of the list , and finally we have that recursive call.

Sexy hein?! 🤓

(Be carful!, this kind of recursive functions may throw a StackOverFlow error if the list is too big, because it’s not a tail recursion. For more about tail recurtion **https://alvinalexander.com/scala/fp-book/tail-recursive-algorithms/** )

We came to the final part of this overview article and we will speak about Higher-Order Functions:

Higher-Order Functions:

A higher-Order function is a function that takes other functions as parameter or it returns a function.

Example : we have an anonymous function that checks whether a number is even or odd, then the filter function takes it as parameter, and finally the increment function returns the add 1 function.

In FP that’s very helpful for mapping, filtering and for other operations that need a callback

In the next articles of this series, we will talk about other advanced concepts in FP like Lazy Evaluation, Monads, Streams and Streams, Tail recursion… etc., and how to deal with side effects and much more… So stay tuned 😉.

Also, if you liked this one don’t forget to keep a thumb up and if you have any question, a remark or anything so please let me know in a comment, be sure that I'll read it 🤓

So, take care and ... See you soon.