Chapter 7. Higher-Order Functions and List Comprehensions

Higher-order functions, functions that accept other functions as arguments, are a key place where Erlang’s power really starts to shine. Unlike many languages, Erlang treats higher-order functions as a native and natural part of the language rather than an oddity. List comprehensions apply them in a compact style.

Simple Higher-Order Functions

Way back in Chapter 2, you saw how to use a fun to create a function:

1> Fall_velocity = fun(Distance) -> math:sqrt(2 * 9.8 * Distance) end.
#Fun<erl_eval.6.111823515>
2> Fall_velocity(20).
19.79898987322333
3> Fall_velocity(200).
62.609903369994115

Erlang not only lets you put functions into variables, it lets you pass functions as arguments. This means that you can create functions whose behavior you modify at the time you call it, in much more intricate ways than are normally possible with parameters. A very simple function that takes another function as an argument might look like Example 7-1, which you can find in ch07/ex1-hof.

Example 7-1. An extremely simple higher-order function
-module(hof).
-export([tripler/2]).

tripler(Value, Function) -> 3 * Function(Value).

The argument names are generic, but fit. tripler/2 will take a value and a function as arguments. It runs the value through the function, and multiplies that result by three. In the shell, this might look like the following:

1> c(hof).
{ok,hof}
2> MyFunction=fun(Value)->20*Value end.
#Fun<erl_eval.6.111823515>
3> hof:tripler(6,MyFunction).
360

That defines another simple function taking one argument (and returning that number multiplied by 20), and stores it in the variable MyFunction. Then it calls the hof:tripler/2 function with a value of six and the MyFunction function. In the hof:tripler/2 function, it feeds the Value to the Function, getting back 120. Then it triples that, returning 360.

You can skip assigning the function to a variable if you want, and just include the fun declaration inside the hof:tripler/2 function call:

4> hof:tripler(6,fun(Value)->20*Value end).
360

That may or may not be easier to read, depending on the functions and your expectations. This case is trivially simple, but demonstrates that it works.

Warning

While this is a powerful technique, you can outsmart yourself with it easily. (I do!) Just as with normal code, you need to make sure the number and sometimes the type of your arguments line up. The extra flexibility and power can create new problems if you aren’t careful.

fun has a few other tricks up its sleeve that you should know. You can use a fun to preserve context, even context that has since vanished:

5> X=20.
20
6> MyFunction2=fun(Value)->X * Value end.
#Fun<erl_eval.6.82930912>
7> f(X).
ok
8> X.
* 1: variable 'X' is unbound
9> hof:tripler(6,MyFunction2).
360

Line 5 assigns a variable named X a value, and line 6 uses that variable in a fun. Line 7 obliterates the X variable, as line 8 demonstrates, but line 9 shows that MyFunction2 still remembers that X was 20. Even though the value of X has been flushed from the shell, the fun preserves the value and can act upon it. (This preservation is called a closure.)

You may also want to pass a function from a module, even a built-in module, to your (or any) higher-order function. That’s simple, too:

7> hof:tripler(math:pi(), fun math:cos/1).
-3.0

In this case, the hof:tripler function receives the value pi and a fun, which is the math:cos/1 function from the built-in math module. Since the cosine of pi is -1, the tripler returns -3.0.

Creating New Lists with Higher-Order Functions

Lists are one of the best and easiest places to apply higher-order functions. Applying a function to all the components of a list to create a new list, sort a list, or break a list into smaller pieces is common. And you don’t need to do much work to make it happen: Erlang’s built-in lists module offers a variety of higher-order functions, listed in Appendix A, that take a function and list and do something with them. You can also use list comprehensions to do much of the same work. The lists module may seem easier at first, but as you’ll see, list comprehensions are powerful and concise.

Running List Values Through a Function

You might also want to create a new list based on what a function does with all of the values in the original list. You can square all of the values in a list by creating a function that returns the square of its argument, and passing that to lists:map/2. Instead of returning ok, it returns a new list reflecting the work of the function it was given:

4> Square = fun(Value)->Value*Value end.
#Fun<erl_eval.6.111823515>
5> lists:map(Square,List).
[1,4,16,64,256,1024]

There’s another way to accomplish the same thing, with what Erlang calls list comprehension.

6> [Square(Value) || Value <- List].
[1,4,16,64,256,1024]

That produces the same resulting list, with different (and more flexible) syntax. While you saw the [A | B] syntax in list constructors, a list comprehension uses [A || B] syntax. That extra vertical bar changes the whole way this is interpreted. Instead of being a head and a tail, it’s an expression—here a function—and a rule for extracting the arguments for that function from a list, called a generator.

In this case, the function is the fun you put in the Square variable on line 4. Its argument, Value, is taken on a walk through the List. That arrow (the <-) means “an element of,” or if you want be more active, “comes from.” You can read this list comprehension as “Create a list consisting of squares of a Value, where the Value comes from List.”

Strictly speaking, the expression on the left doesn’t have to be formally declared as a function. You can get the same results with something less formal:

7> [Value * Value || Value <- List].
[1,4,16,64,256,1024]
Note

The multiplication operator (*) is technically a call to the */2 function, but any legal Erlang expression can be on the left of the ||.

