The General Sequence Object in R Is a List

Sequences come in two flavors in R: vectors and lists . Vectors can only contain basic types, and all elements in a vector must have the same type. Lists can contain a sequence of any type, and the elements in a list can have different types. Lists are thus more general than vectors and are often the building blocks of data structures such as the “next lists” and the trees we used earlier in the book.

It, therefore, comes as no surprise that general functions for working on sequences would work on lists. The three functions, Filter, Map, and Reduce, are also happy to take vectors, but they are treated just as if you had explicitly converted them to lists first. The Reduce function returns a value, not a sequence, of a type that depends on its input, while Filter and Map both return sequences in the form of a list.

From a programming perspective, it is just as easy to work with lists as it is to work with vectors, but some functions do expect vectors—plotting functions and functions for manipulating data frames, for example. So sometimes you will have to translate a list from Filter or Map into a vector. You can do this with the function unlist. This function will convert a list into a vector when this is possible, that is when all elements are of the same basic type, and otherwise will just give you the list back. We will use unlist in many examples in this chapter just because it makes the output nicer to look at, but in most programs, we would not bother doing so until we really need a vector. A list is just as good for storing sequences.

For example, this code:

list(1, 2, 3, 4)
## [[1]]
## [1] 1
##
## [[2]]
## [1] 2
##
## [[3]]
## [1] 3
##
## [[4]]
## [1] 4

gives us a much longer output listing to put in the book than:

1:4
## [1] 1 2 3 4

If you follow along in front of your compute you can see the results with and without unlist to get a feeling for the differences.

You rarely need to convert sequences the other way, from vectors to lists. Functions that work on lists usually also work on vectors, but if you want to, you could use the as.list function and not the list function. The former gives you a list with one element per element in the vector:

as.list(1:4)
## [[1]]
## [1] 1
##
## [[2]]
## [1] 2
##
## [[3]]
## [1] 3
##
## [[4]]
## [1] 4

whereas the latter gives you a list with a single element that contains the vector :

list(1:4)
## [[1]]
## [1] 1 2 3 4

Filtering Sequences

The Filter function is the simplest of the three main functions we cover in this chapter. It simply selects a subset of a sequence based on a predicate. A predicate is a function that returns a single boolean value, and Filter will return a list of elements where the predicate returned TRUE and discard the elements where the predicate returned FALSE:

is_even <- function(x) x %% 2 == 0
unlist(Filter(is_even, 1:10))
## [1]  2  4  6  8 10

The function is often used together with closures so the predicate can depend on local variables:

larger_than <- function(x) function(y) y > x
unlist(Filter(larger_than(5), 1:10))
## [1]  6  7  8  9 10

And of course this works with the curry functions we wrote earlier:

unlist(Filter(curry2(`<`)(5), 1:10))
## [1]  6  7  8  9 10
unlist(Filter(curry2(`>=`)(5), 1:10))
## [1] 1 2 3 4 5

Using curry2 with a binary operator as shown here can look a little confusing, though. We have the left-hand side of the operator immediately to the right of the operator, so the casual reader would expect curry2(<)(5) to pick numbers less than five while in fact it does the opposite since curry2(<)(5) translates to function(y) 5 < y. We can easily fix this by reversing the order of arguments in the curry function:

rcurry2 <- function(f) function(y) function(x) f(x, y)
unlist(Filter(rcurry2(`>=`)(5), 1:10))
## [1]  5  6  7  8  9 10
unlist(Filter(rcurry2(`<`)(5), 1:10))
## [1] 1 2 3 4                      

Here we have used a vector as input to Filter, but any list will do, and we do not need to limit it to sequences of the same type:

s <- list(a = 1:10, b = list(1,2,3,4,5,6),
          c = y ∼ x1 + x2 + x3, d = vector("numeric"))
Filter(function(x) length(x) > 5, s)
## $a
##  [1]  1  2  3  4  5  6  7  8  9 10
##
## $b
## $b[[1]]
## [1] 1
##
## $b[[2]]
## [1] 2
##
## $b[[3]]
## [1] 3
##
## $b[[4]]
## [1] 4
##
## $b[[5]]
## [1] 5
##
## $b[[6]]
## [1] 6

