Zhen Zhang's Blog

Functional Programming Introduction

These days I read the “Advanced R” Book written by Hadley Wickham. I choose this book since I think I have mastered most of R’s intermediate commands, and can use it freely to do data analysis job now, so I need to gain some knowledge related to R’s architecture in order to write the codes more neatly and think in the language of R, not other language.

One thing that is very interested to me is the property of functional programming. Previously, I thought R is a objected-oriented programming language like Python. Although it has a informal class definition, say S3, which is most prevalent in R packages, I still categorized it to the OOP group. But as Wickham says: “R, at its heart, is a functional programming (FP) language. This means that it provides many tools for the creation and manipulation of functions.” I did not understand this sentence very well some days before, but as time went on, I read the following chapters and referred to some other resources talking about this topic, evening comparing it with Python, I have a basic understand now.

In this post, I will display the concepts and knowledge I learnt these days. Since I am the first time learning this topic, I may explain them not very accurately or deeply, but I want to summary it here, and compare to my future notions to make progress. So let’s start.

Functional Programming (FP)

“In computer science, functional programming 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.” (From wikipedia).

The definition is a little bit abstract, so let’s make it clear, talking about some important features that functional programming have:

  • Immutable Data: A function should have immutable data, for sake of easily maintaining. Then a function with fixed input will have fixed output every time we call it. This kind of function is called a pure function, meaing a function with no side effect. If it is necessary to edit an argument for a function, we need to copy it out of the function and then modify it.

  • First-Class Function: A function that can be used like a variable is called a first-class function. This means that you can create, copy, modify a function like you are doing the same thing to a variable, even transferring it between functions and return it as the final output of another function.

  • Tail Recursion: Usually the recursion we write in Java is calling the stacks of a functions once it is being created. But this will cause a problem named stack overflow if we do not allocate the memory in an appropriate way. With tail recursion and the help of compilor, we can avoid this problem.

In the following parts I will explain it in a detail.

Functionals

Anonymous function

I will first introduce anonymous function although it does not belong to this part. Anonymous function is a function writing standard that enables us to write functions very quickly, without explicitly defining it:

1
lapply(1:8, function(x) x + 1)
1
new_list = [lambda x: x ** 2 + 1 for x in range(8)]

These are the expressions in R and python (lambda) respectively. With this technique, we can write functions more concisely.

Looping

Loop is widely used in programming. Consider the following program:

1
2
3
new_list = []
for i in range(n):
new_list[i] = i ** 2

This is not a good way, although it is all right. In python, we have another way of doing it: List Comprehension:

1
new_list = [i ** 2 for i in range(n)]

The most important advantage of using list comprehension is not about its speed (althought it indeed runs a little faster than looping): we can read the program in a more continuous way. Every time I read a loop, I need to assume myself as the loop pointer to figure out what the loop is really doing, so I am often in such a mess.

In R, we have apply family functions that can do the same thing:

1
new_list <- lapply(1:n, function(x) x^2)

(The apply family functions play such an important role in R, and maybe I will talk about it in a another post).

So now I need to dig a little deeper: what is the idea behind these functions?

Dimension Reduction

Recall functionals are the functions that accepts a function as input and return a value without function. The list comprehension in python and apply family functions in R are all functionals, and they do the same thing: dimension reduction. Think of it: if you want to create a list, you need to fill in elements, and now you are moving from 2-dimension to 1-dimension. This is more clear in R apply functions: for example, the lapply function:

1
lapply(data, FUN, ...)

The data that passed into the function will be the lower level of data rendered in the input field: if the data is a list, then the data into the function is each elements of that list.

Map, Reduce and Filter

These three functions have almost become the identifiers of a functional programming language. Fortunately, Python and R all have such implementations. Here I will use R as the example:

1
2
3
Map(function(...), ...)
Reduce(function(...), list)
Filter(function, list)

The Map function will get each elements in the following data and substitute them in the function. The Reduce function will take the first and second elements into the function, get the ouput, then take the output and the third elements into the function, so on so forth. The Filter function will have the function return a logical value, then every element that returns true will remain in the list.

I will not create examples here, but remember, all of them split the list into lower level data so we can handle them like we are writing a loop.

Limitations

