What is Functional Programming? 

August 1, 2023

Functional programming means combining functions to construct a program. Functional programming is declarative, it describes what to solve in contrast to imperative programming that describes how to solve it. In this blog post we will explain what functional programming is and how to apply functional programming concepts with examples in Erlang and one in Haskell.

Functional programming has been around since the dawn of software development with Alonzo Church developing lambda (λ) calculus in the 1930s. Later in the 1950s, John McCarthy developed LISP (LISt Processor) as the first high-level functional programming language for IBM. Functional programming never took off and was long seen as coming from academia and being something used by mathematicians. However in the beginning of the new millennium, more and more companies and organizations turned to functional programming and functional programming concepts, like Google with its own developed map reduce.

 

Functional Programming simplified

If you don’t remember anything else from this blog post, remember this as what is functional programming:

  • Immutability = No data mutation, no side effects, variables are assigned values once.
  • Pure Functions = No implicit states, function returns the same result every time with a given set of arguments.

With this simplified version of what functional programming is, you realize you don’t need a functional programming language to do functional programming. However a functional programming language will help you (or enforce you).

 

Functional Programming vs other paradigms

Sometimes Functional programming is defined as the opposite of imperative programming, including object oriented programming or procedural programming. The most significant difference between FP and the other paradigms are avoiding side effects. Functions don’t keep state and they avoid I/O. Hence, most applications use different paradigms to solve and implement different parts of the applications and a software developer should be able to use all paradigms and know when to apply them.

 

Functional Programming defined

These 10 concepts below defines what functional programming is:

  • Immutability
  • Functions as first-class citizens and higher order functions
  • Pure functions
  • Recursion
  • Function composition
  • Immutable data structures
  • Strict and lazy evaluation
  • Pattern matching
  • Referential transparency
  • Concurrency and parallelism

 

Immutability

Immutability means that variables can only be assigned a value once. The immutability removes side effects and makes code more transparent.

-module(immutability_example).
-export([add_one/1]).

add_one(List) ->
   NewList = lists:map(fun(X) -> X + 1 end, List),
   NewList.

In this example, we have a module called immutability_example with a single exported function called add_one. This function takes a list of integers as input and returns a new list where each element is incremented by 1.

Inside the add_one function, we use the lists:map/2 function to apply a function to each element of the input list. The anonymous function fun(X) -> X + 1 end adds 1 to each element. However, notice that we are not modifying the original list; instead, we create a new list NewList containing the modified elements.

The key point here is that Erlang lists are immutable, meaning that they cannot be modified once created. So, rather than modifying the original list, we create a new list with the desired modifications.

Here’s an example of calling the add_one function:

immutability_example:add_one([1, 2, 3, 4, 5]).

Output:

[2,3,4,5,6]

In this case, we call the add_one function with the input list [1, 2, 3, 4, 5]. The function returns a new list [2, 3, 4, 5, 6], where each element is incremented by 1. The original list remains unchanged because of immutability.

 

Functions as first-class citizens and higher order functions

Functions are bound to names, passed as arguments, returned from functions just as any other data type. With higher order functions, functions can take functions as arguments and return functions.

Applications can be written in modules with functions that are combined to become the application.

-module(higher_order_example).
-export([apply_operation/2]).

apply_operation(List, Operation) ->
   lists:map(Operation, List).

double(X) ->
   X * 2.

triple(X) ->
   X * 3.

In this example, we have a module called higher_order_example with two exported functions: apply_operation/2, double/1, and triple/1.

The apply_operation/2 function takes a list (List) and a function (Operation) as input. It uses the lists:map/2 function to apply the Operation function to each element of the input list. The Operation function is a higher-order function because it is passed as an argument to apply_operation/2.

The double/1 function and triple/1 function are examples of functions that can be passed as arguments to apply_operation/2. They simply double and triple a given value, respectively.

Here’s an example of calling the apply_operation/2 function with the double/1 and triple/1 functions:

1> higher_order_example:apply_operation([1, 2, 3, 4, 5], fun higher_order_example:double/1).

Output:

[2,4,6,8,10]
2> higher_order_example:apply_operation([1, 2, 3, 4, 5], fun higher_order_example:triple/1).

Output:

[3,6,9,12,15]

In these examples, we call the apply_operation/2 function with the input list [1, 2, 3, 4, 5] and pass either the double/1 or triple/1 function as the Operation argument. The apply_operation/2 function applies the specified operation (double/1 or triple/1) to each element of the list, resulting in a new list with the corresponding operations applied to the elements.

 

