@Version : 4.5.0
@Build : 94d077c24
By using this site, you acknowledge that you have read and understand the Cookie Policy, Privacy Policy, and the Terms. Close

Learn Some Functional Programming

Posted Saturday, August 29th, 2020

Function ProgrammingElixirErLangLispHaskell
Learn Some Functional Programming

Acronyms Used

  • FP - Functional Programming.
  • DB - Database.
  • TCO - Tail Call Optimization.
  • HOF - High Order Function.
  • OOP - Object Oriented Programming

Everything I cover here is not as in-depth. This is a lot of content to put in one place but in the end you will see the relationship with each other and how all this makes you a better functional programmer for the better good. Each topic will potentially be a stand-alone article on its own. The goal of this is to introduce the fundamentals focusing on the meanings, usage, and examples. I have also attached some links for further reading.

What is Functional Programming?

Functional programming is a declarative paradigm in which computation follows a compositional approach where functions are chained each returning a value instead of a sequence of imperative statements that change the state of the program. This idea is mainly derived from lambda calculus.

Functional programming has been around for a long time and is a lot older than the famous Object-Oriented Programming. It was dormant for some time but has made a great comeback to new challenges facing the computer science ecosystem. I believe functional programming has key things that need understanding for one to be able to find their way around things. That is what this is about.

I will use Elixir for most of my examples unless I need to show the difference between features in different languages or to just better understand things and how they work in other languages.

Since Functional programming promotes declarative approaches over imperative approaches, it is very useful to understand the difference between the two.

Declarative vs Imperative.

Imagine we work together and I ask you this question: How do I go from the office to your house?

An imperative answer to this would be:

  • Walk to the bus station X
  • Take a bus that uses High Way 6
  • Alight at the second stop after the main interchange.
  • Take the road to the left (Globe Avenue) for about 300 meters
  • My house is number 255.

A declarative would be:

  • My house is Number 255 on Globe Avenue off High Way 6 after the Main Interchange.

The main thing to note here is that the declarative way assumes most things under the hood. For example, in this case, the declarative answer assumes:

  • I know how to move e.g by Bus, Taxi, Driving or Walking
  • I have some kind of GPS to tell me where the Main Interchange on High Way 6 is and where Globe Avenue is. This means regardless of how I get there, I just need to be at that address, while in the imperative approach, I have to follow the steps that are given for me to be at the address.

Functions and declarative approaches are close because functions definitions include just input and output. As long as given X the function produces Y, that is the expectation. If you need to read more about Imperative and Declarative Paradigms check out this link. I believe this makes you see why being declarative is an important part of functional programming.

Why Functional Programming?

In my experience so far, here is a list of some of the good parts of functional programming that I want to remember always.

  • Easy Concurrency and Parallelism.
  • Powerful abstraction.
  • Simple and faster to write.
  • Easy to test.
  • Easy to debug.
  • Easy to reason about.

But there is no silver bullet. FP also has some problems that I have addressed at the end of this post. I put these at the bottom because in most cases they are easy to mitigate and are often outweighed by the good parts.

Playground

I will use sample codes mostly in Elixir, Haskell, and JavaScript. I am using a local shell for my execution because I have all these installed. If you do not want or unable to install, here are online IDEs for you to get going without installing anything.

Programming problem:

In this post, I will use some common computation problems to learn through how different ways can be used to compute the required values in Functional Programming.

Imperative Solutions in JavaScript

