Scala Foundation Course - Functional Elements Part 2

In the part one of this session, we covered several concepts related to functional programming. The next one is Immutability.

What is Immutability?

The literal meaning of Immutability is unable to change. In a simple sense, In an FP world, we create values or objects by initializing them. Then we use them, but we don't change their values or their state. If we need, we create a new one, but we don't modify the existing object's state.
Let me give you some examples in Scala. Scala has two types of variables.

The var stands for a variable, and the val stands for value. You can initialize a var, and later you can reassign a new value to the var. Let me show you.

var s = "Hello World!" //After initializing it once, you can change it later. s = "Hello Scala!"

The next one is the val. The val is a constant. That means, once initialized, you can't change it. Let me show you.

val v = "You can't change me." //Let me try to reassign it. v = "Let me try."

So, reassignment to val is an error. You can't do it. Since Scala is a hybrid language, it supports var and val both. But when you are using Scala as a functional programming language, it recommends using val instead of var.

Why Immutable?

Using val will force you to create programs using only the constants. You might be wondering how it is possible. I mean, without changing a value of the variable, we can't even create a simple loop. Using only constants appears to be the biggest limitation. More importantly, the real world is not immutable. Whatever you are trying to model using your program will have the change in its state. I mean if a bicycle doesn't change its position, it is useless. Right? Even if you think about data, it gets updated. There is a change in its state.
And above all of that even if we try to do it, I wonder what the benefits are? Why do we want to adopt the limitation of immutable? So, behind all such arguments, we have just two questions.

How can we program without a variable?
What are the benefits?

Let's start with the benefits. At this stage, I can give you two advantages.

It helps us to adopt a mathematical approach.
It helps us to avoid various problems.

Immutable helps to adopt mathematical approach

The FP has its origin from the mathematical functions. In a real world, objects do change their state, but in mathematics, objects don't change their state. Let's consider a simple mathematical expression.

What is this expression? Let me rewrite it in a different notation.

Both are same. Right?
So, we apply a sum function, pass two integer objects with values three and one, and the function returns a new integer object with a value 4. Correct?
A mathematical function never changes the value of the existing objects. In this example, the sum function doesn't modify the input objects. However, it returns a new object.
The FP is more inclined towards creating functions in a mathematical sense and using them to solve our problems. We will learn more about it as we progress with the tutorial. But in summary, the immutability helps us to take a mathematical approach and create pure functions.

Immutablehelps us to avoid various problems

The immutability is a big thing in a multi threaded application. It allows a thread to act on an immutable object without worrying about the other threads because it knows that no one is modifying the object. So, the immutable objects are more thread safe than the mutable objects. If you are into concurrent programming, you know that the immutability makes your life simple.
But a more interesting example comes from the data pipelines. We often use immutability in data engineering process. Let me ask you a question. You have a data set. You are requested to perform a data quality operation. You want to achieve two things.

Remove the records where the date column is blank.
Change the date format of all rows into a consistent format and time zone.

A standard requirement. Right? You collected sales transactions from your retail stores all over the world. Some of them don't even have a sales date. You don't want to consider them for your analysis. Since they came from different countries and different systems, they have different date and time zone formats. You may want to convert all of them into a single format.
An essential requirement but how will you do it? Will you delete all records with a blank date? Will you update all rows to a consistent date format?
Assume you did that and a few days later, you identified a bug in your code. You can always fix your code and redeploy it but what about your data? You modified original data, and you lost the original values. You deleted some records as well. The bug in your code has corrupted your data. It's no longer reliable, and now, you have no way to fix your data problem.
The better option is to take the immutable approach and do not modify the original data set. Write one function that creates a new data set T1 by filtering out all records with a blank date.
Then a second function to convert the date into a consistent format and save it as new data set T2.
When you identify a bug in your code, you just execute the new function on the original and immutable data set.
The point that I want to make is that the immutable approach helps us to simplify the solution and avoid many problems. Even the human errors. That's why while learning Scala, we will be using val and avoid var.
Now, let's come back to the next question.

How can we program without a variable?

