Extracted from:

Programming Elixir ≥ 1.6
Functional |> Concurrent |> Pragmatic |> Fun

This PDF file contains pages extracted from Programming Elixir ≥ 1.6, publishedby the Pragmatic Bookshelf. For more information or to purchase a paperback or
PDF copy, please visit http://www.pragprog.com.
Note: This extract contains some colored text (particularly in code listing). Thisis available only in online versions of the books. The printed versions are black
and white. Pagination might vary between the online and printed versions; thecontent is otherwise identical.
Copyright © 2018 The Pragmatic Programmers, LLC.
All rights reserved.
No part of this publication may be reproduced, stored in a retrieval system, or transmitted,
in any form, or by any means, electronic, mechanical, photocopying, recording, or otherwise,
without the prior consent of the publisher.

The Pragmatic Bookshelf
Raleigh, North Carolina

Programming Elixir ≥ 1.6
Functional |> Concurrent |> Pragmatic |> Fun

Dave Thomas

The Pragmatic Bookshelf
Raleigh, North Carolina

Many of the designations used by manufacturers and sellers to distinguish their products
are claimed as trademarks. Where those designations appear in this book, and The Pragmatic
Programmers, LLC was aware of a trademark claim, the designations have been printed ininitial capital letters or in all capitals. The Pragmatic Starter Kit, The Pragmatic Programmer,
Pragmatic Programming, Pragmatic Bookshelf, PragProg and the linking g device are trademarks of The Pragmatic Programmers, LLC.
Every precaution was taken in the preparation of this book. However, the publisher assumes
no responsibility for errors or omissions, or for damages that may result from the use of
information (including program listings) contained herein.
Our Pragmatic books, screencasts, and audio books can help you and your team create
better software and have more fun. Visit us at https://pragprog.com.
The team that produced this book includes:
Publisher: Andy Hunt
VP of Operations: Janet Furlow
Managing Editor: Brian MacDonald
Supervising Editor: Jacquelyn Carter
Copy Editor: Candace Cunningham
Indexing: Potomac Indexing, LLC
Layout: Gilson Graphics
For sales, volume licensing, and support, please contact support@pragprog.com.
For international rights, please contact rights@pragprog.com.

Copyright © 2018 The Pragmatic Programmers, LLC.
All rights reserved.
No part of this publication may be reproduced, stored in a retrieval system, or transmitted,
in any form, or by any means, electronic, mechanical, photocopying, recording, or otherwise,
without the prior consent of the publisher.
Printed in the United States of America.
ISBN-13: 978-1-68050-299-2
Encoded using the finest acid-free high-entropy binary digits.
Book version: P1.0—May 2018

In this chapter, you'll see:
• The recursive structure of lists• Traversing and building lists• Accumulators• Implementing map and reduce

CHAPTER 7

Lists and Recursion
When we program with lists in conventional languages, we treat them asthings to be iterated—it seems natural to loop over them. So why do we havea chapter on lists and recursion? Because if you look at the problem in theright way, recursion is a perfect tool for processing lists.

Heads and Tails
Earlier we said a list may either be empty or consist of a head and a tail. The
head contains a value and the tail is itself a list. This is a recursive definition.
We’ll represent the empty list like this: [ ].
Let’s imagine we could represent the split between the head and the tail using
a pipe character: |. The single-element list we normally write as [ 3 ] can be
written as the value 3 joined to the empty list:[ 3 | [ ] ](I’ve highlighted the inner list.)
When we see the pipe character, we say that what’s on the left is the head ofa list and what’s on the right is the tail.
Let’s look at the list [2, 3]. The head is 2, and the tail is the single-element list
containing 3. And we know what that list looks like—it is our previous
example. So we could write [2,3] as[ 2|[ 3 | [] ] ]At this point, part of your brain is telling you to go read today’s XKCD—thislist stuff can’t be useful. Ignore that small voice, just for a second. We’re about
to do something magical. But before we do, let’s add one more term, making• Click HERE to purchase this book now. discussChapter 7. Lists and Recursion • 4

