Functional programming

Oleksandr Yefymov
Feb 20, 2019
3 min read

Updated: Feb 27, 2019

We will cover next topics:

Definition of FP
Functional Concepts
What is used for
Languages
Pros & Cons

Definition of FP

FP is functional programming and Wiki comes to us with good definition about that:

FP is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

Main idea there, is that our programm, written according to functional paradigm, doesn't contain side-effects, code is declarative and idempotent.

Declarative - means that main focus is on “what to solve”, in contrast to an imperative style where the main focus is “how to solve”. It uses expressions instead of statements. An expression is evaluated to produce a value whereas a statement is executed to assign variables.

Idempotent - the output value of a function depends only on the arguments that are passed to the function, so calling a function f twice with the same value for an argument x produces the same result f(x) each time; this is in contrast to procedures depending on a local or global state, which may produce different results at different times when called with the same arguments but a different program state

Functional Concepts

Lets review each concept from functional programming paradigm.

Such concepts are:

First-class and higher-order functions

In mathematics and computer science, a higher-order function is a function that does at least one of the following:

takes one or more functions as arguments (i.e. procedural parameters)
returns a function as its result

Scala example:

val salaries = Seq(20000, 70000, 40000)
val doubleSalary = (value: Int) => value * 2
val doubledSalaries = salaries.map(doubleSalary)

println(doubledSalaries)

Java example ( function that returns another function as result ):

Comparator<String> comparatorReversed = Comparator.<String>naturalOrder().reversed();

var names = Arrays.asList("alex", "dev");
names.sort(comparatorReversed);

Higher-order functions enable partial application or currying, a technique that applies a function to its arguments one at a time, with each application returning a new function that accepts the next argument. This lets a programmer succinctly express, for example, the successor function as the addition operator partially applied to the natural number one.

And first class functions are functions that are treated like an object (or are assignable to a variable).

Pure functions

Pure functions have no side effects (memory or I/O).

This means that pure functions have several useful properties, many of which can be used to optimize the code:

If the result of a pure expression is not used, it can be removed without affecting other expressions

If a pure function is called with arguments that cause no side-effects, the result is constant with respect to that argument list (sometimes called referential transparency), i.e., calling the pure function again with the same arguments returns the same result. (This can enable caching optimizations such as memoization.)
If there is no data dependency between two pure expressions, their order can be reversed, or they can be performed in parallel and they cannot interfere with one another (in other terms, the evaluation of any pure expression is thread-safe).
If the entire language does not allow side-effects, then any evaluation strategy can be used; this gives the compiler freedom to reorder or combine the evaluation of expressions in a program (for example, using deforestation).

Thus a pure function is a computational analogue of a mathematical function

Scala example:

def doubleNumber(number: Integer): Integer = scala.math.pow(number.doubleValue(), 2).intValue()

Java example:

//pure function
var age = Math.sqrt(64);
System.out.println(age);

Recursion

Iteration (looping) in functional languages is usually accomplished via recursion. Recursive functions invoke themselves, letting an operation be repeated until it reaches the base case.

Why is that important, and what for do we need a recursion at all?

Often we need to iterate through something, do some action in the loop, and with it there is a next problem, in case of FP (function programming). Iteration requires changing a counter - that means there must be a mutable variable, which is prohibited in a purely functional setting.

So functional languages are specially designed to operate without the need for iteration, hence the streamlined function calls with help of recursion.

In FP recursion is optimized (there are some techniques for that, like TRE - tail recursion elimination, if interesting, you can dive into that with help of Google), so it can(and must) be used instead of direct looping.