Beyond List Comprehensions

List comprehensions are concise and powerful, but they lack a few key features available in other recursive processing. The only type of result they can return is a list, but there will be many times when you want to process a list and return something else, like a Boolean, a tuple, or a number. List comprehensions also lack support for accumulators, and don’t let you suspend processing completely when certain conditions are met.

You could write your own recursive functions to process lists, but much of the time you’ll find that the lists module already offers a function that takes a function you define and a list and returns what you need.

Splitting Lists

Filtering lists is useful, but sometimes you want to know what didn’t go through the filter, and sometimes you just want to separate items.

The lists:partition/2 function returns a tuple containing two lists. The first is the list items that met the conditions specified in the function you provided, while the second is the items that didn’t. If the Compare variable is defined as shown in line 14 of the previous demonstration, returning true when a list value is greater than 10, then you can easily split a list into a list of items greater than 10 and a list of items fewer than 10:

17> lists:partition(Compare,List).
{[16,32],[1,2,4,8]}

Sometimes you’ll want to split a list by starting from the beginning—the head—and stopping when a list value no longer meets a condition. The lists:takewhile/2 and lists:dropwhile/2 functions create a new list that contains the parts of an old list before or after encountering a boundary condition. These functions aren’t filters, and to make that clear, the examples use a different list than the rest of the examples in this chapter:

18> Test=fun(Value) -> Value < 4 end.
#Fun<erl_eval.6.111823515>
19> lists:dropwhile(Test, [1,2,4,8,4,2,1]).
[4,8,4,2,1]
20> lists:takewhile(Test, [1,2,4,8,4,2,1]).
[1,2]

Both functions run through a list from head to tail and stop when they reach a value for which the function you provide as the first argument returns false. The lists:dropwhile/2 function returns what’s left of the list, including the value that flunked the test. It does not, however, filter out later list entries that it might have dropped if they had appeared earlier in the list. The lists:takewhile/2 function returns what was already processed, not including the value that flunked the test.

Folding Lists

Adding an accumulator to list processing lets you turn lists into much more than other lists, and opens the door to much more sophisticated processing. Erlang’s lists:foldl/3 and lists:foldr/3 functions let you specify a function, an initial value for an accumulator, and a list. Instead of the one-argument functions you’ve seen so far, you need to create a two-argument function, accepting the current value in the list traversal and the accumulator. The result of that function will become the new value of the accumulator.

Defining a function that works within the folding functions looks a little different, because of the two arguments:

21> Divide=fun(Value, Accumulator) -> Value / Accumulator end.
#Fun<erl_eval.6.111823515>

This function divides its first argument—to be the Value coming from the list—by its second, the Accumulator passed to it by the function doing the folding.

Folding has one other key twist. You can choose whether you want the function to traverse the list from head to tail, with lists:foldl/3, or from tail to head, with lists:foldr/3. foldl means “fold from left to right,” and foldr means “fold from right to left.” If order doesn’t change the result, you should go with lists:foldl/3, as its implementation is tail-recursive and more efficient in most situations.

The Divide function is one of those cases that will produce very different results depending on the direction in which you process the list (and the initial accumulator value). In this case, folding also produces different results than you might expect in a simple division. Given the usual List of [1,2,4,8,16,32], it seems like going from left to right will produce 1/2/4/8/16/32, and going from right to left will produce 32/16/8/4/2/1, at least if you use an initial accumulator of 1. The functions don’t produce those results, however:

22> 1/2/4/8/16/32.
3.0517578125e-5
23> lists:foldl(Divide,1,List).
8.0
24> 32/16/8/4/2/1.
0.03125
25> lists:foldr(Divide,1,List).
0.125

This code seems too simple to have a bug, so what’s going on? Table 7-1 walks through the calculations for lists:foldl(Divide,1,List), and Table 7-2 walks through lists:foldr(Divide,1,List) step by step.

Table 7-1. Recursive division of a list forwards with foldl/3
Value from List Accumulator Result of Division

1

1

1

2

1 (1/1)

2

4

2 (2/1)

2

8

2 (4/2)

4

16

4 (8/2)

4

32

4

8
Table 7-2. Recursive division of a list backwards with foldr/3
Value from List Accumulator Result of Division

32

1

32

16

32 (32/1)

0.5

8

0.5 (32/16)

16

4

16 (8/0.5)

0.25

2

0.25 (4/16)

8

1

8

0.125

Moving through a list step-by-step produces very different values. In this case, the simple Divide function’s behavior changes drastically above and below the value 1, and combining that with walking through a list item by item yields results that might not be precisely what you expected.

Note

The result of the foldl is the same as 32/(16/(8/(4/(2/(1/1))))), while the result of the foldr is the same as 1/(2/(4/(8/(16/(32/1))))). The parentheses in those expressions perform the same restructuring as the fold, and the concluding 1 in each is where the initial accumulator value fits in.

Folding is an incredibly powerful operation. This simple if slightly weird example just used a single value, a number, as an accumulator. If you use a tuple as the accumulator, you can store all kinds of information about a list as it passes by, and even perform multiple operations. You probably won’t want to try to define the functions you use for that as one-liners, but the possibilities are endless.