our list [1, 2, 3]. This is the head 1 followed by the list [2, 3], which is what wederived a moment ago:
[ 1 | [ 2|

[ 3 | [] ] ]This is valid Elixir syntax. Type it into IEx.
iex> [ 1 |[1, 2, 3][ 2|[ 3 | [] ] ] ]And here’s the magic. When we discussed pattern matching, we said thepattern could be a list, and the values in that list would be assigned from theright-hand side.
iex> [a, b, c ] = [ 1, 2, 3 ][1, 2, 3]iex> a1iex> b2iex> c3

We can also use the pipe character in the pattern. What’s to the left of itmatches the head value of the list, and what’s to the right matches the tail.
iex> [ head | tail ] = [ 1, 2, 3 ][1, 2, 3]iex> head
1iex> tail[2, 3]

Using Head and Tail to Process a List
Now we can split a list into its head and its tail, and we can construct a list
from a value and a list, which become the head and tail of that new list.
So why talk about lists after we talk about modules and functions? Because
lists and recursive functions go together like fish and chips. Let’s look at
finding the length of a list.
• The length of an empty list is 0.
• The length of a list is 1 plus the length of that list’s tail.

• Click HERE to purchase this book now. discuss

Using Head and Tail to Process a List • 5

How IEx Displays Lists
In Chapter 11, Strings and Binaries, on page ?, you’ll see that Elixir has two representations for strings. One is the familiar sequence of characters in consecutive
memory locations. Literals written with double quotes use this form.
The second form, using single quotes, represents a string as a list of integer codepoints.
So the string 'cat' is the three codepoints: 99, 97, and 116.
This is a headache for IEx. When it sees a list like [99,97,116] it doesn’t know if it is
supposed to be the string 'cat' or a list of three numbers. So it uses a heuristic. If all
the values in a list represent printable characters, it displays the list as a string;otherwise it displays a list of integers.
iex≻ [99, 97, 116]'cat'iex≻ [99, 97, 116, 0][99, 97, 116, 0]# '0' is nonprintable

In Chapter 11, Strings and Binaries, on page ?, we’ll cover how to bypass thisbehavior. In the meantime, don’t be surprised if a string pops up when you were
expecting a list.

Writing the list-length algorithm in Elixir is easy:
lists/mylist.exs
defmodule MyList do
def len([]), do: 0
def len([head|tail]), do: 1 + len(tail)end

The only tricky part is the definition of the function’s second variant:def len([ head | tail ]) ...

This is a pattern match for any nonempty list. When it does match, the variable
head will hold the value of the first element of the list, and tail will hold therest of the list. (And remember that every list is terminated by an empty list,
so the tail can be [].)
Let’s see this at work with the list [11, 12, 13, 14, 15]. At each step, we takeoff the head and add 1 to the length of the tail:len([11,12,13,14,15])= 1 + len([12,13,14,15])= 1 + 1 + len([13,14,15])= 1 + 1 + 1 + len([14,15])= 1 + 1 + 1 + 1 + len([15])= 1 + 1 + 1 + 1 + 1 + len([])= 1 + 1 + 1 + 1 + 1 + 0= 5• Click HERE to purchase this book now. discussChapter 7. Lists and Recursion • 6Let’s try our code to see if theory works in practice:iex> c "mylist.exs"...mylist.exs:3: variable head is unused[MyList]iex> MyList.len([])
0iex> MyList.len([11,12,13,14,15])
5

It works, but we have a compilation warning—we never used the variable headin the body of our function. We can fix that, and make our code more explicit,
using the special variable _ (underscore), which acts as a placeholder. We canalso use an underscore in front of any variable name to turn off the warning
if that variable isn’t used. I sometimes like to do this to document the unused
parameter.
lists/mylist1.exs
defmodule MyList do
def len([]),
do: 0
def len([ _head | tail ]), do: 1 + len(tail)end

When we compile, the warning is gone. (However, if you compile the second
version of MyList, you may get a warning about “redefining module MyList.” Thisis just Elixir being cautious.)iex> c "mylist1.exs"[MyList]iex> MyList.len([1,2,3,4,5])
5iex> MyList.len(["cat", "dog"])
2

Using Head and Tail to Build a List
Let’s get more ambitious. Let’s write a function that takes a list of numbers
and returns a new list containing the square of each. We don’t show it, butthese definitions are also inside the MyList module.
lists/mylist1.exs
def square([]),
do: []
def square([ head | tail ]), do: [ head*head | square(tail) ]There’s a lot going on here. First, look at the parameter patterns for the two
definitions of square. The first matches an empty list and the second matches
all other lists.

• Click HERE to purchase this book now. discuss

Creating a Map Function • 7Second, look at the body of the second definition:
def square([ head | tail ]), do: [ head*head | square(tail) ]When we match a nonempty list, we return a new list whose head is thesquare of the original list’s head and whose tail is a list of squares of the tail.
This is the recursive step.
Let’s try it:iex> c "mylist1.exs"[MyList]iex> MyList.square [][]iex> MyList.square [4,5,6][16, 25, 36]# this calls the 1st definition# and this calls the 2nd

Let’s do something similar—a function that adds 1 to every element in the list:
lists/mylist1.exs
def add_1([]),
do: []
def add_1([ head | tail ]), do: [ head+1 | add_1(tail) ]And call it:iex> c "mylist1.exs"[MyList]iex> MyList.add_1 [1000][1001]
iex> MyList.add_1 [4,6,8][5, 7, 9]Creating a Map Function
With both square and add_1, all the work is done in the second function definition. And that definition looks about the same for each—it returns a new list
whose head is the result of either squaring or incrementing the head of its
argument and whose tail is the result of calling itself recursively on the tailof the argument. Let’s generalize this. We’ll define a function called map thattakes a list and a function and returns a new list containing the result ofapplying that function to each element in the original.
lists/mylist1.exs
def map([], _func),
do: []
def map([ head | tail ], func), do: [ func.(head) | map(tail, func) ]The map function is pretty much identical to the square and add_1 functions. It
returns an empty list if passed an empty list; otherwise it returns a list where
the head is the result of calling the passed-in function and the tail is arecursive call to itself. Note that in the case of an empty list, we use _func as• Click HERE to purchase this book now. discussChapter 7. Lists and Recursion • 8

the second parameter. The underscore prevents Elixir from warning us about
an unused variable.
To call this function, pass in a list and a function (defined using fn):iex> c "mylist1.exs"[MyList]iex> MyList.map [1,2,3,4], fn (n) -> n*n end[1, 4, 9, 16]

A function is just a built-in type, defined between fn and the end. Here we passa function as the second argument (func) to map. This is invoked inside map
using func.(head), which squares the value in head, using the result to build the
new list.
We can call map with a different function:iex> MyList.map [1,2,3,4], fn (n) -> n+1 end[2, 3, 4, 5]

And another:iex> MyList.map [1,2,3,4], fn (n) -> n > 2 end[false, false, true, true]

And we can do the same using the & shortcut notation:iex> MyList.map [1,2,3,4], &(&1 + 1)
[2, 3, 4, 5]iex> MyList.map [1,2,3,4], &(&1 > 2)
[false, false, true, true]

Reducing a List to a Single Value
The map/2 function we just wrote abstracts the idea of applying a function toeach element of a list independently.
But what if we want to apply that function across the elements? How could
we create an abstraction that would let us sum a list, or find the product of
its elements, or find the largest element?
The sum function reduces a collection to a single value. Other functions needto do something similar—return the greatest/least value, the product of theelements, a string containing a concatenation of elements, and so on. How
can we write a general-purpose function that reduces a collection to a value?
We know it has to take a collection. We also know we need to pass in some
initial value (just like our sum/1 function passed a 0 as an initial value to its• Click HERE to purchase this book now. discuss

Reducing a List to a Single Value • 9helper). Additionally, we need to pass in a function that takes the current
value of the reduction along with the next element of the collection, andreturns the next value of the reduction. So, it looks like our reduce function
will be called with three arguments:
reduce(collection, initial_value, fun)Now let’s think about the recursive design:• reduce([ ], value, _fun) → value• reduce([ head | tail ], value, fun) → reduce(tail, fun.(head, value), fun)reduce applies the function to the list’s head and the current value, and passes

the result as the new current value when reducing the list’s tail.
Here’s our code for reduce. See how closely it follows the design:lists/reduce.exs
defmodule MyList do
def reduce([], value, _) do
value
end
def reduce([head | tail], value, func) do
reduce(tail, func.(head, value), func)
end
end

And, again, we can use the shorthand notation to pass in the function:iex> c "reduce.exs"[MyList]iex> MyList.reduce([1,2,3,4,5], 0, &(&1 + &2))
15iex> MyList.reduce([1,2,3,4,5], 1, &(&1 * &2))
120

Your Turn➤ Exercise: ListsAndRecursion-1
Write a mapsum function that takes a list and a function. It applies thefunction to each element of the list and then sums the result, soiex> MyList.mapsum [1, 2, 3], &(&1 * &1)
14➤ Exercise: ListsAndRecursion-2
Write a max(list) that returns the element with the maximum value in thelist. (This is slightly trickier than it sounds.)• Click HERE to purchase this book now. discussChapter 7. Lists and Recursion • 10

➤ Exercise: ListsAndRecursion-3

An Elixir single-quoted string is actually a list of individual charactercodes. Write a caesar(list, n) function that adds n to each list element,
wrapping if the addition results in a character greater than z.
iex> MyList.caesar('ryvkve', 13)?????? :)More Complex List Patterns
Not every list problem can be easily solved by processing one element at atime. Fortunately, the join operator, |, supports multiple values to its left.
Thus, you could writeiex> [ 1, 2, 3 | [ 4, 5, 6 ]][1, 2, 3, 4, 5, 6]