Given const list = [1, 2, 3, 4, 5], we will do the following operations in different languages to compute the value in each case using functions that exist in functional programming languages. Note that the solutions are the imperative solutions that will be replaced by declarative ways in my examples. I may use other examples not listed here but I will try to keep them simple.

  • Find the sum of these numbers.
    let sum = 0;
    for (let num of list){ 
      sum += num;
    }
    console.log(sum); // 15
  • Create a new list of the squares of each number.
    let squares = [];
    for (let num of list){ 
      squares.push(num * num);
    }
    console.log(squares); // [ 1, 4, 9, 16, 25 ]
  • Create a new list of only add numbers.
    let addsNumbers = [];
    for (let num of list){ 
      if(num % 2 !=0) addsNumbers.push(num);
    }
    console.log(squares); // [ 1, 3, 5 ]
  • Find the sum of the squares of these numbers.
    let sum0fSquares = 0;
    for (let num of list){ 
      sum0fSquares += num * num;
    }
    console.log(sum0fSquares); // 55
  • Find the cumulative product of these numbers starting with first number.
    let sum0fProductsL = 0;
    let productsL = 1;
    for (let num of list){ 
      productsL *= num;
      sum0fProductsL += productsL;
    }
    console.log(sum0fProductsL); // 153
  • Find the cumulative product of these numbers starting with the last number.
    let sum0fProductsR = 0;
    let productsR = 1;
    for (let i = list.length-1; i>=0; i--){
      const num = list[i];
      productsR *= num;
      sum0fProductsR += productsR;
    }
    console.log(sum0fProductsR); // 325

Functional Programming Languages

Functional languages are those that promote the functional way of doing things and can be categorized into two types. Pure and Impure functional languages. While in purely functional languages, functions return the same output for the same set of inputs and do not change anything outside its context (have no side effects), the opposite is true in impure functions.

Pure Functional Languages

In pure functional languages, functions have no side effects, meaning they don't modify the context outside of them. Pure functional languages are fully declarative. Here are some popular purely functional programming languages. pure functional programming languages

Impure Functional Languages

In impure functional languages, there is support for imperative execution and functions are not pure - have side effects like changing the state outside of them. Most popular languages fall in this category. Some impure functional languages include impure functional prgramming languages

It is important to note that a FP Language falling in the impure category does not mean you can not write pure functions in them.

Pure Functions

Remember I mentioned that there are two types of functional languages: Pure and Impure. Pure functions are functions that return the same value always for the same set of inputs. That means they do not depend on any external scope or change it in their execution process.

A good example would be some function that adds two numbers and updates the database. The addition part is pure because the result will always be the same for a set of inputs. But the database update part is not pure due to these side effects.

  • DB may be offline
  • The record to update may not exist.

What is the advantage of having purity in functions?

  • Easy memoization such that once a function is called with the result know, a call with the same set of inputs doe not have to reach the function itself because there is a guarantee that the result will be the same.
  • Tend to be less error-prone. Should make sense :-).
  • Are more clear as there are no "hidden things"
  • Easy to debug.

An important point to take home is the advantages of pure functions and that there are pure and impure functional languages but the bottom line is that you can make pure functions in both of these.

Consider the function below that calculates the area of a circle depending on PI defined above its scope. This function is not pure because when the value of pi changes, it will return a different value for the same input.

let pi = 3.142;

function areaOfCircle(r) {
  return pi * r * r;
}
areaOfCircle(7) // 153.958
pi = 3.14
areaOfCircle(7) // 1153.86

Having pi defined in the function definition can make this a pure function.

Benefits of pure functions

Pure functions have no side effects and thus bring many advantages.

  • Easy to understand.
  • Easy to test
  • Easy to compose and combine
  • Easy to execute concurrently.
  • Easy memoization

Using pure functions have many benefits alongside the listed ones. Here is an article that explains these benefits.

So what happens when you can't be pure?

Ideally in this case you would put most of the side effects in the edges of a system (that is the part closest to the side effect generator) and separate things that can exist inside pure functions on their own.

For example in the case of adding two numbers and updating the DB, you have two functions that one adds the numbers while the other updates the DB. This makes debugging add two numbers easy to test and debug especially if its complex.

Functions as First-Class Citizens

In any language where functions can be assigned to variables and passed as arguments to other functions, they are said to be first-class citizens. This is a very useful and powerful feature found in simple and complex computations. Below is a series of elixir functions being created, assigned as variables, and added as arguments in other function calls.

iex(10)> area = fn length, width -> length * width end
iex(11)> perimeter = fn length, width -> 2 *(length + width) end
iex(12)> sum_area_perimeter = fn l, w, a, p -> a.(l, w) + p.(l, w) end
iex(13)> sum_area_perimeter.(5, 3, area, perimeter)
31
iex(14)>

