A Brief Introduction to Functional Programming Paradigm and Scala
Motivation
This article is based on one of mine 60-minutes internal sharing with my colleagues, most of them are not familiar with the topic. The sharing did not receive the effect as I expected. That is, most of them do not feel comfortable following through the sharing. I must admit, it is not well-organized (takes me about an hour to prepare the content). Still, I consider it as a good material to give people a quick intro to this topic. I personally want to do a post mortem for this sharing. Moreover, it may also inspire people who want to share the concept of functional paradigm or Scala to do a better job than I did. Therefore, I post this material here, edited with considerations during the preparation and findings after the event.
Paragraph in italics are my considerations while preparing the material or findings afterwards.
Notice that the snippets in this material ignore error-handling, boundary-checking, etc to keep brevity.
The full code as Scala worksheet used in this sharing is available here.
Start of the material
What is functional programming?
It is a paradigm under declarative programming, a pure functional programming program consists entirely of functions, where the word function here means function in math, not in programming languages, which are relation between sets, such as f(x) = x * 2.
Programming paradigm is about how you write programs. There’s more than one way to skin a cat. You may want to write a program which order the computer do step by step as you say, which is an imperative approach, or you could declare what you want, which is a declarative approach.
Consideration: Personally I think the phrase skin a cat is cruel, but to pretend to be a better english speaker, I decided to take risk of being sued by animal protection organization.
Why functional programming?
- no share stats => avoid race condition => enable parallel
- referential transparency => no side effects (so there is no for-loop in strict-functional programming)
- modularity => easy to write/read/debug/reuse
Finding: I actually did not illustrate the concept of share stats and referential transparency during the sharing. Consider to modify this. Maybe add some related snippets. This material do show some aspects of modularity, but perhaps the example is too trivial so that audience would not appreciate it.
Why Scala?
- support different programming paradigm
- the language behind Spark, Kafka etc.
- High sweetness: bunch of syntactic sugar
- A language invented by a German! — Martin Odersky. (the sharing was held in a german company)
Consideration: I personally think Scala is great language to introduce functional programming, 1) as a language that widely used in industry (unlike Haskell), 2) support multi paradigm so that my code examples can be written in a single language.
Finding: Scala do contribute some difficulties to follow through this material.
How to write a function to calculate factorial?
The following is two different ways to implement a function to calculate factorial. The iterative approach is essentially imperative, whereas the recursive approach is written in a functional way (Of course you can further improve it to a tail recursive way).
Consideration: here I want to take an example that is not too simple to bore the audience but also not too hard to overwhelm them.That’s the reason I decided to use factorial().
Higher order function
The idea of higher order function also comes from mathematic. A higher order function does at least one of the following:
- takes one or more functions as arguments
- returns a function as its result.
Introduce map() as a higher order function
The following is an imperative implementation of map() function. As we can see here, it takes an array and a function f() as input, then applies the function f() to every element in that array to produce the output. You can see why it is called map since there is a relation between the input and output.
Consideration: the map() function here is written in an imperative way to make audience easier to digest. The type is converted from List to Array to make it more familiar to the audience, since the concept of List in functional programming may confuse them.
Introduce anonymous function
Anonymous function (or lambda function, which comes from λ-calculus, which is then a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution) make it easier to write function that we may only use once. It is useful because function is first-class-citizen in functional programming. When dealing with higher order function, we often use anonymous function as input/output of it.
Another map() implementation, but functional
The following snippet shows a unique thing that makes functional programming both elegant and easy to understand: Pattern Matching!
Consideration: Make comparison between the functional and imperative implementation of the map() function. I think it could convince people that for this very task, namely implement a map() function, the functional way is elegant and easy to understand.
Finding: Turns out it is not easy to understand for beginners. Most people who do not have previous experience in functional programming tend to stuck at this step. The arrow and concat symbols are foreign to them. Although it is an easy concept, most people do have hard time while dealing with foreign symbols (thinking about it when you reading a math paper).
Introduce reduce() as another example of higher order function
The function reduce() takes all the elements in a collection and combine them by using a binary operation to produce a single value. That’s why it is called reduce, it essentially reduces type Collection[T] into type T. Notice that here in Scala syntax we use square brackets instead of angle brackets.
The following snippet is an imperative implementation of reduce().
Voila! Now you know the famous map/reduce() programming model, introduced initially by Google, which further lead to the birth of the popular Spark framework. Guess what, it is written in Scala! Under the hood it replace the ordinary collections we used in these examples by parallel and distributed collections.
WARNING: To be able to run reduce() in paralleled, such binary operation should be a “commutative monoid”, i.e. an operation that is both commutative and associative such as add, multiply. But not minus or divide.
Consideration: Introduce reduce() to show another example of higher order function. It complements with the previous introduced map() function, so that audience can know how the famous map/reduce programming model works, which I think it will be a pretty cool takeaway. Like what I did to introduce map(), here I also first show the implementation of reduce() in an imperative approach.
Another reduce() implementation, but functional
Consideration: Here again, like in the map() example, introduce the functional way to re-implement reduce(). And it is also another example of pattern matching to give the audience an idea how powerful it is.
Finding: Since most people may not fully understand pattern matching during the first example. They could encounter more difficulties in this example. I think I have lost most of the audience’s attention at this time in my sharing.
Re:Invent factorial() but functional
Now let’s re-implement our old friend factorial(), but this time, we want to do it in a functional way, based on what we have seen so far.
As we can see here, we can use the reduce() function to implement the function factorialFunctional().
Consideration: here I go back to the factorial example at the very beginning, to deconstruct what it really means to calculate factorial. By using the reduce() function to implement the factorial() function, I expect the audience could better understand what reduce() do.
Finding: Most people feel confused and just stop listening.
One more thing: higher order function again!
Here is yet another implementation of factorial(). Here we have the higher order function higherOrder() to produce the factorialHigherOrder() function.
Moreover, we can also produce the function sumHigherOrder() via the same higherOrder() function! It is essentially a way to make the program to gain more modularity, right?
Consideration: here I take again the factorial example, but using a higher order function higherOrder(), which return a function, to produce the function factorialHigherOrder(). I also want to illustrate the modularity aspects of functional programming. I expect that audience can better understand what a higher order function actually is and what reduce() actually do. I hope to receive some “a-ha!” from the audience.
Finding: unfortunately, zero “a-ha!” received.
Further readings
- Why functional programming matter, a paper with great ideas and great examples, written by John Hughes
- Programming in Scala, an authoritative book, written by Martin Odersky, Lex Spoon, and Bill Venners
- MapReduce: Simplified Data Processing on Large Clusters, the famous MapReduce paper, written by Jeffrey Dean and Sanjay Ghemawat from Google
End of the material
Post mortem
It is hard to do a blameless post mortem here. I am the one who failed to deliver the result I expected. This material is too heavy and the content is poorly organized. Pattern matching is confusing to beginners. So does higher order function. The syntax of Scala is also hard to understand. The main example should have been sum() instead of factorial(). It should have been at least divided into two subtopics: Intro to Functional Programming and Intro to Scala. My presentation skill is also in novice level, which make it harder to follow through.
Thank you for reading :)