The same thing works in patterns, so you can match multiple individual elements as the head. For example, this program swaps pairs of values in a list:
lists/swap.exs
defmodule Swapper dodef swap([]), do: []def swap([ a, b | tail ]), do: [ b, a | swap(tail) ]def swap([_]), do: raise "Can't swap a list with an odd number of elements"
end

We can play with it in IEx:
iex> c "swap.exs"[Swapper]iex> Swapper.swap [1,2,3,4,5,6][2, 1, 4, 3, 6, 5]iex> Swapper.swap [1,2,3,4,5,6,7]** (RuntimeError) Can't swap a list with an odd number of elements

The third definition of swap matches a list with a single element. This will
happen if we get to the end of the recursion and have only one element left.
Given that we take two values off the list on each cycle, the initial list musthave had an odd number of elements.

Lists of Lists
Let’s imagine we had recorded temperatures and rainfall at a number ofweather stations. Each reading looks like this:[ timestamp, location_id, temperature, rainfall ]• Click HERE to purchase this book now. discussMore Complex List Patterns • 11

Our code is passed a list containing a number of these readings, and we want
to report on the conditions for one particular location, number 27.
lists/weather.exs
defmodule WeatherHistory do
def for_location_27([]), do: []def for_location_27([ [time, 27, temp, rain ] | tail]) do[ [time, 27, temp, rain] | for_location_27(tail) ]end
def for_location_27([ _ | tail]), do: for_location_27(tail)endThis is a standard recurse until the list is empty stanza. But look at ourfunction definition’s second clause. Where we’d normally match into a variable
called head, here the pattern isfor_location_27([ [ time, 27, temp, rain ] | tail])