In the above example, the following properties are visible that make functions as first-class citizens in Elixir.

  • area is a Variable that refers to a Function that takes two integer inputs.
  • perimeter is a Variable that refers to a Function that takes two integer arguments.
  • sum_area_perimeter is a variable that references a function that takes two integer arguments and two function arguments.

How is this useful?

Fact: Being able to assign functions as variables and toss them around as arguments are just so much fun and form a big part of making the abstractions in High Order Functions work. You will see this when you reach the HOF section.

Lambdas - "Anonymous Functions"

Lambdas are also commonly known as Anonymous functions or Closures in JavaScript or Blocks in Smalltalk. They derive from Lambda Calculus. So what exactly are they and what makes them so important?

Lambdas are unnamed functions that are passed as arguments to other functions while keeping access to the variables in global scope and their private scope. This is important because it helps us write small easy throw away functions with closures. Consider the examples below.

In the example below nameWithnitials is a function that takes an initial like Prof and returns a lambda that takes a name (String) and prepends the initial to it. Notice that after calling nameWithnitials('Mr') the result is a lambda that can be called with a name and has access to the value of initial.

const nameWithnitials = (initial) => (name) => {
  return `${initial} ${name}`;
};
const addInitials = nameWithnitials('Mr');
addInitials('Danstan'); // Mr Danstan

Here is another example is in Elixir where a lambda has access to the scope/environment just before it. add_initials is a function that is created by NameModule.add_initials("Mr") and has access to the environment which has initial = Mr. You can see these are very similar to the JS version.

iex(5)> defmodule NameModule do
...(5)>    def add_initials(initial) do
...(5)>       fn name -> "#{initial} #{name}" end
...(5)>    end
...(5)> end
iex(6)> add_initials = NameModule.add_initials("Mr")
iex(7)> add_name.("Danstan")
"Mr Danstan"
iex(8)>

The concept of anonymous functions is common and similar in several languages. Check out this Stack Overflow Answer on lambdas in different languages. Particularly in functional programming, they are used in may small computation flows covered in the Map, Reduce, Filter, and Fold sections because of their simplicity and access to the previous environment.

Immutability

Immutability is the state of being unable to change. In functional programming, data structures are not mutable. This means once you assign a memory location you can not change the value until it is garbage collected by the runtime. Instead, you create a "copy" of it.

In Elixir, you can create a variable and rebind it to another reference. For example:

iex(1)> x = 0
0
iex(2)> x = "Hello World!"
"Hello World!"
iex(3)> x = :atom_here
:atom_here
iex(4)> x = [1, 2, 3]
[1, 2, 3]

Now, this is not immutability, it is just rebinding the memory location that x references. Consider a case where the last value of x, a list of numbers and you want to add 4 to the list. In JavaScript,

var x = [1, 2, 3];
x.push(4);
console.log(x); // [ 1, 2, 3, 4 ]

This is mutability. In JavaScript data structures are mutable. In strongly functional languages that have immutable data structures, you can not mutate like that. Instead, you would create a new list with some new item.

Here is a perfect example. You have a lits of users, objects with properties name and age. You create a const from the first element then you change it. The copy in the list changes too. See below.

const users =  [{ name: 'Danstan', age: 29 } ]
console.log(users) // [ { name: 'Danstan', age: 29 } ]
const user = users[0];
console.log(user) // { name: 'Danstan', age: 29 }
user.age = 39
console.log(user) // { name: 'Danstan', age: 39 }
console.log(users) // [ { name: 'Danstan', age: 39 } ]

This can lead to serious bugs when unintended. For example, if you called some function with user and changed its value downstream in a complex nested relationship in your code flow, you have a problem. Immutability comes to the rescue.

How immutability works under the hood.

In immutable data structures, once you store something, you can only make a copy of if that has the original data with the changes that happened. For example, a list with 10 elements that are transformed into a new list with 12 elements after inserting two items will just reference the first list and the two new items.

I cant better explain this because there is a lot of content already on this that is to well transferable here. See these links for a good understanding of how immutability works under the hood to optimize memory usage while keeping copies.

Why immutability is important.

  • Easy to achieve concurrency
  • Easy catching.
  • Easy to implement State Machines.
  • Less prone to bugs.
  • Leads to consistent code.
  • Easy to test.

Recursion and Tail Call Optimizations