When printed, the results aren’t pretty, but we can’t solve that with unlist in this case. Using unlist we would get a vector, but not one remotely reflecting the structure of the result. The vector a and list b would be flattened into a single vector .

Mapping Over Sequences

The Map function evaluates a function for each element in a list and returns a list with the results:

unlist(Map(is_even, 1:5))
## [1] FALSE  TRUE FALSE  TRUE FALSE

As with Filter, Map is usually combined with closures:

add <- function(x) function(y) x + y
unlist(Map(add(2), 1:5))
## [1] 3 4 5 6 7
unlist(Map(add(3), 1:5))
## [1] 4 5 6 7 8

and can be applied on lists of different types:

s <- list(a = 1:10, b = list(1,2,3,4,5,6),
          c = y ∼ x1 + x2 + x3, d = vector("numeric"))
unlist(Map(length, s))
##  a  b  c  d
## 10  6  3  0

Map can be applied to more than one sequences if the function you provide it takes a number of parameters that matches the number of sequences :

unlist(Map(`+`, 1:5, 1:5))
## [1]  2  4  6  8 10

In this example, we use the function `+`, which takes two arguments, and we give the Map function two sequences, so the result is the component-wise addition.

You can pass along named parameters to a Map call, either directly as a named parameter :

x <- 1:10
y <- c(NA, x)
s <- list(x = x, y = y)
unlist(Map(mean, s))
##   x   y
## 5.5  NA
unlist(Map(mean, s, na.rm = TRUE))
##   x   y
## 5.5 5.5

or as a list provided to the MoreArgs parameter:

unlist(Map(mean, s, MoreArgs = list(na.rm = TRUE)))
##   x   y
## 5.5 5.5

For a single value, the two approaches work the same, but the semantics are slightly different, which comes into play when providing arguments that are sequences. Providing a named argument directly to Map works just as if providing an unnamed argument (except that you can pick a specific variable by name instead of by position). So Map assumes that you want to apply your function to every element of the argument. The reason this works with a single argument is that, as R generally does, the shorter sequence is repeated as many times as needed. With a single argument, that is exactly what we want, but it isn’t necessarily with a sequence.

If we want that behavior, we can just use the named argument to Map, but if we want the function to be called with the entire sequence each time it is called, we must put the sequence as an argument to the MoreArgs parameter .

As an example, we can consider our trusted friend the scale function and make a version where a vector, x, is scaled by the mean and standard deviation of another vector, y:

scale <- function(x, y) (x - mean(y))/sd(y)

If we just provide Map with two arguments for scale, it will evaluate all pairs independently (and we will get a lot of NA values because we are calling the sd function on a single value):

unlist(Map(scale, 1:10, 1:5))
##  [1] NA NA NA NA NA NA NA NA NA NA

The same happens if we name parameter y:

unlist(Map(scale, 1:10, y = 1:5))
##  [1] NA NA NA NA NA NA NA NA NA NA

But if we use MoreArgs, the entire vector y is provided to scale in each call:

unlist(Map(scale, 1:10, MoreArgs = list(y = 1:5)))
##  [1] -1.2649111 -0.6324555  0.0000000  0.6324555
##  [5]  1.2649111  1.8973666  2.5298221  3.1622777
##  [9]  3.7947332  4.4271887

Just as Filter, Map is not restricted to work on vectors, so we can map over arbitrary types as long as our function can handle the different types :

s <- list(a = 1:10, b = list(1,2,3,4,5,6),
          c = y ∼ x1 + x2 + x3, d = vector("numeric"))
unlist(Map(length, s))
##  a  b  c  d
## 10  6  3  0

Reducing Sequences

While Filter and Map produce lists, the Reduce function transforms a list into a value. Of course that value can also be a list, since lists are also values, but Reduce doesn’t simply process each element in its input list independently. Instead, it summarizes the list by applying a function iteratively to pairs. You provide it a function, f, of two elements, and it will first call f on the first two elements in the list. Then it will take the result of this and call f with this and the next element, and continue doing that through the list.