For this to match, the head of the list must itself be a four-element list, andthe second element of this sublist must be 27. This function will execute only
for entries from the desired location. But when we do this kind of filtering,
we also have to remember to deal with the case when our function doesn’tmatch. That’s what the third line does. We could have written
for_location_27([ [ time, _, temp, rain ] | tail])but in reality we don’t care what is in the head at this point.
In the same module we define some simple test data:lists/weather.exs
def test_data do[[1366225622, 26, 15, 0.125],[1366225622, 27, 15, 0.45],[1366225622, 28, 21, 0.25],[1366229222, 26, 19, 0.081],[1366229222, 27, 17, 0.468],[1366229222, 28, 15, 0.60],[1366232822, 26, 22, 0.095],[1366232822, 27, 21, 0.05],[1366232822, 28, 24, 0.03],[1366236422, 26, 17, 0.025]]
end

We can use that to play with our function in IEx. To make this easier, I’musing the import function. This adds the functions in WeatherHistory to our local• Click HERE to purchase this book now. discussChapter 7. Lists and Recursion • 12

name scope. After calling import we don’t have to put the module name in frontof every function call.
iex> c "weather.exs"[WeatherHistory]iex> import WeatherHistory
WeatherHistoryiex> for_location_27(test_data)[[1366225622, 27, 15, 0.45], [1366229222, 27, 17, 0.468],[1366232822, 27, 21, 0.05]]