Recursion is where a function calls itself several times. For example:

iex(6)> defmodule LogTime do
...(6)>     def log() do
...(6)>         :timer.sleep(1000)
...(6)>         IO.puts(DateTime.utc_now())
...(6)>         log()
...(6)>     end
...(6)> end
iex(7)> LogTime.log()
2020-08-21 10:01:40.045702Z
2020-08-21 10:01:41.043736Z

Why is recursion important in FP?

As we have seen, functional languages have immutable data structures, recursion is usually the go-to for repeated tasks that are done using loops in other languages.

Imagine the JavaScript function below that does iterate through a list and check it value against an object of squares and update its value.

const squares = {};
function squareList(list) {
  for (const item of list) {
    squares[item] = item * item;
  }
  return squares;
}
console.log(squareList([1, 3, 6])); // { '1': 1, '3': 9, '6': 36 }
console.log(squareList([2, 4, 8])); // { '1': 1, '2': 4, '3': 9, '4': 16, '6': 36, '8': 64 }

Because of immutability, this would not work in a language that has immutable data structures. Such problems are solved by recursion. We can not change the same squares object or map as its immutable. Here is a recursive solution for it in Elixir where each time, change the map and call with it.

iex(3)> defmodule MapValueToSquare do
...(3)>     def square([], squares), do: squares
...(3)>     def square(nums, squares) do
...(3)>         {num, rest} = List.pop_at(nums, 0)
...(3)>         squares = Map.put(squares, num, num * num)
...(3)>
...(3)>         square(rest, squares)
...(3)>     end
...(3)> end
iex(4)> result = MapValueToSquare.square([1, 3, 6], %{})
%{1 => 1, 3 => 9, 6 => 36}
iex(5)> MapValueToSquare.square([1, 3, 6], %{})
%{1 => 1, 3 => 9, 6 => 36}
iex(6)> MapValueToSquare.square([2, 4, 8], result)
%{1 => 1, 2 => 4, 3 => 9, 4 => 16, 6 => 36, 8 => 64}
iex(7)>

Notice that in the Elixir example, it forces you to be explicit about using the same map to store the values of the two different operations. This is often a bonus of immutability as the JavaScript case can lead to undesirable behavior.

Tail Call Optimization (TCO)

Recursion can often lead to memory problems caused by adding a stack frame for each call to the function eventually leading to a stack overflow. Some FP languages like Elixir and JavaScript from ES6 solve this by having Tail Call Optimization at runtime. In languages where TCO is not supported like Java and Python, it is generally not a good idea to use recursion for memory-intensive tasks or huge loops.

I am still trying to wrap my head around how TCO really works. If you need to know here are a few links.:

In Elixir it is possible for Body recursive to be faster than Tail Recursive function. I have no idea how. See here.

The key point here is just that you need to be aware of this about the language you are using and how you can optimize recursion at runtime.

High Order Functions (HOF)

From Wikipedia - High Order Functions are a mathematical and computer science concept that refers to functions that have at least one of the characteristics.

  • Take one or more functions as input.
  • Return a function as a result.

High Order Functions are usually some optimized abstraction to some algorithms that are common.

Here is an example in Elixir. add is a lambda. add_then_double a HOF because it takes sum a function and calls it to sum numbers n1 and n1.

iex(16)> add = fn n1, n2 -> n1 + n2 end
iex(17)> add_then_double = fn n1, n2, sum -> sum.(n1, n2) * 2 end
iex(18)> add_then_double.(5, 6, add)
22
iex(19)

In this case add_then_double abstracts away double operation while taking a add function. This means you have control of what add does. This happens when add is always needed before double but add may be different for each caller of add_then_double.

Please allow me to write my very first Haskell Code. Consider the following very simple Haskell functions. I pulled these from Learn You Haskell - High Order Functions. Actually the first Haskell I have written :-). In this examples sumEarnings is a high order function that returns a lambda that intern calculates the sum of three earnings while sumConvertToCurrency is a high order function that takes a function f as forth argument and calls it.

Prelude> sumEarnings = (\sale loans ads -> sale + loans + ads)
Prelude> sumConvertToCurrency sale loans ads f  = f sale loans ads * 107.25
Prelude> sumConvertToCurrency 10 20 20 sumEarnings
5362.5
Prelude>