It looks like a difficult thing but not impossible in many cases, and the functional programming languages like Scala provide you enough language constructs to achieve that.
Let me show you a simple loop example, and a solution to achieve immutability.

def iFactorial(n: Int): Int = { var i = n var f = 1 while (i > 0) { f = f * i i = i - 1 } return f }

So, this function takes a positive number n and returns a factorial value. I am using two vars in this function. Now, I have two questions for you.

Is this a pure function?
Can you rewrite this function without using vars?

I leave the first question for you to answer. The second one is simple. If you learned any modern programming language, you must have learned recursion.

What is Recursion?

A recursion is a programming technique in which a function calls itself. You can replace most of the loops with a recursion. We use recursion extensively in functional programming. I know, recursion is one of the toughest things to use. But with some practice, you should be able to use it as a powerful tool.
Let me convert the factorial function to a recursive solution.

def rFactorial(n: Int): Int = { if (n <= 0) return 1 else return n * rFactorial(n - 1) }

So, this is it, and we also learned one more element of FP. The recursion.

Programming with immutable values.

This one example of converting a loop into a recursion may give you an assurance that you can replace your loops with a recursion and avoid using vars. But let me ask you a straight question. Are you convinced that you can program without using vars?
How can we program without a variable?
This question is still standing tall enough. But this limitation should not be a problem because you can create new value for each new state. Do you remember our data quality check example? We are not changing the original data set, but we can create two new tables. Right? You can take the same approach and create new values instead of changing existing ones. And that's perfectly fine.
Having said all that, let me tell you that we are not taking an oath to keep everything immutable. Mutability may have its definite advantages, and we are free to choose what suits best for the given problem. The point is that the immutability is a powerful thing. It simplifies the solution and avoids many problems, so it is the default approach for FP. A Functional programmer challenges every mutation and tries an immutable alternative.

What is a Trail recursion?

You already know recursion. We just talked about it. But there is another concept associated with recursion. The tails recursion. So, What is the Tail recursion?
Let's first understand the Tail.
If you have a list like (5,4,3,2,1,0), the first element is the head, and the rest is the tail. I can remove the head and create a new list. It looks like (4,3,2,1,0). Right? Now, 4 is the new head and rest of the list is a tail.
You look at any recursive algorithm, and you will realize that it always works on a list. When I need to think something recursively, I follow these three steps.

Identify the List.
Implement the termination condition.
Compute the head and recurs with the tail.

That's it. The compute is the part where you need to think. Rest is same for all recursion implementations. You can quickly test these steps for the factorial function.
The list is (5,4,3,2,1,0).
The termination is the 0. To compute the factorial, you can't multiply with a zero, so we return 1.
The compute part is a multiplication of the head with the new head in the tail. That's it. So, recurs with the tail to get the next head and multiply it with the current head.
But, there is a catch here.
You can't multiply the head until you discover the next head from the next call. So, your runtime environment will keep the head in the stack and make a new call. And this goes on until you reach the termination. Every call is waiting for the next call to complete. So, the actual multiplication happens when we reach the termination condition, and the chain of calls starts folding.
So, each recursive call requires a frame in the stack. That's a big problem. If your recursion goes on for thousands of calls, you may run out of memory. That's a significant limitation with the recursion.
You can quickly check the stack by throwing an exception. Let me throw an exception at the termination.

def eFactorial(n: Int): Int = { if (n <= 0) throw new Exception("boom!") else return n * eFactorial(n - 1) }

If I call this function, I get an exception and the stack trace is visible.
You can see those six calls. You will see six entries in the stack. One for each recursion call. Every entry consumes some memory. But if you implement same logic using a loop, these stack frames are not used.
So, what do we conclude?

Is a loop better than a recursion?

If you consider memory requirements and performance, the answer is a definite Yes. So, loops are more efficient than recursion. Scala compiler knows this and tries to optimize the recursive calls.
But we must redesign the recursion is a way that there are no unfinished operations for the next recursive call. That is where the tail recursion come in.
So, By definition, A tail call or a tail recursion is a function call performed as the last action.
What does it mean?
It means that your recursive call should be the last operation in your function.
If we look at the factorial function, it waits for the recursive call and then multiplies the result with n. So, the multiplication is the last action.
To make it a tail recursive, we need to change it in a way that recursive call becomes the final action instead of the multiplication.

