Launching our Functional Programming Track
As you might have noticed, we recently started work on a Functional Programming section. At this point of time, we have a track with introductory problems and a lot more exciting ones are in the pipeline.
There’s an interesting paradigm shift in the Computing industry towards Functional Programming. Here, for instance are lists of companies which have started using Clojure and Scala in production.
Clojure:
Who’s using Clojure in production?
Scala:
What startups or tech companies are using Scala
So, we note that even biggies like Amazon, Twitter and LinkedIn are making at least a partial shift to Functional Programming.
What is Functional Programming?
Functional programming treats computation as the evaluation of Mathematical Functions. A functional program does not resemble the typical sequence of instructions which one finds in an imperative program, and it avoids mutable data, extra variables and state. Here I illustrate a few simple tasks with a comparison of their functional and imperative pseudocodes to drive home the difference.
Task #1: Given an array of positive integers, return an array which contains only the multiples of three from the original list
Functional Pseudo-Code
original_list.select{|x| x%3 == 0}
Imperative Pseudo-Code
filtered_list = []
for each element x in original_list:
if x % 3 == 0
add x to filtered_list
end_if
end_for
return filtered_list
Task #2: Given an array of integers, multiply each integer by 4
Functional Pseudo-Code
original_list.map{|x| x^2}
Imperative Pseudo-Code
multiplied_list = []
for each element x in original_list:
append 4x to multiplied_list
end_for
return multiplied_list
Task #3: Given an array of integers, find their product
Functional Pseudo-Code
original_list.reduce(multiply_function)
Imperative Pseudo-Code
product = 1
for each element x in original_list:
product = product * x
end_for
return product
The General Take-away from the above code snippets
The above snippets are really small, but hopefully they will convey the general idea, that functional programming, is heavily dependant on the evaluation of functions and expressions, and avoids direct change in state. Imperative programming, is a sequence of instructions, introduces new variables and involves changes in state.
Why is Functional Programming Important?
Because this involves functions with no side-effects and changes in state, and the order of execution is not so important. This also resembles the mathematical functions and expressions a lot more, so is perhaps more intuitive.
The main advantage that we get from having no side-effects, is the inherent parallelism that it can manage to support, as we move towards more cores in the CPU, and more nodes in distributed systems. The popular map-reduce paradigm is also much easier to understand if one has an understanding of functional programming.
While it might be a bit far fetched to say that it can completely replace the imperative and Object Oriented paradigms, it is realistic to assume that mixed paradigm langauges like Scala will become extremely popular, with compute-intensive parts of code bases written in the functional paradigm, with a focus on making those parallelizable or distributed.
Pre-requisities
There’s no pre-requisite really, and a functional language can often be a great CS101 course for a complete newcomer to programming. For the theory inclined, one thing to note, is that other programming languages, use the Turing model of Computation whereas Functional Languages are based on Lamba Calculus. So it might help a bit to understand Lambda Calculus and monads, but please don’t let the terms scare you away.
Resources
The material from the Scala course on Coursera can be a great starting point:
Functional Programming Principles with Scala
This course was taught by Martin Odersky, the creator of the language, who teaches it as it should be taught: with a strong emphasis on functional programming principles, in stark comparison to a lot of other resources which introduce Scala as an improved Java. Scala is a mixed-paradigm programming language, which is quickly becoming popular, and is being used at LinkedIn and Twitter.
Apart from that, you might also find this course on Udacity both interesting and useful- The Design of Computer Programs, by Peter Norvig
Note, that the above course is in Python, however even Python has a lot of support for various functional programming style features and keywords (like map, reduce, closures, lambdas, comprehensions and generators) and this course might be ideal for those who simply want to learn functional programming principles to include them in their regular programming tasks to create more elegant and readable course.
Lastly, do take a look at some of the content available in SICP: The Structure and Interpretation of Computer Programs.
This introduces computer science and programming, with a heavy emphasis on the functional paradigm and is a very well respected resource. This serves as the text for an intense introduction to CS at MIT, Berkeley and a lot of top universities. The SICP courses were originally LISP based, but some have now switched to Python.