In functional programming it is very common to use HOF as in a lot of cases, you will want to pass functions as arguments or return them as results of executions.

There are many High Order Functions that are available in most functional languages which help developers to have an easy time. The most common among which I will cover below are:

Filter

Filter is an operation in FP that takes an enumerable and a function that returns a Boolean and returns a new version of that enumerable where the input function returned True for the current element. A filter is also a high order function that abstracts this operation by going through the entire enumerable while applying the filter function.

In Elixir, here is an operation to remove add numbers from a list of numbers

iex(3)> Enum.filter([1, 2, 3, 4], fn num -> rem(num, 2) == 0 end)
[2, 4]
iex(4)>

In Haskell, here is an operation to remove even numbers from a list of numbers. See how similar they are :-)

Prelude> filter (\num -> (rem num 2) /= 0) [1, 2, 3, 4, 5]
[1,3,5]
Prelude>

In an object oriented language that supports functional paradigm, it would be something like this. JavaScript

[1, 2, 3, 4, 5].filter(num => num % 2 == 0) // [ 2, 4 ]
// OR
const [1, 2, 3, 4, 5]
list.filter(num => num % 2 == 0) // [ 2, 4 ]

Map

In functional programming, map is an operation that is performed on an enumerable by applying a function on each element of the enumerable while keeping the order. A map is usually a transformation operation used to convert the elements to some other format resulting in a new list.

Consider a list of numbers that need to be transformed into a list of the squares of the numbers. A map operation on the list that takes a lambda which squares the number is common.

In Elixir

iex(5)> nums = [1,2, 3, 4, 5]
iex(6)> Enum.map(nums, fn num -> num * num end)
[1,4, 9, 16, 25]
iex(7)>

In Haskell

Prelude> nums = [1,2, 3, 4, 5]
Prelude> map (\num -> num * num) nums
[1,4,9,16,25]
Prelude>

Most functional languages will provide the map HOF that is optimized with an efficient algorithm under the hood. It is possible to do this using recursion or a loop. Here is an example in Elixir

iex(9)> defmodule MyEnum do
...(9)>     def map(enum, map_fun), do: recursive_map(enum, [], map_fun)
...(9)>
...(9)>     defp recursive_map([], mapped, _), do: mapped
...(9)>     defp recursive_map(left, mapped, map_fun) do
...(9)>         [first | rest] = left
...(9)>         recursive_map(rest, mapped ++ [map_fun.(first)], map_fun)
...(9)>     end
...(9)> end
iex(10)> MyEnum.map([1,2, 3, 4, 5], fn num -> num * num end)
[1,4, 9, 16, 25]
iex(11)>

Note that this is limited as it only works on some types. For example, it only works on List type of enumerable in elixir and not other types like streams. Therefore whenever this function is provided by the runtime, it is better to use it instead of your own unless there is a significant performance boost with a custom solution.

Reduce

Reduce is another important concept in FP. It means exactly like its name. Reduce function takes an enumerable, an accumulator, and reducer and returns the accumulated value from the reduce operation.

Reduce function is useful for doing aggregation like summing integer enumerable members into one value.

In Elixir

iex(12)> Enum.reduce([1, 2, 3, 4, 5], 0, fn num, acc -> acc + num  end)
15
iex(13)>

In JavaScript

const list = [1, 2, 3, 4, 5];

list.reduce((accumulator, num) => accumulator + num, 0); // 15

Reduce is used in very complex computations especially data pipelines. Imagine having a lits of users and having to count and group by age bracket.

defmodule UserGroup do
  def by_age(users) do
    users
    |> Enum.reduce(%{}, &append_by_ge/2)
  end

  defp append_by_ge(user, acc) do
    cond do
      user.age < 10 -> append(acc, :child)
      user.age < 20 -> append(acc, :teen)
      user.age < 40 -> append(acc, :middle)
      true -> append(acc, :old)
    end
  end

  defp append(acc, aggregate) do
    value = acc |> Map.get(aggregate) || 0
    acc |> Map.put(aggregate, value + 1)
  end
