Functional programming matters in Elixir

This is a short piece (part of an extended series) that will cover the paper Functional Programming Matters, authored by John Hughes (PDF here).

In particular, this piece aims to translate or rewrite parts of the paper in a more modern notation, or rather infix notation, using Elixir, as the Miranda notation used in the paper might be harder to understand. This piece will not cover the benefits of functional programming as the paper itself does that wonderfully.

As a challenge, we will abide by a set of stricter rules in functional programming. No loops and no variable assignments.

We will go over Section 3 of the paper, up to the definition of the function summatrix . This section helps us build the must fundamental blocks of functional programming dealing with lists.

Definition

Let us review the definition that the paper provides for a list

Definition of a list

The star symbol * in the definition above represents anything. It could refer to apples, a data structure, the planets — even other lists. The definition says that a list can be defined as the empty list (which is Nil) or (denoted by the | character ) by one element of type star preappended to another list. It is helpful to clarify that Cons should be understood as the Cons operation and that this definition is recursive. We can take Nil to mean [] — the empty list.

Keep in mind that the definition is recursive and the termination case is defined by appending a list to the empty list.

Section 3 of the paper gives us a way of translating the formal definition to a more familiar notation.

Applying the definition of list

(Now we will get our hands dirty with Elixir. You can either open up an elixir terminal with iex or create a new project using mix new fpmatters and write the definitions to a file.)

In Elixir the Cons operator in the form of the | symbol. The simpler definitions are to the left and Elixir equivalent is defined to the right, followed by the Miranda definition.

[] = []
[1] = [1 | []] # Cons 1 Nil
[1,2,3] = [1 | [2 | [3 | []]]] # Cons 1 (Cons 2 (Cons 3 Nil))

There is a way to bridge the Elixir notation with the Miranda notation by defining a function named cons that uses Elixir’s own | under the hood.

defmodule Fpmatters do
  def cons(a, list \\ []), do: nil
end

Now in the Elixir repl we could type in:

Fpmatters.cons(1, Fpmatters.cons(2))

which is a rather awkward way of saying [1,2] which is equivalent to [1 | [2 | []] under the hood in Elixir.

We now have a very rudimentary way of dealing with lists. Let us now implement the sum operation over a list of integers or floats using nothing but the | operator and pattern matching.

@spec gp_sum(list(number())) :: number()
def gp_sum([]), do: 0
def gp_sum([h | t]), do: h + gp_sum(t)

Our gp_sum function can take a list and it will grab the head of the (assigned to h ) list put it aside, and continue summing the rest of the list until the list is completely traversed and it returns 0 , which leaves the preceding sum unaffected.

the sum function over a list defined in terms of con

We can readily see that

sum (Cons n list)

can be written as

def gp_sum([h | t]), do: h + gp_sum(t)

because

Cons n list <-> [ n | list ] 

in Elixir notation.

Foldr

What we would like to achieve now is to abstract this concept away and come up with a way of iterating over a list using any function and obtaining a result from it after applying the function to every element of the list .

The definition of foldr

The preceding notation makes foldr appear very obscure. We will first throw some light into it by rewriting some parts of it in infix notation (this is not Elixir notation)

foldr f x [] = x

This is the base case. If foldr is passed in the empty list [] it will simply return x without applying the function to it. Keep in mind that x could also be the empty list, a fact that will be very useful later on. We can think of foldr as a function that takes three params, a function f to apply to the list, the an initial value x and a list .

The second line of the Miranda definition above becomes:

foldr f x [a | l] = f a ((foldr f x) l)

What is confusing above the previous notation is the fact that f is standing to the very left of everything as supposed to being in the center — we are very used to reading infix notation. Let’s suppose that f is indeed + and rearrange the terms.

foldr + x [a | l] = + a((foldr f x) l) = a + ((foldr fx) l) 

Now we can see that, foldr is splitting the list into its head and tail and then passing the head as the first argument to the function. Then, it calls itself again passing in the same function, the same initial value and another list — the tail of the list (which is a list).

Now, we are ready to see the definition in Elixir, which will make matters clearer:

@spec foldr((any(), any() -> any()), any(), list(any())) :: any()
def foldr(_, x, []), do: x
def foldr(f, x, [h | t]), do: f.(h, foldr(f, x, t))

As we said before, foldr passes in the head of the list to the function and calls itself again with both f and x unchanged to continue the iteration over the tail of the list.

Fpmatters.foldr(&(&1 + &2), 0, [1, 2, 3])
returns 6

We can now define auxiliary functions by using partial evaluation that use foldr under the hood.

@spec product(list(number())) :: number()
def product(list), do: foldr(&(&1 * &2), 1, list)
@spec sum(list(number())) :: number()
def sum(list), do: foldr(&(&1 + &2), 0, list)

Note that we pass in 1 and 0 as the initial values respectively (each of them is the identity).

Fpmatters.sum([1,3,5]) or [1,3,5] |> Fpmatters.sum()
returns 9
Fpmatters.product([2,3,5]) or [2,3,5] |> Fpmatters.product()
returns 30

This is great. We have just finished writing a reducer. However, we are constrained by what we can do with it: we can only apply a function to a list and get a value, a result by using foldr. What we would like to write now is a function (a map) that when applied to foldr does not simply return a value but another list instead.

Definition of double

The paper gives several more examples of using foldr . After some definitions and examples, we are presented the previous example.

doubleall is a function that under the hood leverages foldr . In this case, the function applied to every element of the list is 2*n .

In Elixir notation, we can write the previous definition as follows:

@spec doublealllist(number())) :: number()
def doubleall(list), do: foldr(fn x, y -> [2 * x | y] end, [], list)

The difference with the previous definitions of sum and product is that we are taking advantage of the fact that we can pass [] as the initial value and use the | operator to preappend the result of the n element to another list.

Fpmatters.doubleall([2, 4, 6])
returns [4, 8, 12]

Map

Instead of leaving the function hardcoded for each case, we will define a map function that takes in a list and a function. It applies the said function to every element of the list while traversing it.

@spec map(list(any()), (any() -> any())) :: list(any())
def map(list, f), do: foldr(&Fpmatters.cons(f.(&1), &2), [], list)

or

@spec map(list(any()), (any() -> any())) :: list(any())
def map(list, f), do: foldr(fn x, y -> [f.(x) | y] end, [], list)

Take note that we can obtain the definition below by substituting in the values.

Definition of map in Miranda notation

Now we have completed another building block that allows us to transform any list into another list of the same length (In the definition above, the x and y arguments are implied, which might make it more difficult to read).

To wrap up, we can define yet another function that leverages all of the building blocks we have built.

@spec summatrix(list(list(number()))) :: number()
def summatrix(list), do: list |> Fpmatters.map(&Fpmatters.sum/1) |> Fpmatters.sum()

In this case, Elixir notation really shines. summatrix adds all the values in a matrix by traversing the rows, collapsing them and them summing the remaining single column.

Conclusion

Functional programming is really powerful and a lot can be done with a few building blocks and lists. Functions allow for a lot of modularity and they can be reused in all parts of your program with the additional benefit that they can be ported to other programs exhibiting deterministic behavior due to their nature. The downside is that it is difficult to think in terms of functions alone sometimes and it takes a while to get used to it.

The next part in the series will go over iterating over trees, a more sophisticated data structure, using functions.

Grab the code here