So calling Reduce(f, 1:5) will be equivalent to calling:

f(f(f(f(1, 2), 3), 4), 5)

It is just more readable to write Reduce(f, 1:5).

We can see this in action using `+` as the function:

Reduce(`+`, 1:5)
## [1] 15

You can also get the step-wise results back by using the parameter accumulate. This will return a list of all the calls to f and include the first value in the list, so Reduce(f, 1:5) will return the list:

c(1, f(1, 2), f(f(1 ,2), 3), f(f(f(1, 2), 3), 4),
   f(f(f(f(1, 2), 3), 4), 5))

So for addition we would get:

Reduce(`+`, 1:5, accumulate = TRUE)
## [1]  1  3  6 10 15                      

By default Reduce does its computations from left to right, but by setting the option right to TRUE, you instead get the results from right to left:

Reduce(`+`, 1:5, right = TRUE, accumulate = TRUE)
## [1] 15 14 12  9  5

For an associative operation like `+`, this will, of course, give the same result if we do not ask for the accumulative function calls.

In many functional programming languages, which all have this function, although it is sometimes called fold or accumulate, you need to provide an initial value for the computation. This is then used in the first call to f, so the folding instead starts with f(init, x[1]) if init refers to the initial value and x is the sequence.

You can also get that behavior in R by explicitly giving Reduce an initial value through parameter init:

Reduce(`+`, 1:5, init = 10, accumulate = TRUE)
## [1] 10 11 13 16 20 25

You just don’t need to specify this initial value that often. In languages that require it, it is used to get the right starting point when accumulating results. For addition, we would use 0 as an initial value if we want Reduce to compute a sum because adding zero to the first value in the sequence would just get us the first element. For multiplication, we would instead have to use 1 as the initial value since that is how the first function application will just give us the initial value.

In R we don’t need to provide these initial values if we are happy with just having the first function call be on the first two elements in the list. So multiplication works just as well as addition without providing init:

Reduce(`*`, 1:5)
## [1] 120
Reduce(`*`, 1:5, accumulate = TRUE)
## [1]   1   2   6  24 120
Reduce(`*`, 1:5, right = TRUE, accumulate = TRUE)
## [1] 120 120  60  20   5                      

You wouldn’t normally use Reduce for summarizing values as their sum or product. There are already functions in R for this (sum and prod, respectively), and these are much faster as they are low-level functions implemented in C while Reduce has to be a high-level function to handle arbitrary functions. For more complex data where we do not already have a function to summarize a list, Reduce is often the way to go.

Here is an example taken from Hadley Wickham’s Advanced R book:¹

samples <- replicate(3, sample(1:10, replace = TRUE),
                                     simplify = FALSE)
str(samples)
## List of 3
##  $ : int [1:10] 7 10 4 3 7 10 4 4 4 3
##  $ : int [1:10] 3 6 2 1 8 10 3 3 10 3
##  $ : int [1:10] 7 10 10 3 9 7 9 8 1 4
Reduce(intersect, samples)
## [1] 10  3

We have a list of three vectors each with ten samples of the numbers from 1 to 10, and we want to get the intersection of these three lists. That means taking the intersection of the first two and then taking the intersection of that result and the third list. Perfect for Reduce. We just combine it with the intersection function.

Bringing the Functions Together

The three functions are often used together, where Filter first gets rid of elements that should not be processed, then Map processes the list, and finally Reduce combines all the results.

In this section, we will see a few examples of how we can use these functions together. We start with processing trees. Remember that we can construct trees using the make_node function we wrote earlier, and we can, of course, create a list of trees:

A <- make_node("A")
C <- make_node("C", make_node("A"),
                    make_node("B"))
E <- make_node("E",
               make_node("C", make_node("A"), make_node("B")),
               make_node("D"))

trees <- list(A = A, C = C, E = E)