Pure functions

Functions without any side effects (I/O is considered a side effect) combines functions with referential transparency (immutability). Same arguments to a pure function always returns the same result, the result is constant from the pure function. This means that pure functions are thread safe and can be run in parallel, multiple calls to a pure function can be run on parallel processors. Pure functions are also easier from a test perspective.

-module(pure_function_example).
-export([add/2]).

add(X, Y) ->
   X + Y.

In this example, we have a module called pure_function_example with a single exported function called add. The add function takes two arguments, X and Y, and returns their sum.

This function is considered pure because it satisfies the following criteria:

  1. It always produces the same output for the same input values. Given the same values of X and Y, the result of add(X, Y) will be consistent and predictable.
  2. It has no side effects. The add function does not modify any external state or variables outside of its scope.
  3. It does not rely on or modify any mutable data structures. In this case, the function simply performs a mathematical addition operation and returns the result.

Here’s an example of calling the add function:

1> pure_function_example:add(3, 5).

Output:

8

In this example, we call the add function with the arguments 3 and 5. The function returns their sum, which is 8. Since the function is pure, it will always return the correct result for the given inputs, without causing any side effects or relying on external mutable data.

It’s worth noting that this example is intentionally simple to demonstrate the purity of the function. In real-world scenarios, pure functions may perform more complex calculations or transformations while still adhering to the principles of purity.

 

Recursion

In functional programming there are no loop statements (for, while, do, etc), instead a function calls itself until it reaches its base case. A special optimized way of recursion is tail-recursion.

Recursion is enforced in functional programming languages, recursion in imperative languages is possible, however the application can overflow the stack. In functional programming languages the compiler, virtual machine and garbage collector takes care of the stack overflow problems and can also optimize the code to be tail-recursive.

-module(recursion_example).
-export([factorial/1]).

factorial(0) ->
   1;

factorial(N) when N > 0 ->
   N * factorial(N - 1).

In this example, we have a module called recursion_example with a single exported function called factorial. The factorial function calculates the factorial of a non-negative integer.

The factorial function uses recursion to compute the factorial. It has two clauses:

  1. The base case: If the input N is 0, the factorial is defined as 1. This acts as the termination condition for the recursive calls.
  2. The recursive case: If the input N is greater than 0, the factorial is calculated by multiplying N with the factorial of N-1. This recursive call allows us to break down the problem into smaller subproblems until we reach the base case.

Here’s an example of calling the factorial function:

1> recursion_example:factorial(5).

Output:

120

In this example, we call the factorial function with the argument 5. The function calculates the factorial of 5 using recursion, and the result is 120.

Some languages may have loop-like expressions called “for” or similar, but they are typically list comprehensions and work differently from “for” statements in most non-functional languages.

 

Function composition

Functional programming encourages function composition, which involves combining smaller functions to create more complex functions. The output of one function becomes the input of another, allowing for modular and reusable code.

With function composition, it is easy to define and reason about the flow of data as a pipe, as data moves from one function to the next.

-module(composition_example).
-export([compose/2]).

compose(F, G) ->
   fun (X) -> F(G(X)) end.

add_one(X) ->
   X + 1.

double(X) ->
   X * 2.

In this example, we have a module called composition_example with an exported function called compose. The compose function takes two functions, F and G, as arguments and returns a new function that represents the composition of F and G.

The compose function creates and returns an anonymous function that takes an argument X. Inside this anonymous function, it applies G(X) first and then applies F to the result of G(X). This composition of functions allows the output of G to be passed as input to F.

Additionally, we define two functions, add_one and double, which are used as examples of functions that can be composed.

Here’s an example of calling the compose function:


1> ComposedFn = composition_example:compose(fun composition_example:add_one/1, fun composition_example:double/1).
2> Result = ComposedFn(5).

Output:

Result = 12

In this example, we call the compose function with add_one and double as arguments. It returns a composed function that adds one to the double of a given value.

We then assign the composed function to the variable ComposedFn. Finally, we apply the composed function to the value 5, resulting in 12. The composition of add_one and double is achieved by passing the output of double as input to add_one.

 

Immutable data structures

Functional programming promotes the use of immutable data structures, such as lists, sets, and maps. These data structures cannot be modified once created, ensuring data consistency and enabling safe concurrent programming.

