X

Break New Ground

The Power of Functional Programming

Arvind Kumar GS
Senior Member of Technical Staff

What is Functional Programming?

Functional Programming paradigm can be equated to the mathematical equivalent of y = fn(x).

Mathematical definition:

A function is a process or a relation that associates each element x of a set X, the domain of the function, to a single element y of another set Y (possibly the same set), the co-domain of the function.

Function

How does functions benefit programmers?

Functions have certain properties that make it favorable, especially when you want your code to seamless work in a multi threaded concurrent environment. Some of its notable properties are:

  • Functions are idempotent, that is calling a function multiple times with the same input yields the same output.
  • Functions can be chained. For example,

    Given two functions f\colon X\to Y and {\displaystyle g\colon Y\to Z} such that the domain of g is the co-domain of f, their composition is the function g\circ f\colon X\rightarrow Z defined by

    (g\circ f)(x)=g(f(x)).

  • Functions are associative, if one of {\displaystyle (h\circ g)\circ f} and {\displaystyle h\circ (g\circ f)} is defined, then the other is also defined, and they are equal. Thus, one writes {\displaystyle h\circ g\circ f=(h\circ g)\circ f=h\circ (g\circ f).}

These properties enforce immutability in the way the functions are written. For example, in Java streams, only variables declared as final can utilized inside the anonymous functions used in streams.This makes functions to be easily utilized by parallel streams.

Kotlin

Kotlin is an  open source, cross platform, statically typed, general purpose programming language with type inference. Kotlin is designed to be fully interoperable with Java, and the JVM version of its standard library depends on the Java Class Library,[2] but type inference allows its syntax to be more concise. Kotlin mainly targets the JVM, but also compiles to JavaScript or native code (via LLVM). Kotlin is sponsored by JetBrains and Google through the Kotlin Foundation.

Functional Programming Constructs in Kotlin

Traditionally functions take parameters like primitive types. However functions in Functional Programming, can consume other functions as well. These functions are called higer-order functions. Like in Python, functions in Kotlin are first-class citizens - they can be assigned to variables and passed around as parameters. Consider this function:

fun safeDivide(numerator: Int, denominator: Int) =
    if (denominator == 0.0) 0.0 else numerator.toDouble() / denominator

It takes two Int parameters and returns a Double so its type is (Int,Int) -> Double. We can reference the function itself by prefixing its name with :: as shown below:

val f: (Int, Int) -> Double = ::safeDivide

A more concise representation is (type is inferred here):

val f = ::safeDivide

When you have a variable or parameter of function type (sometimes called a function reference), you can call it as if it were an ordinary function, and that will cause the referenced function to be called:

val quotient = f(3.14, 0.0)

Higher Order Functions using an Example

Suppose that you are building an Employee - Department system defined as:

class Employee(
        val name: String,
        var salary: Int,
        val department: Department
)

class Department(val name: String) {
}

You need to find the salaries of all employees. Traditional way to solve this is:

fun sumSalariesOfEmployees(employees: List): Int {
        var total= 0
        for (employee in employees){
        total += employee.salary
        }
        return total
}

Now solving using functional approach you can do it:

return employees.sumBy { employee -> employee.salary }

Next if you need to enhance it to get salaries by department, then you will need to filter by deparment:

fun sumSalariesOfEmployeesByDeparment(employees: List<Employee>, department: Department): Int {
    return employees.filter { employee -> employee.department == department }.sumBy { employee -> employee.salary }
}

Now if you need to enhance it to take take a list of departments, you will need to create another method,

fun sumSalariesOfEmployeesByDeparments(employees: List<Employee>, departments: List<Department>): Int {
    return employees.filter { employee -> employee.department in departments }.sumBy { employee -> employee.salary }
}

You see the problem in this approach. You need to define the filtering criteria each time for different requirements. This is where functional programming comes handy. Let's see how to create higher-order functions.

Create and invoke Higher-order function

To create higher order functions, syntax is as follows:

fun higerOrderFunction(innerFn: (param: Any) -> Any) {

val myParam: Any

innerFn(myParam)

}

The above function uses an inner function passed to it, that takes 'Any' type argument. The higher-order function can be invoked as follows:

higerOrderFunction( fun(param: Any): Anyreturn param } )

Above I am creating an anonymous function on the fly and passing to the higher-order function.

Now lets restructures the 'sumSalariesOfEmployees' function to make it a higher-order function. It accepts a predicate function that defines the criteria on which it should filter the employee and then calculate their sum.