Printing a tree gives us the list representation of it. If we unlist a tree, we get the same representation, just flattened, so the structure is shown in the names of the resulting vector. But here we wrote a print_tree function that gives us a string representation in Newick format :

trees[[2]]
## $name
## [1] "C"
##
## $left
## $left$name
## [1] "A"
##
## $left$left
## NULL
##
## $left$right
## NULL
##
##
## $right
## $right$name
## [1] "B"
##
## $right$left
## NULL
##
## $right$right
## NULL
unlist(trees[[2]])
##       name  left.name right.name
##        "C"        "A"        "B"
print_tree(trees[[2]])
## [1] "(A,B)"

We can use Map to translate a list of trees into their Newick format and flatten this list to just get a vector of characters:

Map(print_tree, trees)                                                               
## $A
## [1] "A"
##
## $C
## [1] "(A,B)"
##
## $E
## [1] "((A,B),D)"
unlist(Map(print_tree, trees))
##           A           C           E
##         "A"     "(A,B)" "((A,B),D)"

We can combine this with Filter to only get the trees that are not single leaves. Here we can use the size_of_tree function we wrote earlier:

unlist(Map(print_tree,
           Filter(function(tree) size_of_tree(tree) > 1, trees)))
##           C           E
##     "(A,B)" "((A,B),D)"

or we can get the size of all trees and compute their sum by combining Map with Reduce:

unlist(Map(size_of_tree, trees))
## A C E
## 1 3 5
Reduce(`+`, Map(size_of_tree, trees), 0)
## [1] 9

We can also search for the node depth of a specific node and for example get the depth of "B" in all the trees:

node_depth_B <- function(tree) node_depth(tree, "B")
unlist(Map(node_depth_B, trees))
##  A  C  E
## NA  1  2

The names we get in the results are just confusing. They refer to the names we gave the trees when we constructed the list, and we can get rid of them by using the parameter use.names in unlist. In general, if you don’t need the names of a vector, you should always do this. It speeds up computations when R doesn’t have to drag names along with the data you are working on:

unlist(Map(node_depth_B, trees), use.names = FALSE)
## [1] NA  1  2

For trees that do not have a "B" node, we get NA when we search for the node depth, and we can easily remove those using Filter:

Filter(function(x) !is.na(x),
       unlist(Map(node_depth_B, trees), use.names = FALSE))
## [1] 1 2

or we can explicitly check if a tree has node "B" before we Map over the trees:

has_B <- function(node) {
  if (node$name == "B") return(TRUE)
  if (is.null(node$left) && is.null(node$right)) return(FALSE)
  has_B(node$left) || has_B(node$right)
}
unlist(Map(node_depth_B, Filter(has_B, trees)), use.names = FALSE)
## [1] 1 2

The solution with filtering after mapping is probably preferable since we do not have to remember to match the has_B with node_depth_B if we replace them with general functions that handle arbitrary node names, but either solution will work.

The Apply Family of Functions

The Map function is a general solution for mapping over elements in a list, but R has a whole family of Map-like functions that operate on different types of input. These are all named “something”-apply, and we have already seen sapply in Chapter 4. The Map function is actually just a wrapper around one of these, the function mapply, and since we have already seen Map in use, I will not discuss mapply here, but I will give you a brief overview of the other functions in the apply family.

sapply(trees, size_of_tree)
## A C E
## 1 3 5
sapply(trees, identity)
##       A    C      E
## name  "A"  "C"    "E"
## left  NULL List,3 List,3
## right NULL List,3 List,3

vapply(trees, size_of_tree, 1)
## A C E
## 1 3 5

lapply(trees, size_of_tree)
## $A
## [1] 1
##
## $C
## [1] 3
##
## $E
## [1] 5

(m <- matrix(1:6, nrow=2, byrow=TRUE))
##      [,1] [,2] [,3]
## [1,]    1    2    3
## [2,]    4    5    6

collaps_input <- function(x) paste(x, collapse = ":")

apply(m, 1, collaps_input)
## [1] "1:2:3" "4:5:6"