How to implement tail recursion?

Not that simple but yes, you can do it by applying some trick.
In the old logic, the first multiplication happens when we reach the termination condition, and we get one as the last number. Instead of returning one at the termination, we can take it in the beginning and perform the multiplication before the recursion call.
To implement this trick, you need two input parameters.
Here is the code.

def tFactorial(n: Int, f: Int): Int = { println("Calling tFactorial.") if (n <= 0) return f else return tFactorial(n - 1, n * f) }

So, f must be one for this function to work.

This code implements tail recursive factorial because the recursive call is the last action. When the Scala compiler recognizes that it's a tail recursion, it will optimize the function by converting it to a standard loop. We will not realize the change, but the compiler will do it internally. This optimization will overcome the performance and memory problem. If you want to prove it, you can again implement an exception and double check it.

def tFactorial(n: Int, f: Int): Int = { if (n <= 0) throw new Exception("boom!") else return tFactorial(n - 1, n * f) }

You can see that there is only one function call in the stack trace because the compiler converts the tail recursion to a loop.
Good, that's all about tail recursion. Just one last thing. If you think that a factorial function with two input parameters looks odd, you can wrap it into an outer function. Here is the code.

def Factorial(i: Int): Int = { println("You called Factorial for " + i) def tFactorial(n: Int, f: Int): Int = { if (n <= 0) f else tFactorial(n - 1, n * f) } return tFactorial(i, 1) }

So, the Factorial takes just one parameter, and it internally calculates the factorial using the tFactorial function. The tFactorial is a local tail recursive function. I kept this println statement because we will be using this print message in next topic. However, println is a side effect, and you should avoid such things in functional programming.

Scala Statements vs Expressions

This item should be the simplest one. If you know programming in any language, you already know Statements. A statement is the smallest stand alone element that expresses some action to be carried out. For example.

This one is a statement. There is another common term. Definition or Declaration. For Example.

We often call it a definition. A definition is also a kind of statement. It is a statement that defines something. With this information, we can say that a program is nothing but a sequence of statements. Here is an example.

def myResult(m: Int) = { var r = "" if (m >= 50) r = "passed"; else r = "failed"; println(r) } myResult(65)

If you carefully look at this small program, you can extend the definition of a program. I can now say that a program is nothing but a sequence of statements that modify some program state.
In this program, we have an 'if' statement and then we have a print statement. Both statements are modifying something. The 'if' statement is changing the state of r and print changes the state of the console. The first line is a definition, and we leave the definition aside from this discussion.
Now, since we understand the statements in imperative programming, lets come back to the functional paradigm.
In FP model, we have definitions and statements, but every statement should have a capability to return a value. That's the ground rule for functional statements. This rule is even valid for print statement. Let me show you.

So, the println function returns a Unit. The unit is like void in Java programming. But it is not exactly same as void. The void means nothing whereas unit has a value. We represent the unit value using () symbol.
So, the point that wanted to make is that every statement in Scala can return some value. Even a Scala loop can return a value. We will learn more about Scala language in future videos. But for now, just remember that since Scala is a functional programming language the statements in Scala can have a return value.
Since a Scala statement returns a value, some people don't call them a statement. They call them an expression. So, it is common that you find people saying that Scala doesn't have statements but only expressions.

Why Scala supports expressions?

Finally, you might be wondering about the benefits of a statement returning a value. I mean, we learned that functions return a value but why do we want every statement to return a value. What is the benefit?
When you start practicing FP approach, you will realize that using functional statements allows us to reduce the number of variables in our code. Removing the variables from your code helps you to achieve immutability. I mean, if you don't have a variable, you don't need to mutate it. Right?
Let's come back to the myResult function. This code is imperative. Let's make it functional.

That's it. You can print your result by calling this function.

The 'if' statement returns a value hence we don't need a variable. The functional version of the code is concise, and the returning statement helps us to eliminate variables and achieve immutability.
Good. So that's all about statements.
Thank you very much for watching learning journal. Keep learning and keep growing.