Our function is specific to a particular location, which is pretty limiting. We’d
like to be able to pass in the location as a parameter. We can use patternmatching for this.
lists/weather2.exs
defmodule WeatherHistory do
def for_location([], _target_loc), do: []➤def for_location([ [time, target_loc, temp, rain ] | tail], target_loc) do[ [time, target_loc, temp, rain] | for_location(tail, target_loc) ]end
def for_location([ _ | tail], target_loc), do: for_location(tail, target_loc)end

Now the second function fires only when the location extracted from the list
head equals the target location passed as a parameter.
But we can improve on this. Our filter doesn’t care about the other three fields
in the head—it just needs the location. But we do need the value of the headitself to create the output list. Fortunately, Elixir pattern matching is recursive
and we can match patterns inside patterns.
lists/weather3.exs
defmodule WeatherHistory do
def for_location([], _target_loc), do: []➤def for_location([ head = [_, target_loc, _, _ ] | tail], target_loc) do[ head | for_location(tail, target_loc) ]end
def for_location([ _ | tail], target_loc), do: for_location(tail, target_loc)
end

The key change here is this line:
def for_location([ head = [_, target_loc, _, _ ] | tail], target_loc)• Click HERE to purchase this book now. discuss

The List Module in Action • 13

Compare that with the previous version:
def for_location([ [ time, target_loc, temp, rain ] | tail], target_loc)

In the new version, we use placeholders for the fields we don’t care about.
But we also match the entire four-element array into the parameter head. It’s
as if we said, “Match the head of the list where the second element is matchedto target_loc and then match that whole head with the variable head.” We’ve
extracted an individual component of the sublist as well as the entire sublist.
In the original body of for_location, we generated our result list using the individual fields:
def for_location([ [ time, target_loc, temp, rain ] | tail], target_loc)[ [ time, target_loc, temp, rain ] | for_location(tail, target_loc) ]end

In the new version, we can just use the head, making it a lot clearer:
def for_location([ head = [_, target_loc, _, _ ] | tail], target_loc)[ head | for_location(tail, target_loc) ]enddoYour Turn➤ Exercise: ListsAndRecursion-4
Write a function MyList.span(from, to) that returns a list of the numbers fromfrom up to to.

The List Module in Action
The List module provides a set of functions that operate on lists.
## Concatenate lists#iex> [1,2,3] ++ [4,5,6][1, 2, 3, 4, 5, 6]## Flatten#iex> List.flatten([[[1], 2], [[[3]]]])[1, 2, 3]## Folding (like reduce, but can choose direction)#iex> List.foldl([1,2,3], "", fn value, acc -> "#{value}(#{acc})" end)
"3(2(1()))"
iex> List.foldr([1,2,3], "", fn value, acc -> "#{value}(#{acc})" end)
"1(2(3()))"• Click HERE to purchase this book now. discussChapter 7. Lists and Recursion • 14#
# Updating in the middle (not a cheap operation)#iex> list = [ 1, 2, 3 ][ 1, 2, 3 ]iex> List.replace_at(list, 2, "buckle my shoe")[1, 2, "buckle my shoe"]## Accessing tuples within lists#iex> kw = [{:name, "Dave"}, {:likes, "Programming"}, {:where, "Dallas", "TX"}][{:name, "Dave"}, {:likes, "Programming"}, {:where, "Dallas", "TX"}]
iex> List.keyfind(kw, "Dallas", 1){:where, "Dallas", "TX"}
iex> List.keyfind(kw, "TX", 2){:where, "Dallas", "TX"}
iex> List.keyfind(kw, "TX", 1)niliex> List.keyfind(kw, "TX", 1, "No city called TX")
"No city called TX"
iex> kw = List.keydelete(kw, "TX", 2)[name: "Dave", likes: "Programming"]iex> kw = List.keyreplace(kw, :name, 0, {:first_name, "Dave"})[first_name: "Dave", likes: "Programming"]

Get Friendly with Lists
Lists are the natural data structure to use when you have a stream of values
to handle. You’ll use them to parse data, handle collections of values, andrecord the results of a series of function calls. It’s worth spending a while
getting comfortable with them.
Next we’ll look at the various dictionary types, including maps. These let us
organize data into collections of key/value pairs.

• Click HERE to purchase this book now. discuss