apply(m, 2, collaps_input)
## [1] "1:4" "2:5" "3:6"

apply(m, c(1, 2), collaps_input)
##      [,1] [,2] [,3]
## [1,] "1"  "2"  "3"
## [2,] "4"  "5"  "6"                                                                      

(x <- rnorm(10))
##  [1]  0.1311435 -2.8011897 -0.5525549  0.7913567
##  [5]  0.1799513  0.9231047 -0.7701383  0.2615430
##  [9]  0.4992433 -1.3999893
(categories <- sample(c("A", "B", "C"), size = 10, replace = TRUE))
##  [1] "B" "A" "A" "C" "C" "A" "A" "B" "B" "C"
tapply(x, categories, mean)
##          A          B          C
## -0.8001945  0.2973099 -0.1428937

(categories2 <- sample(c("X", "Y"), size = 10, replace = TRUE))
##  [1] "Y" "X" "Y" "X" "X" "X" "X" "X" "X" "Y"
tapply(x, list(categories, categories2), mean)
##            X          Y
## A -0.8827411 -0.5525549
## B  0.3803931  0.1311435
## C  0.4856540 -1.3999893

Functional Programming in purrr

The Filter, Map, and Reduce functions are the building blocks of many functional algorithms, in addition to recursive functions. However, many common operations require various combinations of the three functions and combinations with unlist, so writing functions using only these three or four functions means building functions from the most basic building blocks. This is not efficient, so you want to have a toolbox of more specific functions for common operations.

The package purrrimplements a number of such functions for more efficient functional programming, in addition to its own versions of Filter, Map, and Reduce. Complete coverage of the purrr package is beyond the scope of this book, but I will give a quick overview of the functions available in the package and urge you to explore the package more if you are serious in using functional programming in R.

keep(1:5, rcurry2(`>`)(3))
## [1] 4 5
discard(1:5, rcurry2(`>`)(3))
## [1] 1 2 3

keep(as.list(1:5), rcurry2(`>`)(3))
## [[1]]
## [1] 4
##
## [[2]]
## [1] 5

every(1:5, rcurry2(`>`)(0))
## [1] TRUE
every(1:5, rcurry2(`>`)(3))
## [1] FALSE
some(1:5, rcurry2(`>`)(3))
## [1] TRUE
some(1:5, rcurry2(`>`)(6))
## [1] FALSE

keep(1:5, ∼ .x > 3)
## [1] 4 5
discard(1:5, ∼ .x > 3)
## [1] 1 2 3                                          

map(1:5, ∼ .x + 2)
## [[1]]
## [1] 3
##
## [[2]]
## [1] 4
##
## [[3]]
## [1] 5
##
## [[4]]
## [1] 6
##
## [[5]]
## [1] 7
map_dbl(1:5, ∼ .x + 2)
## [1] 3 4 5 6 7

map2(1:5, 6:10, ∼ 2 * .x + .y)
## [[1]]
## [1] 8
##
## [[2]]
## [1] 11
##
## [[3]]
## [1] 14
##
## [[4]]
## [1] 17
##
## [[5]]
## [1] 20
map2_dbl(1:5, 6:10, ∼ 2 * .x + .y)
## [1]  8 11 14 17 20

pmap(list(1:5, 6:10, 11:15),
     function(x, y, z) x + y + z)
## [[1]]
## [1] 18
##
## [[2]]
## [1] 21
##
## [[3]]
## [1] 24
##
## [[4]]
## [1] 27
##
## [[5]]
## [1] 30
pmap_dbl(list(1:5, 6:10, 11:15),
         function(x, y, z) x + y + z)
## [1] 18 21 24 27 30

unlist(map_if(1:5, ∼ .x %% 2 == 1, ∼ 2*.x))
## [1]  2  2  6  4 10

map_chr(map(keep(trees, ∼ size_of_tree(.x) > 1), "left"),
        print_tree)
##       C       E
##     "A" "(A,B)"

reduce(1:5, `+`)
## [1] 15

reduce_right(1:5, `*`)
## [1] 120