-module(immutable_data_example).
-export([add_value/2]).

add_value(Value, List) ->
   [Value | List].

In this example, we have a module called immutable_data_example with a single exported function called add_value. The add_value function takes a Value and a List as input and returns a new list where the Value is added to the front of the original List, an operation sometimes known as “cons” (from construct).

Erlang lists are immutable, which means they cannot be modified once created. In the add_value function, instead of modifying the original List, we create a new list by concatenating [Value] with the existing List.

Here’s an example of calling the add_value function:

1> immutable_data_example:add_value(3, [1, 2, 4, 5]).

Output:

[3,1,2,4,5]

In this example, we call the add_value function with the value 3 and the list [1, 2, 4, 5]. The function returns a new list [3, 1, 2, 4, 5], where the value 3 is added to the front of the original list.

 

Strict and lazy evaluation

In functional programming, strict evaluation and lazy evaluation are two different evaluation strategies for evaluating expressions.

 

Strict Evaluation

Strict evaluation is the default evaluation strategy used in most programming languages. In strict evaluation, expressions are evaluated eagerly, meaning that the arguments to a function are evaluated before the function is applied. This means that all the necessary computations are performed immediately, and the results are stored in memory. Strict evaluation ensures that all arguments are fully evaluated and any side effects of the evaluations are executed before a function is applied.

Example in Erlang:

add(X, Y) ->
   X + Y.

calculate() ->
   Result = add(3, 4),
   Result * 2.

In the above example, when calculate/0 function is called, it first evaluates the expression add(3, 4), which results in 7. Then, it multiplies Result by 2 and returns 14. The arguments 3 and 4 are evaluated immediately, and their values are used in the computation.

 

Lazy Evaluation

Lazy evaluation, on the other hand, is an evaluation strategy where expressions are not evaluated until their values are actually needed. Lazy evaluation defers the computation until it is explicitly demanded. This can be useful when dealing with potentially infinite data structures or when evaluating expensive computations that may not be needed in certain cases. Lazy evaluation can help improve performance by avoiding unnecessary computations.

Example in Haskell:

numbersFrom n = n : numbersFrom (n + 1)

calculate =
   let numbers = numbersFrom(1)
      result = take 5 numbers
   in sum result

In this Haskell example, the numbersFrom function generates an infinite list of consecutive numbers starting from the given input. However, in the calculate function, we only need the first five numbers. With lazy evaluation, the computation of the infinite list is deferred until it is necessary. The take function lazily takes the first five numbers from the infinite list, and then sum function calculates their sum. The infinite list is not fully computed; only the required portion is evaluated.

Lazy evaluation allows for more efficient and concise code in certain scenarios, as computations are performed on an as-needed basis.

Both strict evaluation and lazy evaluation have their advantages and trade-offs, and the choice of evaluation strategy depends on the specific requirements of the problem at hand. Functional programming languages like Haskell often provide support for lazy evaluation, while other languages typically follow strict evaluation by default.

 

Pattern Matching

Pattern matching is a powerful technique used in functional programming languages to destructure and match data against patterns. It enables concise and expressive code by extracting values or executing specific branches based on the structure of the input data.

-module(pattern_matching_list_example).
-export([process_list/1]).

process_list([]) ->
   io:format("Empty list. Nothing to process.~n");

process_list([First | Rest]) ->
   io:format("Processing element: ~p~n", [First]),
   process_list(Rest).

In this example, we have a module called pattern_matching_list_example with an exported function called process_list. The process_list function takes a list as an argument and processes each element in the list.

The function uses pattern matching to define two different cases:

  1. If the input list is empty ([]), it matches the empty list pattern and prints a message stating that the list is empty and there is nothing to process.
  2. If the input list is not empty and contains at least one element ([First | Rest]), it matches the head of the list (First) and the remaining tail of the list (Rest). It then prints a message indicating that it is processing the current element (First) and recursively calls process_list with the remaining tail of the list (Rest).

Here’s an example of calling the process_list function:

1> pattern_matching_list_example:process_list([1, 2, 3, 4, 5]).

Output:

Processing element: 1
Processing element: 2
Processing element: 3
Processing element: 4
Processing element: 5
Empty list. Nothing to process.

In this example, we call the process_list function with the list [1, 2, 3, 4, 5]. The function pattern matches the list and processes each element by printing a message for each element. It iterates through the list recursively until the list is empty.

 

Referential Transparency