end
iex(30)> users = [%{age: 9}, %{age: 40}, %{age: 30}, %{age: 2}]
iex(31)> UserGroup.by_age(users)
%{child: 2, middle: 1, old: 1}
iex(32)>

Reduce is a common function used to do a lot of other computations that range from counting, data cleaning, aggregation, analysis, etc. It is a very important concept to grasp.

Map-Reduce

Map-Reduce as the name suggests combines the map and the reduce functions in one operation thereby returning a transformed list and an accumulated value. The syntax also just combines that of the two individual map and reduce function. Below is a map-reduce that sums list members and squares them in one operation.

iex(32)> Enum.map_reduce([1, 2, 3], 0, fn x, acc -> {x * 2, x + acc} end)
{[2, 4, 6], 6}
iex(34)>

This is usually efficient because it is very common to have a map operation alongside reduce so doing them in one operation reduces the Big-0.

Note that this is not the Hadoop Big Data Map-Reduce although there are some similarities in the operations. The Hadoop MapReduce is much more involving than our plain map and reduce function I have just described.

Fold

In FP, Fold is very similar to the reduce operation because it takes an enumerable and applies a function to each element while keeping an accumulated value from the operation. The only difference is that Fold can do this in reverse or natural order. Thus most languages tend to have foldl and foldr

Our example here we need to find the sum of the squares of [2, 3, 4, 5]. Our operation mathematically should be like this: 0 + (2*

Fold Left

Foldl will apply a function to an enumerable in the natural order (left to right) hence the name fold left while keeping an accumulator. Whenever I can use this function, I tend to replace it with reduce.

In Elixir, foldl is available in the List module. I assume this means it will work on only lists instead of working on other enumerable(s).

iex(14)> List.foldl([1, 2, 3, 4, 5], 0, fn num, acc -> acc + IO.inspect(num)  end)
1
2
3
4
5
15
iex(15)>

Fold Right

Fold right is the same as Fold left only that it operates on the list in reverse order.

iex(13)> List.foldr([1, 2, 3, 4, 5], 0, fn num, acc -> acc + IO.inspect(num)  end)
5
4
3
2
1
15
iex(14)>

Function Composition

This is my favorite part of functional programming. As you may see now, functional languages promote everything is a function way of doing things, meaning small computations will exist as functions that do less alone but when combined in chains or groups, they do a lot more complex stuff. Function composition is what gives ways to combine small functions.

Function composition is the art of combining small functions in chains such that the result from the previous function is the input to the next. Function composition is best explained by example.

In Haskell

Given the list [1, 2, 3, 4, 5, 6, 7, 8, 9], Find the sum of the squares of the odd numbers in the list. This can be done in the following sequence. Notice that the . operator is called a Function composition operator.

  • filter the numbers to remove the even ones.
  • map the result and square each.
  • sum the result.
Prelude> remove_even = (\ nums -> filter (\num -> (rem num 2) /= 0) nums)
Prelude> square = (\ nums -> map (\num -> num * num) nums)
Prelude> (sum . square . remove_even) [1, 2, 3, 4, 5, 6, 7, 8, 9]
165
Prelude>

In the example above, here is the same thing without composition and it leads to unnecessary repetition.

Prelude> remove_even = (\ nums -> filter (\num -> (rem num 2) /= 0) nums)
Prelude> square = (\ nums -> map (\num -> num * num) nums)
Prelude> result1 = remove_even [1, 2, 3, 4, 5, 6, 7, 8, 9]
[1,3,5,7,9]
Prelude> result2 = square result1
[1,9,25,49,81]
Prelude> sum result2
165
Prelude>

In Elixir

Doing the same thing above in Elixir is just the same only the syntax is changing. In Elixir, the composition operator is |> called the pipe operator.

iex(12)> square = fn nums -> Enum.map(nums, &(&1 * &1)) end
iex(13)> remove_even = fn nums -> Enum.filter(nums, &(rem(&1, 2) != 0)) end
iex(14)> nums |> remove_even.() |> square.() |> Enum.sum()
165
iex(15)>

This pattern useful and very common. You can do this also in languages like C# and JavaScript with similarities to the ones above. For example, to do this very thing in JavaScript - though this is not like chains. Here we have a new Array class instance in each step which has the method called on it.

const list = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ];
list
  .filter(num => num % 2 !== 0)
  .map(num => num * num)
  .reduce((acc, num) => acc + num, 0 ); // 165