This method is very strong, but it still has many limitations:

  1. When modifying in place, there will be some trouble:

    1
    2
    new_list <- 1:9
    lapply(new_list, function(x) x <- x + 1)

    This will not return the true value, since all the operations we do in the functions are only visible to the function itself. All variables we modify in the function are not global variables, they are just local variables. The value of local variables will not affect the value of global variables. In this situation, it is better to write a loop. But what is we want to do it in a function?

    1
    2
    new_list <- 1:9
    lapply(new_list, function(x) x <<- x + 1)

    This method can do it, since the <<- operator can modify objects in the global environment. But I do not recommed to do so, since it will cause the variables in a confused state.

  2. Recursive relationships

    Consider when we are doing logistic regression. We need gradient descent to update the weights vector:

    $$w_i := w_i - \alpha\frac{\partial RSS}{\partial w_i}$$

    In this case, the program can only be written in the loop format, since the $i+1$ state depends on the $i$ state:

    1
    2
    3
    for (i in 1:10000) {
    w <- w - alpha * adjust
    }
  3. While loop

    When we are using a while loop, sometimes we do not know when to stop if we define a stopping criterion. So in this time, we can only use a loop.

  4. Lazy evaluation

    Lazy evaluation means the value of the arguments will not be evaluated until it is used the first time. In other words, the function does not know the value when the stack is first created, but only know it when the value first appears.

    1
    2
    3
    4
    5
    6
    7
    what_is_love <- function(f) {
    function(...) {
    cat('f is', f, '\n')
    }
    }
    funs <- lapply(c('love', 'cherry'), what_is_love)

    When you print the functions in funs, the value will be identical: both are “f is cherry”. It is not a good phenomenon, so how to solve it?

    1
    2
    3
    4
    5
    6
    what_is_love <- function(f) {
    force(f)
    function(...) {
    cat('f is', f, '\n')
    }
    }

    The inner function creates an enclosure for f, but the catch is that until you actually use a variable passed to a function, it remains a “promise” and is not actually evaluated. If you want to “capture” the current value of f, then you need to force the evaluation of the promise; you can use the force() function for this.

    But this has been changed in R version 3.2.0: “Higher order functions such as the apply functions and Reduce() now force arguments to the functions they apply in order to eliminate undesirable interactions between lazy evaluation and variable capture in closures.”

Compare between OOP and FP

A famous use is the sort method in python:

1
2
a = [1,4,2,7,3,9]
sort(a)

But the behavior of sort can be changed by giving a compare method to sort:

1
2
3
4
5
6
7
8
def new_sort_method(x, y)
if x > y:
return -1
if x < y:
return 1
return 0
sort(a, new_sort_method)

We can see now the list is ordered in a descent order. Note that the sort function accepts a user defined sort method as its input. But if I want to implement it in a OOP language, such as Java, what should I do?

1
2
3
4
5
6
7
8
9
10
public interface Comparator {
compareTo(x, y)
}
Integer[] new_list = new Integer[8]
new_list.sort(Comparator() {
compare(o1, o2) {
return o1 - o2
}
})

Although I use anonymous class here, the implementation is still very long: I need to define an interface that implements the compare method, then the sort method for the list object must accepts a new class instance that implements that interface.

Function Operators

Return a function

The functionals in the last section all return values as the output. But what if I write a function that return a function as an output?

This is the definition of function operators. A function operator is a function that takes one (or more) functions as input and returns a function as output.

In general, the function operator can modify the input, output, inner behavior. In this section, I will first introduce closures,second then partial, then decorator functions.

Closures

List of functions

Closure is a very important concept in functional programming. Consider this situation: I want to calculate the output of a exponential power. But the question is, I do not know the accurate power. Sometimes it can be one, sometimes two. So do I need to write functions every time I use a different power?

Of course not. Keep in mind, in functional programming, almost every operation needs to be done once and only once. So this is the situation where closure can solve:

1
2
3
def cal_power(n):
def inner_cal_power(x):
return x ** n

Then I can reuse it as follows:

1
2
3
4
power_one <- cal_power(1)
power_one(4)
power_two <- cal_power(2)
power_two(4)

So in this manner, we can view closure as defining a list of functions. Then we can use lapply to quickly return a list of functions by giving the closure a list of inputs.

Mutable State

Accurately speaking, closure is not really a function. It just behaviors like a function. Also, when we create a closure, the outer function will not disappear: since the closure is using the local variable of the outer function. But here comes another important question: if I can modify the value of local variable in the outer function, then each closure will maintain a unqiue value of that particular local variable since each closure is defined separately.

Yes. This is the concept of mutable state. With this notion in mind, we can create a counter that counts the time that the function is called:

1
2
3
4
5
6
7
8
counter <- function(f) {
i <- 1
function(...) {
if (i % 8) == 0 cat("I have been called 8 times!")
f(...)
i <<- i + 1
}
}