Functional programming encourages referential transparency, which means that an expression can be replaced with its corresponding value without affecting the program’s behavior. This property makes code more predictable and easier to reason about.

square(X) ->
   X * X.

calculate() ->
   Result1 = square(5),
   Result2 = square(5),
   Result1 + Result2.

In the code snippet above, we have a square/1 function that takes a number as input and returns the square of that number. The calculate/0 function demonstrates referential transparency by using the square/1 function.

Within the calculate/0 function, we call the square/1 function twice with the same input value of 5 and assign the results to Result1 and Result2, respectively. Since the square/1 function always produces the same output for the same input, both Result1 and Result2 will be equal to 25.

Finally, we add Result1 and Result2 together, which will always result in 50.

The key point here is that the square/1 function is referentially transparent because it consistently returns the same result for the same input, and it doesn’t have any side effects. This property allows us to replace the function call with its result without changing the behavior of the program, which is a fundamental characteristic of referential transparency.

 

Concurrency and Parallelism

Functional programming provides strong support for writing concurrent and parallel programs. By avoiding mutable state and side effects, functional code can be easily executed in parallel, making it suitable for modern multi-core and distributed systems.

-module(concurrency_parallelism_example).
-export([start/0]).

start() ->
   Parent = self(),
   Pid1 = spawn(fun() -> Parent ! {result1, count_up(1, 5)} end),
   Pid2 = spawn(fun() -> Parent ! {result2, count_down(10, 6)} end),
   Pid3 = spawn(fun() -> Parent ! {result3, increment(5)} end),
   Pid4 = spawn(fun() -> Parent ! {result4, square(7)} end),
   Pid5 = spawn(fun() -> Parent ! {result5, multiply(3, 4)} end),

   receive
      {result1, R1} -> io:format("Count up result: ~p~n", [R1])
   end,
   receive
      {result2, R2} -> io:format("Count down result: ~p~n", [R2])
   end,
   receive
      {result3, R3} -> io:format("Increment result: ~p~n", [R3])
   end,
   receive
      {result4, R4} -> io:format("Square result: ~p~n", [R4])
   end,
   receive
      {result5, R5} -> io:format("Multiplication result: ~p~n", [R5])
   end.

count_up(N, Limit) ->
   io:format("Counting up: ~p~n", [N]),
   if N < Limit ->
  	count_up(N + 1, Limit);
   true ->
  	N
   end.

count_down(N, Limit) ->
   io:format("Counting down: ~p~n", [N]),
   if N > Limit ->
      count_down(N - 1, Limit);
   true ->
      N
   end.

increment(N) ->
   Result = N + 1,
   Result.

square(N) ->
   Result = N * N,
   Result.

multiply(X, Y) ->
   Result = X * Y,
   Result.

In this example, we have a module called concurrency_parallelism_example with an exported function called start/0. The start function demonstrates both concurrency and parallelism.

Inside the start function, we spawn multiple processes using the spawn function. Each process executes a specific computation asynchronously:

  • Pid1 counts up from 1 to 5 using the count_up function.
  • Pid2 counts down from 10 to 6 using the count_down function.
  • Pid3 increments the value 5 by 1 using the increment function.
  • Pid4 calculates the square of 7 using the square function.
  • Pid5 multiplies the numbers 3 and 4 using the multiply function.

Inside the spawned processes, we use the ! operator to send the results back to the process ID contained in the Parent variable, which is the process that is running the start/0 function.

After spawning the processes, we use receive blocks with pattern matches to receive and print the results of each process.

To run the example, you can call the concurrency_parallelism_example:start() function.

When executing the example, you will see the output showing the concurrent execution of the processes and the results they produce.

 

Summary

Functional programming is a programming paradigm that focuses on combining functions to construct programs. It is declarative, describing what to solve rather than how to solve it. Functional programming has been around since the 1930s and gained more popularity in recent years.

Functional programming emphasizes immutability and pure functions. Immutability means variables can only be assigned a value once, eliminating data mutation and side effects. Pure functions have no implicit states and always return the same result given the same arguments.

Overall, functional programming offers benefits such as code transparency, testability, thread safety, and modularity. While functional programming languages facilitate functional programming, the concepts can be applied in any language.

 

Additional resources

Check out the Ada Beat Functional Programming blog for more topics, including functional programming principles, summaries of MeetUps, language specific articles, and much more. Whether you’re interested in functional programming theory or practical application, we have something for everyone.