Introduction
Hello there, Andrei Muja here, back with new content for you.
In this article, I will present what is functional programming using Scala and why it’s crucial in building high performant and quality products. Many of the functionalities shown are common in other languages too, therefore anyone with coding background in any language can easily follow the content. If, however, you are new to programming or do not know Scala at all (I will not tackle any language introduction), I suggest you first check my other article here: Scala Introduction, then come back and follow along. Furthermore, I will present some insights about this elegant language, the advantages and disadvantages of functional programming, along with a couple of small algorithmic problems solved in 100% functional style. At the end of the content, I hope you leave with a different mindset which could benefit you in your career or give you several ideas to start a personal project using new technologies. Note: we will still use Scala version 2.13, but examples are compatible with Scala 3 as well, we do not tackle any syntax changes.
What is Scala?
To recap, Scala is a statically typed programming language who supports both object-oriented programming and functional programming. It started as a project in Switzerland, at École Polytechnique Fédérale de Lausanne, by Martin Odersky and released in 2003. Since then, it came a long gaining popularity within big corporations, such as Twitter, Zalando and Coursera. The community keeps on growing, especially in Romania where it’s at an “infant” level. It has a lot of frameworks, one considered to be the most secure, Lift, and libraries developed and managed by a group of creative people with common interests who put passion in their work to deliver high scalable solutions keeping code expressivity in mind. It runs on JVM, same as her older “brother” Java, and younger one, Kotlin.
Functional programming?
Before diving into functional programming, or FP in short, let’s first define what is a function. Most of you should know this term from your early years in school. Mathematics maybe? So, what is it? A function connects an input with an output. To go from a place A to B, we go through an operation. A function takes elements from an initial set, called domain and extracts them into another set, called codomain, with every input producing exactly one output. Enough about math, how about programming? Well, in functional programming, functions are the stepping stone in creating programs. That’s not enough, however, we would, ideally, want to deal only with pure functions and immutability. There are various functional constructs that we can create in object-oriented programming too, like functions that take or return other functions and methods that are defined inside one another. But in functional programming, these occur naturally and are alsome everywhere. You could call this paradigm mathematics “on steroids” for programmers.
Scala FP characteristics:
Some of these characteristics can be found in other functional languages, like Haskell, Clojure, or even Java with streams (1.8 and forward) and Javascript. However, I will cover them using Scala and how powerful are specifically in this environment.
1. Immutability: imperative or object-oriented programming deals with modified data called mutable state. We don’t do that here. We want every value to remain unchanged without possibility to be modified after creation. The most important aspect here is that immutable objects are thread safe and lead to fewer errors. Of course, some values can be changed, but in a very special way, using a construct which Scala names as case classes. For more info, as I said in the introduction section, you can check my other article where I present in detailed fashion Scala’s main features. By creating a copy method on the object, we can easily change one of its properties. See below image:
Asteroid’s diameter was changed, even though object has immutable values
2. Pure functions: they have a couple of properties: Firstly, they should always return the same value for the same inputs. Secondly, take this simple function:
We can replace the piece of code with the resulting value and vice-versa without changing the meaning or the result of our program. This is called referential transparency, a powerful concept which gives a developer the chance to reduce repeating code and write quality clean-code. Anywhere we encounter this method, we can simply replace with add (4, 5), 4+5 or 9.
Pure functions lack of side effects: thinking from an imperative perspective, almost every function has side effects, from changing content inside a collection (who by the way, Scala collections are default immutable, I will convince you later this is true 😊) to throwing an exception. In functional paradigm, we eliminate this, thus, functions are easier to be tested and have a deterministic behavior. In Scala, functions always return a value, even if an error occurred. Our beloved language takes care of this by introducing objects who wrap successful or error values (Option, Either, Try). Again, check my introductive article if you want to learn more.
3. Composition: coming back to math, the function (f ∘ g)(x) = f(g(x)), ah, good old high school memories, for all x in its domain is an example of composition. In programming, we simply pass result of the first function call as an argument for the second. Example below shows this, using Scala’s built-in method “compose”. Defined as trait, it creates an anonymous function which accepts a value, applies the internal function g, returns its value, passes it inside the external one, f, and gives our final result.
Let’s see a composition function in action:
4. High-order functions (HOF): they take one or multiple functions as parameters and return a function as a result. The best explanation is a practical one. Let’s consider we want to calculate a distance in different unit measures. We can create a function to transform meters in yards, inches or miles.
First method is a HOF which returns the function we pass as parameter. Notice inside variables there is no need to write parentheses for different calculation methods since Scala already knows what to do. Take a look at the next example where I make use of pattern matching to show the power of HOFs:
Calculating the mass of different planets is possible by passing a function based on a String planet match. If there is no match, or we have the default case written here with wildcard symbol “_”, simply return the weight from our dearest planet Earth.
5. Anonymous functions: if you were paying close attention, you may have noticed I mentioned this concept earlier. Some of the most used collection methods (which I will dive into later) take an anonymous function as an argument. It has no name, but has a body, input and occasionally a return type. They appear under different naming such as: function literal or lambda expression. Here is a small example of creating another list whose values are greater than 12, our condition, from a range of numbers between 1 and 20:
6. Closures: they are also functions, but use one or more free variables. Hmm, what are free variables? Well, they are just plain variables which are not local ones nor formal parameters. Check following image:
7. Partially applied functions: When only a subset of the parameters is passed to the function, the function is called a partially applied function. Once the required initial parameters are provided to the partially applied function, a new function is returned with the rest of the arguments needed to be passed. Consider this:
Method “calculateSimpleInterest” takes three arguments — initial principal, rate and timespan. Rate was set to 0.2 for the interest. Here, we simply pass the first two parameters to the function and return a new function “valueAdded” with timespan as a missing parameter. Then, use “rateApplied” without being bothered about the value of the timespan, which in turn becomes 2 years.
8. Currying: when dealing with functions that take multiple arguments, we can rearrange the method into a chain of calls, each taking one argument. The function returned is passed as new argument and so on.
Function has two arguments; we can convert into a curried one or use “curried” method. Result is the same. As a good practice, Scala creates multiple arguments list, as seen for 4, 5 and 6 below:
9. Tail recursion: Loops are based on mutable variables. Is there any way to get rid of them? Of course. Java-like code is permitted in Scala, we could even write recursion in the “old” way, but is discouraged since there is a better approach in terms of mutability and stack optimization. Tail recursion reuses the same stack frame for each consecutive recursive call. If you write a tail-recursive function, do not forget to annotate it with @tailrec which will trigger the compiler to check your code and analyze whether code is optimized or not. Following example shows how we can write a tail recursive solution to find if a number is a palindrome or not.
We define a method inside another one, a classic Scala way to code to avoid duplication and messiness. Annotate method “go” with @tailrec, then make the last call from the bigger method to be the recursive one.
Important immutable collections methods
With FP properties under your belt, in this chapter, we will dive into some of the most used collection methods in Scala environment. All of them are high order functions and are the building blocks in creating scalable code, easy to maintain and thread safe.
1. Map: creates a new collection by applying a function to transform each element of the initial collection. It has the following form:
A collection having elements of type A will be transformed by function “f” into a collection with type B elements.
For all football fans out there, below is an example of using map. Each of the Premier League team has the prefix of “Big Four” to remember the good old days when they dominated English league.
2. FlatMap: creates a new collection by applying a function “f” to every element and all sub elements formed are “flattened” into one single resulting collection. It can be defined as a trait:
Suppose you are given a sequence of numbers and are asked to create a list of numbers containing each initial value followed by its double. You can use flatMap method, which is recommended, or map along with “flatten”. The latter would give us a warning, not wrong, but why complicate? If you would have printed out the value before being flattened, program would have responded with a list of lists of tuples (at line 14).
What happens internally can be seen analyzing the diagram:
3. Filter: constructs a collection having only the elements which satisfy a condition or predicate, while old values not corresponding are deleted.
To demonstrate what power this method holds, let’s shorten the list of colleagues containing only those whose name contains letter “r” or “R”. Example:
It eliminated all names with no “r”/ ”R”. You can take a look at this diagram to see how it works behind the scenes:
4. Reduce: applies a binary operator to pairs of elements (taken as tuple) successively until returns the result needed. It comes along with some derivations too: reduceLeft, reduceLeftOption, reduceOption, reduceRight, reduceRightOption. We will focus only on the first one. For empty collections, function “operator” throws an UnsupportedOperationException exception.
Coming back to example before, let’s say we want to return the longest name from our list. We can do that with reduce, or reduceLeft, they are interchangeable. Then, I would like to get the product of some scores at a game. Again, reduce comes to play:
Internal diagram looks like this:
5. Fold: applies a binary operation on collection’s elements, but has an initial value, or a “seed” which can be reused. Almost a carbon-copy of reduce method. Counterparts: foldLeft, foldRight.
As part of demonstration, consider we want to know the sum of lengths of all colleagues’ names. Then, concatenate all names from right to left. Apply foldLeft for the first operation, then foldRight for second one. Keep in mind seed value has to determine the result type, in first case Integer, second case String. Result here:
Internal structure:
6. ScanLeft / ScanRight: create a collection with the intermediate results of applying the binary operator “op” to every element, going from left to right, or right to left. Initially, the seed is introduced in the operator.
Return again to our list of colleagues and try to do a successive concatenation, from the big list to only one element with scanRight and successive scores sum through each iteration using scanLeft. Note: I dropped the last element, which was a comma, for concatenation using dropRight(n), meaning delete the last n elements, in this case being 1. Final results:
If you would like to check how they work under the hood, here are their diagrams:
scanLeft and scanRight
7. Zip: creates a whole new collection by pairing each element with another element from a second collection which has the same position/index, discarding unpaired tuples. There is another structure, zipWithIndex, which pairs every element with its own index. Also, zipAll, which pairs elements from two collections and if one of them is shorter, it adds placeholders to have same length as the other.
Coming yet again to our colleagues, what if we pair them up with their scores? We can simply do that by calling zip method. Here is how it’s done:
As you can see, all colleagues whose index do not have a match in scores are discarded
Diagrams for zip, zipWithIndex and zipAll:
8. Collect: build a collection with elements as a result of applying a partial function “f” on them and discarding the rest.
I am interested now in having a list with my colleagues’ names whose length are even. Use a collect method like below and check result. If no name length is even, return me an empty list:
And its diagram:
FP approach to several problems:
Now that we know some functional programming techniques, I have a couple of small miscellaneous problems we will tackle together. These tasks can be implemented in different ways, even in Scala, choosing a more imperative approach close to plain old Java, but this section focuses on solving them pure functionally, focusing on maintaining immutability.
But before going through them, I would like to go through two meaningful concepts which are LazyList and View. LazyList, initially called Stream, describes a “theoretically” infinite list that evaluates, when necessary, in a “lazy” fashion. The only downfall is that sometimes it persists the values in memory longer than needed. Any workaround? View comes to help!!! View builds a structure that “mirrors” another structure, until “forced” by an eager operation like “.toList”, “.foreach”, “.forall” and “.count” methods. Instead of creating a new list for every stage, you evaluate new items sequentially, meaning more optimization and better performance. Okay, enough with theory, time to put the new knowledge into practice.
1. FizzBuzz: a classic programming question which quickly tests your skills and attention. The problem statement is: for every number, you should be able to output ‘Fizz’ if it is divisible by 3, ‘Buzz’, if it is divisible by 5, ‘FizzBuzz’ if it is divisible by 15, and in all other cases such as ’31’, return ’31’. Of course, it can be done in mutable fashion, other languages even encourage this. But, since we became functional Scala whiz kids, we developed a different mindset. Check below code snippet for a possible solution:
Firstly, we construct a map from number to a word. Most of the programmers would proceed to add numbers 3 and 5 in the logic of the ‘fizzBuzz’ function itself, with an “if” condition. With Scala’s ‘collect’ method learned earlier, you can do a ‘filter’ and a ‘map’ operation simultaneously, saving on typing. Collect all the numbers with their corresponding words, and get a List as output. If there are no words who check the process, just return the original number; otherwise, return the combination of words.
2. Find anagrams: given a word and a list of words, return only the list of those who are anagrams. While in many other languages, it would require a couple of lines of code, Scala offers a very compact and straightforward solution. All you have to do is:
Filter the words in the list by transforming them in lowercase, then sort with “sorted”. Instantly -> same word resulted, it’s a match, bang, anagram!!
3. Find first unpaired type in an array: If you were to group each member of an array with another one of itself, would there be any that cannot be grouped? If yes, return the first. If not, return None, as part of an Option.
This problem applies to any type, it does not matter if we have numbers or strings, which is why generic types of Scala, with template [T] comes in handy to implement the solution. You simply create a Set, and as soon as an item is encountered, remove it from the set, and append to the set if it is not – in conclusion, any item remaining in the set is basically the unpaired item.
4. Fibonacci, immutable way: well known sequence: 0,1,1,2,3,5,8,13,21… where every element is the sum of the previous two elements. Goal here is to compute it in pure-functional immutable way. Here is how we proceed:
By stumbling upon this problem, we can use a property of LazyLists, which is that they memoise the items: we compute a result only once it is needed, and then store it for future retrievals. Memoisation could resemble a caching mechanism. In this solution, we zip the LazyList with itself. The catch? Lazy val is initially defined with the first two values; and when more values are requested, values are computed on demand. By zipping, we are effectively performing the f(n+2) = f(n+1) + f(n) (we use “.tail” to combine the two LazyLists).
5. Pascal triangle: print only the nth row. In a Pascal’s triangle, a number in a row is created by adding the two numbers directly above it; the first row contains only 1, the second row contains 1 plus another 1 and so on. A sixth row would have values: 1, 6, 15, 20, 15, 6, 1. Write a program to print 6th row of Pascal’s triangle, how about 9th row?
Observation: the next row’s items are actually a sum of pairs of previous row’s items, combined with previous row’s items shifted. In short, sum the original row with the original row slightly shifted (0 added). It is a perfect time to use zipAll which fills in either of the lists with default values (thisElem / thatElem) so that the total length would be that of the higher of the two lists. When we integrate them, we make use again of Lazy List. It also comes with an apply(Int) method to select a specific element from the LazyList to be used for testing method.
6. Problem: given an input: “aab”, “ca”, “ac”, “ba”, “caa”, “d”, “bab”, write a program to return a map of values for strings composed of same letters. Words “aab” and “ba” are treated as the same since they are made of “a” and “b”. In short, output should be: Map(ab -> 3, ac -> 3, d -> 1). Code snippet below is one of many potential solutions:
7. Write a code that creates map function using foldRight and filter using foldLeft as internal methods. This example is purposely done for education, to show it is quite feasible to “build” a method from another if considered “canon” in Scala’s library. After seeing definitions for map and filter, can you represent them using other HOFs? Of course, here is a solution:
Notice how map takes as initial seed an empty list of type B, then for every tuple (a, b), adds function of a at the beginning of the list, using “::” method defined for lists. For filter, we start with an empty list of type A, then for every tuple (a, b), if predicate is evaluated, we append “a” element to “b”, else we simply return “a”. That’s why we first encounter 4, then 2 in the returning list.
Why is functional programming so important?
The appearance and use on large scale of JVM languages who work under devise “write once, run anywhere” has allowed programmers to interact as little as possible with low-level programming concepts who deal with memory management. Unfortunately, even these languages have their limitations. Quick evolution in processors production which now have more integrated cores rather than faster clock rates led to a significant increase of performance. Modern applications have to handle incoming millions of requests in just a couple of milliseconds.
Companies thrive on competing for having the fastest and resilient solutions. Key is to design and implement multi-threaded and fully distributed applications. Grab yourself a cup of coffee or tea and go back on memory lane only to discover that several corporations had to reshape their architecture from ground up to fit their clients’ needs. For example, Wix.com refactored their entire application from monolith to separate microservices, thus improving scalability. Another company that faced same issues was Twitter, by shifting from a programming language to another because it lacked native thread support, again messing up with performance. That language was none other than Scala. The language was barely existent at that point, but desire to build fault tolerant real-time searches was essential, and Scala could do it.
Ok Andrei, we understand, but what has anything mentioned above to do with functional programming? Well, functional programming simplifies everything when it comes to multithreading and distributed systems.
The transition is easier from an OOP based language to a functional one rather than vice versa if you put in the effort. That’s exactly what Twitter guys faced years ago. Scala’s advantages are not to be neglected: immutable objects, I cannot emphasize enough on this, it relies on functions, best suited for big data analysis (Kafka, Flink). Few languages come close to Scala when designing software with high quality and performance as main objective.
Are there any disadvantages?
Andrei, I saw what functional programming can do, it’s great, no doubt. But are there any disadvantages? As every programming parading, functional one is not perfect, actually not even close, here are a few reasons why:
- Writing pure functions is easy, but combining them into a complete application is difficult and requires attention;
- Shifting to FP, eventually you will encounter some advanced math terminology (monad, monoid, functor, used in FP libraries as first-class functions) makes coding intimidating, especially for programmers with years of experience with imperative style, cannot adapt quickly or hate mixing math with programming;
- Recursion is a slow killer. You would have to practice a lot, hidden patterns can be found almost under every algorithm, and you could get used to this flavor, but is not everyone’s cup of tea, plus excessive recursion functions definitely lead to memory problems and headaches;
- Because you can mutate existing data only using “copy” method from case classes. Especially found in nested code, or structures, similar to OOP standards;
- Pure functions and I/O don’t mix well. No language is entirely pure. Besides, there will be real world cases when you deal with database operations, or files, or functions that are mandatory to mutate data;
- Using only immutable values and recursion can potentially impact RAM use and speed. Scala also has a huge advantage and a drawback, both resulting from the fact you can combine OOP with FP.
Conclusion
Wow, that was a journey! Just to summarize, functional programming gives a lot of flexibility and makes code more elegant. Multithreaded applications have never been as fast and less error-prone as now and will keep getting better. As you saw, it’s not always possible to create a 100% functional system from scratch. The objective is to minimize the amount of mutable state as much as possible and maintain the rest of the code purely functional. Functional programming is the best candidate when it comes to developing distributed services with millions of requests per second. I hope that after reading this article you will consider using this paradigm every day, work or passion.
Check your knowledge about the concepts presented here and many more Scala here: https://www.scala-exercises.org/ Don’t forget to login with your Github account. For visual representation of most HOFs out there, visit this link: Scala HOFS.
The joy of learning a language is felt the biggest when practicing, a lot. Here are some useful links for reference which I visit regularly:
- Baeldung -> tons of resources on Java, Spring Framework, Spring Security, but also Scala. In my opinion, one of the best places to learn JVM technologies for free on the internet;
- RockTheJvm -> Youtube channel with lots of tutorials and tips and tricks. The best part is the creator is Romanian and one of the biggest contributors to Scala community worldwide;
- Academy Lightbend -> company behind Akka framework used in distributed applications with high real-time data traffic. They also offer free and paid certificates to learn Scala and Akka. Play framework also falls under their umbrella;
- Documentation for FP libraries: Cats, Cats Effects, Monix, and lately, with huge popularity, ZIO. The last one is pretty hot on market right now, so learning functional programming opens new opportunities to work with cutting edge tools, building type-safe, resilient and asynchronous products.
As you saw, Scala is not the best language to start your programming path, but if you have a good grasp of mathematical concepts and are a complete novice, give it a go. For experienced programmers who want to enter functional world, I have news: Scala excels on functional programming, get your hands dirty, then come back with feedback. I am pretty sure your mindset will change and make you a better programmer by shaping your problem-solving skills like you never thought was possible. Disappointment is not an Option, wrap it with None 😊.
If you have questions or any of the readers who are already working with Scala and / or would like to share their experiences, you can find me on Linkedin.
1 Comentariu
rqprxnyih
The complete guide to Scala Functional Programming – 24 Code Examples
[url=http://www.gr3jw3y3226o3l7l1x2d6817maqzi9r6s.org/]urqprxnyih[/url]
arqprxnyih
rqprxnyih http://www.gr3jw3y3226o3l7l1x2d6817maqzi9r6s.org/