Higher-Order Functions and List Comprehensions - Introducing Elixir: Getting Started in Functional Programming (2014)

Introducing Elixir: Getting Started in Functional Programming (2014)

Chapter 8. Higher-Order Functions and List Comprehensions

Higher-order functions, functions that accept other functions as arguments, are a key place where Elixir’s power really starts to shine. It’s not that you can’t do higher-order functions in other languages — you can in many — but rather that Elixir treats higher-order functions as a native and natural part of the language rather than an oddity.

Simple Higher-Order Functions

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

iex(1)> fall_velocity = fn(distance) -> :math.sqrt(2 * 9.8 * distance) end

#Function<6.106461118/1 in :erl_eval.expr/5>

iex(2)> fall_velocity.(20)

19.79898987322333

iex(3)> fall_velocity.(200)

62.609903369994115

Elixir 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 them, in much more intricate ways than is normally possible with parameters. A very simple function that takes another function as an argument might look like Example 8-1, which you can find in ch08/ex1-hof.

Example 8-1. An extremely simple higher-order function

defmodule Hof do

def tripler(value, function) do

3 * function.(value)

end

end

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:

iex(1)> c("hof.ex")

[Hof]

iex(2)> my_function = fn(value) -> 20 * value end

#Function<6.106461118/1 in :erl_eval.expr/5>

iex(3)> Hof.tripler(6, my_function)

360

Line 2 defines another simple function taking one argument (and returning that number multiplied by 20) and stores it in the variable my_function. Then line 3 calls the Hof.tripler/2 function with a value of 6 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 fn declaration inside the Hof.tripler/2 function call:

iex(4)> Hof.tripler(6, fn(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.

Elixir gives you another way to specify the function: you can use & as the capture operator, &1 to stand for the first argument, and so on. Using this notation, you can make the previous examples even simpler:

iex(5)> ampersand_function = &(20 * &1)

#Function<6.106461118/1 in :erl_eval.expr/5>

iex(6)> Hof.tripler(6, ampersand_function)

360

iex(7)> Hof.tripler(6, &(20 * &1))

360

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.

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

iex(8)> x = 20

20

iex(9)> my_function2 = fn(value) -> x * value end

#Function<6.106461118/1 in :erl_eval.expr/5>

iex(10)> x = 0

0

iex(11)> my_function2.(6)

120

Line 8 assigns a variable named x a value, and line 9 uses that variable in a fn. Line 10 changes the x variable, but line 11 shows that my_function2 still remembers that x was 20. Even though the value of x has been changed, the fn preserves the value and can act upon it. (This is called aclosure.)

Again, you can use the ampersand notation:

iex(12)> x = 20

20

iex(13)> my_function3 = &(x * &1)

#Function<6.106461118/1 in :erl_eval.expr/5>

iex(14)> x = 0

0

iex(15)> Hof.tripler(6, my_function3)

360

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:

iex(16)> Hof.tripler(:math.pi, &:math.cos(&1))

-3.0

In this case, the Hof.tripler function receives the value pi and a function, which is the :math.cos/1 function from the built-in math module. Since the function has arity 1, you must indicate this with &1. 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 popular work. You don’t need to do much difficult work to make this happen, though: Elixir’s built-in List and Enum modules offer 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 List and Enum modules may seem easier at first, but as you’ll see, list comprehensions are powerful and concise.

NOTE

The functions in the Enum module will work on any collection of data (for example, the individual lines in a file); the functions in List make sense only for lists.

Reporting on a List

The simplest of these functions is Enum.each/2, which always returns the atom :ok. That may sound strange, but Enum.each/2 is a function you’ll call if and only if you want to do something to the list with side effects — like present the contents of a list to the console. To do that, define a list and a simple function that applies IO.puts/1, here stored in the variable print, and then pass them both to Enum.each/2:

iex(1)> print = fn(value) -> IO.puts(" #{value}") end

#Function<6.106461118/1 in :erl_eval.expr/5>

iex(2)> list = [1,2,4,8,16,32]

iex(3)> Enum.each(list, print)

1

2

4

8

16

32

:ok

The Enum.each/2 function walked through the list, in order, and called the function in print with each item of the list as a value. The IO.puts function inside of print presented the list item, slightly indented. When it reached the end of the list, Enum.each/2 returned the value :ok, which the console also displayed.

NOTE

Most of the demonstrations in this chapter will be operating on that same list variable containing [1,2,4,8,16,32].

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 Enum.map/2. Instead of returning :ok, it returns a new list reflecting the work of the function it was given:

ex(4)> square = &(&1 * &1)

#Function<6.106461118/1 in :erl_eval.expr/5>

iex(5)> Enum.map(list, square)

[1, 4, 16, 64, 256, 1024]

NOTE

If you want to generate a list of sequential integers (or characters), you can use the notation start..end. You normally use this notation with integers, but you can also use it with characters, with rather unusual results:

iex(6)> Enum.map(1..3, square)

[1, 4, 9]

iex(7)> Enum.map(-2..2, square)

[4, 1, 0, 1, 4]

iex(8)> Enum.map(?a..?d, square)

[9409, 9604, 9801, 10000]

There’s another way to accomplish the same thing that Enum.map/2 does, with what Elixir calls a list comprehension:

iex(9)> for value <- list, do: value * value

[1, 4, 16, 64, 256, 1024]

That produces the same resulting list, with different (and more flexible) syntax.

You can read this list comprehension as “For each value in list list, create an entry value * value in a new list.” You can also use ranges in a list comprehension: for value ← 1..3, do: value * value.

Filtering List Values

The Enum module offers a few different functions for filtering the content of a list based on a function you provide as a parameter. The most obvious, Enum.filter/2, returns a list composed of the members of the original list for which the function returned true. For example, if you wanted to filter a list of integers down to values that could be represented as four binary digits, so numbers 0 or greater but less than 16, you could define a function and store it in four_bits:

iex(10)> four_bits = fn(value) -> (value >= 0) and (value < 16) end

#Function<6.106461118/1 in :erl_eval.expr/5>

Then, if you apply it to the previously defined list of [1,2,4,8,16,32], you’d get just the first four values:

iex(11)> Enum.filter(list, four_bits)

[1, 2, 4, 8]

Once again, you can create the same effect with a list comprehension. This time, you don’t actually need to create a function, but instead use a guard-like construct (written without the when) on the right side of the comprehension:

iex(12)> for value <- list, value >= 0, value < 16, do: value

[1, 2, 4, 8]

NOTE

If you also want a list of values that didn’t match, use Enum.partition/2, which returns both the matched and unmatched values as separate lists.

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 Enum and List modules already offer a function that takes a function you define and a list and returns what you need.

Testing Lists

Sometimes you just want to know if all the values — or any of the values — in a list meet specific criteria. Are they all of a specific type, or do they have a value that meets certain criteria?

The Enum.all?/2 and Enum.any?/2 functions let you test a list against rules you specify in a function. If your function returns true for all of the list values, both of these functions will return true. Enum.any?/2 will also return true if one or more values in the list results in your function returning true. Both will return false if your function consistently returns false.

NOTE

Enum.all?/2 and Enum.any?/2 don’t necessarily evaluate the entire list; as soon as they hit a value that provides a definitive answer, they’ll stop and return that answer.

iex(13)> is_int = fn(value) -> is_integer(value) end

#Function<erl_eval.6.17052888>

iex(14)> Enum.all?(list, is_int)

true

iex(15)> Enum.any?(list, is_int)

true

iex(16)> compare = &(&1 > 10)

#Function<6.106461118/1 in :erl_eval.expr/5>

iex(17)> Enum.all?(list, compare)

false

iex(18)> Enum.any?(list, compare)

true

You can think of Enum.all?/2 as an and function applied to lists because it stops processing as soon as it encounters a false result. Similarly, Enum.any?/2 is like or, in this case stopping as soon as it finds a true result. As long as you need only to test individual values within lists, these two higher order functions can save you writing a lot of recursive code.

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 Enum.partition/2 function returns a tuple containing two lists. The first list contains the items from the original list that met the conditions specified in the function you provided, while the second list contains 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 split a list into a list of items greater than 10 and a list of items less than or equal to 10 easily:

iex(19)> Enum.partition(list, compare)

{[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 Enum.take_while/2 and Enum.drop_while/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 in this chapter:

iex(20)> test = &(&1 < 4)

#Function<6.106461118/1 in :erl_eval.expr/5>

iex(21)> Enum.drop_while([1,2,4,8,4,2,1], test)

[4, 8, 4, 2, 1]

iex(22)> Enum.take_while([1,2,4,8,4,2,1], test)

[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 Enum.drop_while/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 Enum.take_while/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. Elixir’s List.foldl/3 and List.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. The first argument is the current value in the list traversal, and the second argument is an 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:

iex(23)> divide = fn(value, accumulator) -> value / accumulator end

#Function<12.106461118/2 in :erl_eval.expr/5>

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

Folding has one other key twist. You can choose whether you want the function to traverse the list from head to tail, with List.foldl/3, or from tail to head, with List.foldr/3. If order doesn’t change the result, you should go with List.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 listof [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. They don’t produce those results, however:

iex(24)> divide = fn(value, accumulator) -> value / accumulator end

#Function<12.106461118/2 in :erl_eval.expr/5>

iex(25)> 1/2/4/8/16/32

3.0517578125e-5

iex(26)> List.foldl(list, 1, divide)

8.0

iex(24)> 32/16/8/4/2/1

0.03125

iex(25)> List.foldr(list, 1, divide)

0.125

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

Table 8-1. Recursive division of a list forward with List.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 8-2. Recursive division of a list backward with List.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 List.foldl is the same as 32/(16/(8/(4/(2/(1/1))))), while the result of the List.foldr is the same as 1/(2/(4/(8/(16/(32/1))))). The parentheses in those 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.