fun sumEmployeeSalariesOn(employees: List<Employee>, predicate: (employee: Any) -> Boolean): Int {
    // 'it' is a Kotlin keyword that refers to a single param in a lambda function
    return employees.filter { predicate(it) }.sumBy { it.salary }
}

Now I can utilize this to compute sums based on different criteria without needing to create new functions:

//Sum of all Employees
return sumEmployeeSalariesOn(employees, { true })
//Sum of all Employees belonging to one department
return sumEmployeeSalariesOn(employees, fun(employee: Any): Boolean { return employee is Employee && department == employee.department } )
//Sum of all Employees belonging to a list of deparments
return sumEmployeeSalariesOn(employees, fun(employee: Any): Boolean { return employee is Employee && employee.department in departments})

Suppose I want to list of  Pairs as <Department, Int> for the total salaries for each departments. I can use the groupBy function to group by 'Department' and then from the resulting map(Key, Value) of the form {Department, List<Employee>} I can call the sumEmployeeSalariesOn to get the sum of salaries of the list of employees similar to the first use case above.

return employees.groupBy { it.department }.
map { (K, V) ->  Pair(K, sumEmployeeSalariesOn(V, { true })) }

Let us see a sample problem, that I have solved in traditional OOP (Object oriented programming) and see how we can solve it in FP (Functional programming).

Sample Problem

Suppose you need to design an application that navigates a rover across a grid.

The input to the application is:

  • Grid dimensions (Upper-right corner coordinates, lower left being implied as 0,0)
  • Position of the rover on the grid in the form (x, y, d) where x and y are positions on the x and y axis of the grid and d is the direction in which the rover is facing, being one of these values (N - 'North', S - 'South', E - 'East', W - 'West').
  • Route to navigate as character sequence with values being ('L' - turn left by 90º, 'R' - turn right by 90º, 'M' - move to the next grid position without changing direction).

Sample Input 

5 5

1 2 N

LMLMLMLMM

Expected Output

1 3 N

Design

You have a Rover, a Plateau (terrain) and a Main object that will call invoke and instruct the Rover.

The Main initializes the Plateau, and Rover objects.

Code - OOP

Below is my implementation of the Rover class in OOP. I iterate over the instructions and using 'when' (switch in java) handle each of the instructions.

Available on GitHub

Code - FP

Below is the functional version of the same code.Code available on Github

Explanation

You can see how concise this code looks compared to the OOP approach used to solve the same problem here

I have used fold to reduce the the sequence of instructions to a single final position, which is the destination expected.

Fold takes an accumulator and element of list/map, combines/reduces and returns this value as accumulator to next element and so on, till the last element is completed.

Fold is similar to Reduce except that it takes and initial value, whereas Reduce copies the first element to the accumulator. Also Fold can be used when the accumulator is of a different type than the list or map.

The crux of the problem is converting the sequence of instructions given as a string to a position on the grid.

So, given instructions 'MML' tells the rover to move two spaces in which ever direction it is facing and the turn left.

  • Split the string(ins) into a Character Sequence.
  • Pass the initial position of Rover to Fold
  • For each char instruction('L', 'R' or 'M'), turn left, right or move the rover respectively.

More on functional constructs available on Kotlin - here

This is just a small demonstration of how functional programming can make your code more concise and reduce the boiler plate code. I highly recommend trying out Kotlin to make your code more readable.

Oracle has added support to serverless computing on the cloud that enables developers to leverage programming languages that support Functional programming like Kotlin.

References

Join the discussion

Comments ( 3 )
  • Pratik Monday, April 8, 2019
    Java 8 is all about FP. I think all modern programming languages support FP.
  • GUILHERME MACIEL DE CARVALHO Tuesday, April 9, 2019
    The chain of functions is the power of FP.
    It is an very nice botton-up aproach.
  • Zack Macomber Wednesday, October 9, 2019
    I love the conciseness that FP affords but it's important to note cons of FP. FP performance doesn't compare (at least in the Java world) to imperative performance when it comes to processing big lists of data. This becomes especially evident when using nested loops. Also, FP can be really hard to debug inside it's chaining mechanisms of functions. Much easier to hold state in a variable and examine that and/or log it then to attempt to debug FP function chains.
Please enter your name.Please provide a valid email address.Please enter a comment.CAPTCHA challenge response provided was incorrect. Please try again.

Recent Content