### This is an edited excerpt of  Hadley Wickham's
### http://adv-r.had.co.nz/Functional-programming.html
### --------------------------------------------------

# Functional programming

At its heart, R is a functional programming (FP) language. It focusses on the creation and manipulation of functions. R has what's known as first class functions: you can do anything with functions that you can do with vectors. You can assign them to variables, store them in lists, pass them as arguments to other functions. You can even create functions without names, and functions within functions (and even have them returned).

By way of a motivating example, which removes redundancy and duplication in code used to clean and summarise data, this chapter will introduce you to some of the key techniques of functional programming in R:

* __Anonymous functions__, functions that don't have a name

* __Closures__, functions written by other functions

* __Lists of functions__, storing functions in a list

Using the case study of __numerical integration__, the chapter concludes by showing you how to build a family of composite integration tools starting from very simple primitives. This will be the recurring theme in this chapter: start with small, easy-to-understand building blocks, combine them into more complex structures, and apply them with confidence.

The discussion of functional programming continues in the following two chapters: [functionals](#functionals) explores functions that take functions as arguments and return vectors as output, and [function operators](#function-operators) explores functions that use functions as inputs and returns them as outputs.

## Motivation

Imagine you've loaded a data file, like the one below, that uses -99 to represent missing values.

```{r}
# Generate a sample dataset
set.seed(1014)
df <- data.frame(replicate(6, sample(c(1:10, -99), 10, rep = TRUE)))
names(df) <- letters[1:6]
head(df)
```

When you first started writing R code, you may have dealt with these -99's by using copy-and-paste, approaching the problem as a series of repetitive tasks:

```{r, eval = FALSE}
df$a[df$a == -99] <- NA
df$b[df$b == -99] <- NA
df$c[df$c == -98] <- NA
df$d[df$d == -99] <- NA
df$e[df$e == -99] <- NA
df$f[df$g == -99] <- NA
```

Juergen Zell:
```{r}
df[ df == -99 ] <- NA
```
One problem with copy-and-paste is that it's easy to make mistakes (can you spot the two in the block above?). The problem with such code is that some items, the -99's for example, are repeated multiple times. Repetition is bad because it allows for inconsistencies (aka bugs) and makes it harder to change code. For example, if the code for a missing value changes from -99 to 9999, you'll need to make changes in multiple places.

To prevent bugs and to make more adaptable software, you should adopt the "do not repeat yourself", or DRY, principle. Popularised by the [pragmatic programmers](http://pragprog.com/about) Dave Thomas and Andy Hunt, this principle states: "every piece of knowledge must have a single, unambiguous, authoritative representation within a system". This is another reason why the ideas behind FP are valuable. They give us tools to help reduce duplication.

We can start applying some of the ideas of FP to our example by writing a function that fixes the missing values in a single vector:

```{r, eval = FALSE}
fix_missing <- function(x) {
  x[x == -99] <- NA
  x
}
df$a <- fix_missing(df$a)
df$b <- fix_missing(df$b)
df$c <- fix_missing(df$c)
df$d <- fix_missing(df$d)
df$e <- fix_missing(df$e)
df$f <- fix_missing(df$e)
```

While this reduces the scope of errors, it doesn't eliminate them. Another potential source of error is that we apply our function to each column one at a time. To address this, we can create a composite function by combining the function for correcting missing values with a function, like `lapply()`, which can, in a single pass, do something to each column in a data frame.

`lapply()` takes three inputs: `x`, a list; `f`, a function; and ``...`, other arguments to pass to `f`. It applies the function to each element of the list and returns a new list. Since data frames are also lists, `lapply()` also works on data frames. `lapply(x, f, ...)` is equivalent to the following for loop:

```{r, eval = FALSE}
out <- vector("list", length(x))
for (i in seq_along(x)) {
  out[[i]] <- f(x[[i]], ...)
}
```

The real `lapply()` is rather more complicated since it's implemented in C for efficiency, but the essence of the algorithm is the same. `lapply()` is called a __functional__, because it takes a function as an argument. Functionals are an important part of functional programming. We'll learn more about them in the [functionals](#functionals)

Note that there's a neat little trick you can use with `lapply()`. Rather than simply assigning the results to `df` you can assign them to `df[]`. By doing so, R's usual subsetting rules take over and you get a data frame instead of a list. (If this comes as a surprise, you might want to read over [subsetting and assignment](#subsetting-and-assignment).)

```{r, eval = FALSE}
fix_missing <- function(x) {
  x[x == -99] <- NA
  x
}
df[] <- lapply(df, fix_missing)
```

As well as being more compact, there are four main advantages of this code over our previous code:

* If the numerical code for missing values changes, we only need to change it in
  one place.

* There is no way for some columns to be treated differently than others.

* Our code works regardless of the number of columns in the data frame: there is
  no way to miss a column because of a copy and paste error.

* It is easy to generalise this technique to a subset of columns:

    ```{r, eval = FALSE}
    df[1:5] <- lapply(df[1:5], fix_missing)
    ```

The key idea here is composition. We take two simple functions, one which does something to each column and one which fixes missing values, and combine them to fix missing values in every column. Writing simple functions that can be understood in isolation and then composited together to solve complex problems is an important technique for effective FP.

What if different columns used different indicators for missing values? You again might be tempted to copy-and-paste:

```{r}
fix_missing_99 <- function(x) {
  x[x == -99] <- NA
  x
}
fix_missing_999 <- function(x) {
  x[x == -999] <- NA
  x
}
fix_missing_9999 <- function(x) {
  x[x == -999] <- NA
  x
}
```

But as before, it's easy to create bugs. The next functional programming tool we'll discuss helps deal with this sort of duplication. When we have multiple functions that all follow same basic template, we can create closures: functions that return functions. Closures allow us to make functions based on a template.

```{r}
missing_fixer <- function(na_value) {
  function(x) {
    x[x == na_value] <- NA
    x
  }
}
fix_missing_99 <- missing_fixer(-99)
fix_missing_999 <- missing_fixer(-999)
fix_missing_9999 <- missing_fixer(-9999)

missing_fixer
fix_missing_99
env <- environment(fix_missing_99)
ls(env)
get("na_value", envir = env)

## 
fix_miss_45  <- fix_missing_99
environment(fix_miss_45) <- new.env() # silly
fix_miss_45(1:10) # error
fix_miss_45  <- fix_missing_99
assign("na_value", -45,  envir = environment(fix_miss_45))
fix_miss_45(1:10) 

fix_miss_45(c(NA,1:4,NA, 8:10))
fix_miss_45(c(-45,1:4,NA, 8:10))
```

(In this case, you could argue that we should just add another argument:

```{r}
fix_missing <- function(x, na.value) {
  x[x == na.value] <- NA
  x
}
```

That's a reasonable solution here, but it doesn't always work well in every situation. We'll see more compelling uses for closures later in the chapter.)

Now consider a new problem. Once we've cleaned up our data, we might want to compute the same set of numerical summaries for each variable. We could write code like this:

```{r, eval = FALSE}
mean(df$a)
median(df$a)
sd(df$a)
mad(df$a)
IQR(df$a)

mean(df$b)
median(df$b)
sd(df$b)
mad(df$b)
IQR(df$b)
```

But again, we'd be better off identifying and removing duplicate items. Take a minute or two to think about how you might tackle this problem before reading on.

One approach would be to write a summary function and then apply it to each column:

```{r, eval = FALSE}
summary <- function(x) {
  c(mean(x), median(x), sd(x), mad(x), IQR(x))
}
lapply(df, summary)
```

But there's still some duplication here. If we make the summary function slightly more realistic, it's easier to see it:

```{r, eval = FALSE}
summary <- function(x) {
 c(mean(x, na.rm = TRUE),
   median(x, na.rm = TRUE),
   sd(x, na.rm = TRUE),
   mad(x, na.rm = TRUE),
   IQR(x, na.rm = TRUE))
}
```

All five functions are called with the same arguments (`x` and `na.rm`) repeated five times. As before, this duplication makes our code fragile: making it easier to introduce bugs and harder to adapt to changing requirements.

To remove this source of duplication, we can take advantage of another functional programming technique: storing functions in lists.

```{r, eval = FALSE}
Summary <- function(x) {
  funs <- c(mean, median, sd, mad, IQR)
  names(funs) <- c("mean", "median", "sd","mad", "IQR")
  sapply(funs, function(f) f(x, na.rm = TRUE))
}

# even nicer:
Summary <- function(x) {
  nms <- c("mean", "median", "sd","mad", "IQR")
  funs <- sapply(nms, get)
  sapply(funs, function(f) f(x, na.rm = TRUE))
}

sapply(df, Summary)
```

The remainder of this chapter will discuss these techniques in more detail. But before we can start on those more complicated techniques, we need to first revisit a simple functional programming tool, anonymous functions.

## Anonymous functions

In R, functions are objects in their own right. They aren't automatically bound to a name and, unlike C, C++, Python or Ruby, R doesn't have a special syntax for creating named functions. You might have noticed this already: when you create a function, you use the usual assignment operator to give it a name.

Given the name of a function, like `"mean"`, it's possible to find the function using `match.fun()`. However, you can't do the reverse. Given the object `f <- mean`, there's no way to find its name. This is because some functions have more than one name and others have no name whatsoever. The latter are called __anonymous functions__.

We use anonymous functions when it's not worth the effort to name a function:

```{r, eval = FALSE}
lapply(mtcars, function(x) length(unique(x)))
Filter(function(x) !is.numeric(x), mtcars)
integrate(function(x) sin(x) ^ 2, 0, pi)
```

Like all functions in R, anonymous functions have `formals()`, a `body()`, and a parent `environment()`:

```{r}
formals(function(x = 4) g(x) + h(x))
body(function(x = 4) g(x) + h(x))
environment(function(x = 4) g(x) + h(x))
``

You can call anonymous functions directly, but the code is a little tricky to read because you must use parentheses in two different ways: first, to call a function, and second to make it clear that you want to call the anonymous function itself, as opposed to calling a (possibly invalid) function _inside_ the anonymous function:

```{r}
# This does not call the anonymous function.
# (Note that "3" is not a valid function.)
function(x) 3  ()

# With appropriate parenthesis, the function is called:
(function(x) 3)()

# So this anonymous function syntax
(function(x) x + 3)(10)

# behaves exactly the same as
f <- function(x) x + 3
f(10)
```

You can supply arguments to anonymous functions in all the usual ways (by position, exact name and partial name) but if you find yourself doing this, it's a good sign that your function needs a name.

One of the most common uses for anonymous functions is to create closures, functions made by other functions. Closures are described in the next section.

### Exercises (2 of 4):

* Use `lapply()` and an anonymous function to find the coefficient of variation (the standard deviation divided by the mean) for all columns in the `mtcars` dataset

* Use `integrate()` and an anonymous function to find the area under the curve for the following functions.

    * `y = x ^ 2 - x`, x in [0, 10]
    * `y = sin(x) + cos(x)`, x in [-pi, pi]
    * `y = exp(x) / x`, x in [10, 20]


## Introduction to closures

"An object is data with functions. A closure is a function with data."
--- [John D Cook](http://twitter.com/JohnDCook/status/29670670701)

One use of anonymous functions is to create small functions that are not worth naming. The other main use is to create closures, functions written by functions.

 Closures get their name from the fact that they __enclose__ the environment of the parent function and can access all its variables. This is useful because it allows us to have two levels of parameters: a parent level to control how the function works and a child level to do the work. The following example shows how we can use this idea to generate a family of power functions in which a parent function (`power()`) creates two child functions (`square()` and `cube()`).

```{r}
power <- function(exponent) {
  function(x) x ^ exponent
}

square <- power(2)
square(2)
square(4)

cube <- power(3)
cube(2)
cube(4)
ls(environment(cube))
ls.str(environment(cube))
env <- environment(cube)
## The next three function calls are equivalent:
get("exponent", env)
env$exponent
as.list(env)$exponent

```

In R, almost every function is a closure. All functions remember the environment in which they were created, typically either the global environment, if it's a function that you've written, or a package environment, if it's a function that someone else has written. The only exception are primitive functions, which call to C directly.

When you print a closure, you don't see anything terribly useful
(but you see that it has a "non-standard" environment):

```{r}
square
cube
```

That's because the function itself doesn't change. The only thing that's different is the enclosing environment, `environment(square)`. One way to see the contents of the environment is to convert it to a list:

```{r}
as.list(environment(square))
as.list(environment(cube))

## as.list is generic has many methods:
as.list ##-> UseMethod ===> it is a S3 generic function
methods(as.list)
#-> 
```

A more compact way is to use `ls.str()` on the environment:
(Hadley prefers to use his own package `pryr` and its `unenclose()`)

```{r}
ls.str(environment(square))
ls.str(environment(cube))
```

This illustrates that the parent environment of a closure is the execution environment of the function that creates it:

```{r}
power <- function(exponent) {
  print(environment())
  function(x) x ^ exponent
}
zero <- power(0)
environment(zero)
```

This environment normally disappears once the function finishes executing, but because we return a function, the environment is captured and attached to the new function. Each time we re-run `power()` a new environment is created, so each function produced by `power()` is independent.

Closures are useful for making function factories, and are one way to manage mutable state in R.

### Function factories

We've already seen two example of function factories, `missing_fixer()` and `power()`. In both these cases using a function factory instead of a single function with multiple arguments has little, if any, benefit. Function factories are most useful when:

* the different levels are more complex, with multiple arguments and complicated bodies

* some work only needs to be done once, when the function is generated

INSERT USEFUL EXAMPLE HERE

We'll see another compelling use of function factories in [mathematical functionals](#mathematical-functionals); they are particularly well suited to maximum likelihood problems.

### Mutable state

Having variables at two levels makes it possible to maintain state across function invocations, because while the function environment is refreshed every time, its parent environment stays constant. The key to managing variables at different levels is the double arrow assignment operator (`<<-`). Unlike the usual single arrow assignment (`<-`) that always assigns in the current environment, the double arrow operator will keep looking up the chain of parent environments until it finds a matching name. ([Environments](#environments) has more details on how it works.)

Together, a static parent environment and `<<-` make it possible to maintain state across function calls.  The following example shows a counter that records how many times a function has been called. Each time `new_counter` is run, it creates an environment, initialises the counter `i` in this environment, and then creates a new function.

```{r}
new_counter <- function() {
  i <- 0
  function() {
    i <<- i + 1
    i
  }
}
```

The new function is a closure, and its enclosing environment is the environment created when `new_counter` is run. Ordinarily, function execution environments are temporary, but a closure maintains access to the environment it was created in. So in the example below, when the closures `counter_one` and `counter_two` are run, each one modifies a counter in a different enclosing environment, maintaining different counts.

```{r}
counter_one <- new_counter()
counter_two <- new_counter()

counter_one()
counter_one()
counter_two()
```

We can use our environment inspection tools to see what's going on here:

```{r}
as.list(environment(counter_one))
as.list(environment(counter_two))
```

The counters get around the "fresh start" limitation by not modifying variables in their local environment. Since the changes are made in the unchanging parent (or enclosing) environment, they are preserved across function calls.

What happens if we don't use a closure? What happens if we only use `<-` instead of `<<-`? Make predictions about what will happen if you replace `new_counter()` with each variant below, then run the code and check your predictions.

```{r}
i <- 0
new_counter2 <- function() {
  i <<- i + 1
  i
}
new_counter3 <- function() {
  i <- 0
  function() {
    i <- i + 1
    i
  }
}
```

Modifying values in a parent environment is an important technique because
it is one way to generate "mutable state" in R. Mutable state is normally
hard to achieve, because every time it looks like you're modifying an
object, you're actually creating a copy and modifying that.

### Exercises (MM: shortened)

* What does `approxfun()` do? What does it return?

* What does the `ecdf()` function do? What does it return?

* Create a function `pick()`, that takes an index, `i`, as an argument and returns a function with an argument `x` that subsets `x` with `i`.

    ```{r, eval = FALSE}
    lapply(mtcars, pick(5))
    # should do the same this as
    lapply(mtcars, function(x) x[[5]])
    ```

## Lists of functions

In R, functions can be stored in lists. Instead of giving a set of functions related names, you can store them in a list. In the same way a data frame makes it easier to work with groups of related vectors, this makes it easier to work with groups of related functions.

We'll start with a simple benchmarking example. Imagine you are comparing the performance of multiple ways of computing the arithmetic mean. You could do this by storing each approach (function) in a list:

```{r}
compute_mean <- list(
  base = function(x) mean(x),
  sum = function(x) sum(x) / length(x),
  manual = function(x) {
    total <- 0
    n <- length(x)
    for (i in seq_along(x)) {
      total <- total + x[i] / n
    }
    total
  }
)
```

Calling a function from a list is straightforward. You just extract it from the list:

```{r}
x <- runif(1e5)
system.time(compute_mean$base(x))
system.time(compute_mean[[2]](x))
system.time(compute_mean[["manual"]](x))
```

If we want to call each of the functions to check that we've implemented them correctly and that they return the same answer, we can use `lapply()`, either as an anonymous function or as a named function.

```{r}
lapply(compute_mean, function(f, ...) f(...), x)

call_fun <- function(f, ...) f(...)
lapply(compute_mean, call_fun, x)
```

If we want to time how long each function takes, we can combine lapply with `system.time()`:

```{r}
lapply(compute_mean, function(f) system.time(f(x)))
```

Another use for a lists of functions is summarising an object in multiple ways. To do that, we could store each summary function in a list, and then run them all with `lapply()`:

```{r}
funs <- list(
  sum = sum,
  mean = mean,
  median = median
)
lapply(funs, function(f) f(1:10))
```

What if we wanted our summary functions to automatically remove missing values? One approach would be make a list of anonymous functions that call our summary functions with the appropriate arguments:

```{r, eval=FALSE}
funs2 <- list(
  sum = function(x, ...) sum(x, ..., na.rm = TRUE),
  mean = function(x, ...) mean(x, ..., na.rm = TRUE),
  median = function(x, ...) median(x, ..., na.rm = TRUE)
)
lapply(funs2, function(f) f(x))
# ...
```

This, however, leads to a lot of duplication. Apart from a different function name, each function is almost identical. A better approach would be to modify our original `lapply()` call to include the argument:

```{r, eval=FALSE}
lapply(funs, function(f) f(x, na.rm = TRUE))
# ...
```

It's also possible to do this in a more functional way by generating a list of functions that remove missing values.

```{r, eval=FALSE}
funs2 <- lapply(funs, function(f) {
  function(...) f(..., na.rm = TRUE)
})

# Or use a named function instead of an anonymous function
remove_missings <- function(f) {
  function(...) f(..., na.rm = TRUE)
}
funs2 <- lapply(funs, remove_missings)
```

### Exercises

* Implement a summary function that works like `base::summary()`, but uses a list of functions. Modify the function so it returns a closure, making it possible to use it as a function factory.

* Create a named list of all base functions. Use `ls()`, `get()` and `is.function()`. Use that list of functions to answer the following questions:

    * Which base function has the most arguments?
    * How many base functions have no arguments?

* Which of the following commands is equivalent to `with(x, f(z))`?

    (a) `x$f(x$z)`
    (b) `f(x$z)`
    (c) `x$f(z)`
    (d) `f(z)`