Here I use the <<- operator to modify the global variable (to the closure). Then the function will print “I have been called 8 times” when it is called for a 8 time in total.

Partial

Closure can be viewed as the process of creating a function by giving an argument to a function that you create all by yourself, which does not exist before. But, what should I do if I want to creating a function by giving an argument to a function that already exists? It is called partial.

A partial function can be defined by partial giving the function name and at least one of the function’s argument:

1
mean_na_rm <- partial(mean, na.rm = T)

Then we have mean_na_rm(x) equals to mean(x, na.rm = T). In other words, it increase the ability of reuse of one particular argument by creating a corresponding function for it.

Currying

Suppose I have a function f that has so many arguments: f(x, y, z, w...), then a typical calling format is to give the arguments values f simultaneously. But it can cause confusion. What if I want to supply only one argument each time?

1
2
3
4
# One implementation
so_long <- f(x, y, z, w...)
# Another implementation
not_so_long <- partial(w, partial(z, partial(y, partial(f, x))))

The second format is a little wired: why should I do so? This is called currying. By implementing like this, we can encapsulate a function with several arguments to several functions with only one argument for each. Each inner function has been encapsulated as a new function and then acts as input of the next encapsulated partial function. This written type if a little complicated, but what if I write it like this?

1
so_short <- f(x)(y)(z)(w)

It is much better now!

Decorator

Decorator without arguments

Now comes the decorator. Decorator can modify the behavior of a function. First let’s see a example:

1
2
3
4
5
6
def decorator(f):
def wrapper(*args, **kwargs):
print("Hi, I will be called!")
f(*args, **kwargs)
print("Hi, I have been called!")
return wrapper

The decorator accepts a function as its input, and after that, the function is decorated. It will do the behavior we defined in the decorator:

1
2
3
4
5
6
7
def hello_world():
print("Hello world")
hello_world()
hello_world() = decorator(hello_world)
hello_world()

Here we can see the output of the function has been changed.

In python, the decorator is so popular that there is a particular mark to do it:

1
2
3
4
5
@decorator
def hello_world():
print("Hello world")
hello_world()

Decorator with arguments

What if I want a decorator with different arguments every time I use it? It is a little hard in the first glimpse, but which function can we use to store the different input afterwards but can be created without knowing them? In other words, the decorator with arguments must remember the argument you first give it, and can generate a list of functions as you want. Yes, it is the closures.

For this question, we only need to wrap the decorator with closures:

1
2
3
4
5
6
7
8
9
def closure_wrapper(x):
def decorator(f):
def wrapper(*args, **kargs):
print(x)
print("Hi, I will be called!")
f(*args, **kwargs)
print("Hi, I have been called!")
return wrapper
return decorator

Then we need to first give the argument to the decorator closure, and the result will be served as a decorator.

Tail Recursion

Although python and R do not support for tail recursion, I still want to talk about it, since I am mostly talking about the concept of functional programming.

Tail call

So what is tail call? The tail call is you call the function at the last of a function, without any other calculations:

1
2
def f(x):
return g(x)

There is one circumstance that are not tail call: with other calculations:

1
2
def f(x):
return g(x) + 1

But we only need the return function at the end of the calling function, not at the end of the program.

But why should we focus on this?

In general, a function call is accompanied with a stack. If one function is calling another without tail call, the new stack will be put on the old stack, which means the length of the initial stack will continue growing until it overflows. But tail call will not encounter this issue: since tail call is the last step of a function call, so the function only needs to remember the tail call stack state, and destroy the initial stack.

Recursion

Recursion often creates stacks very long, so it is the time to use tail call as the implementation of tail recursion.

Here I use fibonacci sequence as the example:

Normal Recursion:

1
2
3
4
5
def fibonacci(n):
if n <= 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)

Tail Recursion Version:

1
2
3
4
5
6
7
def fibonacci(n):
def fibonacci_rec(a, b, n):
if n == 0:
return a
else:
return fibonacci(b, a + b, n - 1)
return fibonacci_rec(1, 1, n)

Tail recursion usually needs one or more new arguments to memorize the temporary value in the function instead of storing it as a local variable in the stack. So we usually needs to define a new function to accepts more arguments. Then the initial function calls the new function at last, after the recursion job has been done by the new function.

Future

I think functional programming is the future of programming languages, since it can do parallel computing, and we can see the developing speed of scala. But who knows? I only know with these tools, I can write the codes more efficiently.