Why is function composition useful?

  • Easy to read
  • Removes repetition.
  • Easy to reason about.
  • Promotes consistency.
  • Can represent business models.
  • Promotes re-usability.
  • Can combine small tasks or flows into a huge flow that is straight forward.

Lazy Evaluation

Lazy Evaluation aka call-by-need is an evaluation strategy which delays the evaluation of an expression until its value is needed and which also avoids repeated evaluations. From Wikipedia

Try this in an Elixir shell. For me, I waited for 10 minutes on a computer with 4 core i7 CPU and 16GB of Ram and eventually canceled it.

iex(6)> Enum.filter(1..1000_000_000, &(rem(&1, 3) == 0 || rem(&1, 5) == 0)) |> Enum.take(5)

Then try this. This for me was instant.

iex(1)> Stream.filter(1..1000_000_000, &(rem(&1, 3) == 0 || rem(&1, 5) == 0)) |> Enum.take(5)
[3, 5, 6, 9, 10]
iex(2)>

So how does this work such that one takes forever and the other is instant. Lazy Evaluation :-). In the example above, Enum.filter has to load the entire list in memory - Strict evaluation while Stream.filter will not load the whole list at once thus may finish without evaluating some part of the list.

To understand this concept, we have to understand what infinite data structures are.

Infinite Data Structures

In Haskell [1..] is an infinite enumerable of the non-negative numbers. You can see this by interacting with it.

Prelude> [1..]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71, -- Runs forever

The whole list of all positive numbers can not fit in memory because its infinite but that does not mean we can not work with it. Infinite data structures allow us to represent data such that their values are only evaluated when needed (Lazy Evaluation). See here how we can work with infinite lists.

The code below runs forever but does square every number in the list infinitely.

Prelude> map (^2) [1..]
[1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961,1024,1089,1156,1225,1296,1369,1444,1521,1600,1681,1764,1849,1936,2025,2116,2209,2304,2401 -- Runs forever
Prelude> take 10 (map (^2) [1..])
[1,4,9,16,25,36,49,64,81,100]
Prelude>

This is just the tip of the iceberg. I recommend you look at the links below to better understand this

  • Watch this video to see how lazy evaluation makes working with infinite lists achievable in Haskell
  • See here how some JS libraries add lazy evaluation

Problems with Functional Programming

In the tech space, there are no silver bullets and neither are their perfect solutions. There are always some trade-offs or shortcomings. Functional programming is no exception. For example:

  • Things always have side effects - Programs always interact with the real world through IO. There are always side effects.
  • Problems with recursion - As we have seen recursion can have some memory issues in some functional; languages.
  • Computers are generally huge state machines - As much as functional programming promotes immutability, the machines are stateful as the real world is. There are efficient ways to overcome this in modern functional languages.

Things to note

There are a number of functions that are potentially using another concept we have covered here. For example:

  • Map - Is potentially using reduce in many languages like Elixir.
  • Sum - Is potentially a reduce with /2 sum lambda.
  • Count - Is also most likely a reduce with /2 sum lambda
  • Filter - A map with a lambda that returns Boolean.
  • Reverse - Can be a reduce that accumulates into a reversed enumerable.

This list may go on. This is very important because it brings out abstractions into plane sight hence enabling us to build quality precise code that does exactly what we want without any hidden things.

Functional programming ideas are not only for functional programming. They apply very well in other paradigms like OOP. These concepts are actually multi-paradigm because the solutions they aim to solve exist there too.

FP has a lot of abstractions that are mostly based on tested ways of doing things. A good example is Erlang and Elixir OTP.

Further reading

Here are some further reading resources that I found helpful. There is no harm in reading from different sources and besides, more content will give you more context and richer knowledge.

Thank you for reading.



Thank you for finding time to read my post. I hope you found this helpful and it was insightful to you. I enjoy creating content like this for knowledge sharing, my own mastery and reference.

If you want to contribute, you can do any or all of the following 😉. It will go along way! Thanks again and Cheers!