6.3 Day 2: Changing Forms

In this section, you’re going to begin to appreciate Agent Smith’s power. The agents in The Matrix have super-human strength. They can dodge bullets and punch through concrete. Functional languages are at a higher level of abstraction than object-oriented languages. Though they are more difficult to understand, you can express bigger ideas with less code.

Agent Smith can also take the form of any other person in the matrix. That’s an important capability in a functional language. You’re going to learn to apply functions to lists that can quickly shape the list into exactly what you need. Do you want to turn a shopping list into a list of prices? What about turning a list of URLs into tuples containing content and URLs? These are the problems that functional languages simply devour.

Control Structures

Let’s start with a few mundane pieces of Erlang: basic control structures. You’ll notice that this section of the book is much shorter than Scala’s. Often, you’ll see programs with plenty of case statements, because they will interpret which message to process when you’re writing concurrent applications. ifs are less prevalent.

Case

Let’s start with a case. Most of the time, you think of a pattern match in the context of function invocation. Think of this control structure as a pattern match that you can use anywhere. For example, say you have a variable called Animal. You want to conditionally execute the code based on the value:

So, in this example, the string matched the first clause and returned the atom underdog. As with Prolog, you can use the underscore (_) to match anything, like this (note: Animal is still "dog"):

The animal was not "elephant", so it matched the last clause. You can also use underscores in any other Erlang match. I’d like to point out a basic syntactic wart here. Notice that all case clauses but the last end in a semicolon. That means if you want to edit your statement to reorder your clauses, you must adjust the syntax accordingly, though it would have been pretty easy to allow an optional semicolon after the last clause. Sure, the syntax is logical: the semicolon is a separator for the case clauses. It’s just not very convenient. Agent Smith just kicked sand all over my kid nephew, and I think I heard him laugh. He has to brush up on those public relations if he wants to win Agent of the Month. Let’s move on to the basic if.

If

The case statement uses pattern matching, and the if statement uses guards. In Erlang, a guard is a condition that must be satisfied for a match to succeed. Later, we’ll introduce guards on pattern matches, but the most basic form of a guard is in an if statement. You start with the if keyword and then follow it with several guard -> expression clauses. Here’s the idea:

What happens if there is no match?

Unlike Ruby or Io, one of the statements must be true, because if is a function. Each case must return a value. If you truly want an else, make the last guard true, like this:

That’s really it for control structures. You’re going to get much more out of higher-order functions and pattern matching to accomplish your goals, so let’s leave these control statements behind and dive in deeper into functional programming. We’re going to work with higher-order functions and use them to process lists. We’ll learn to solve progressively more complex problems with functions.

Anonymous Functions

As you recall, higher-order functions either return functions or take functions as arguments. Ruby used code blocks for higher-order functions, with special attention to passing code blocks to iterate over lists. In Erlang, you can assign arbitrary functions to variables and pass them around like any other data types.

You’ve seen some of these concepts before, but we’re going to lay some of the foundations in Erlang and then build some higher-level abstractions. It all starts with anonymous functions. Here’s how you’d assign a function to a variable:

Line 16 uses a new keyword called fun. That keyword defines an anonymous function. In this case, the function takes a single argument called I and returns the negation, -I. We assign that anonymous function to Negate. To be clear, Negate is not the value returned by the function. It actually is the function.

Two significant ideas are happening here. First, we’re assigning a function to a variable. This concept allows us to pass around behaviors just as we would any other data. Second, we can easily invoke the underlying function, just by specifying an argument list. Notice the dynamic typing. We don’t have to concern ourselves with the return type of the function, so we’re protected from some of the invasive syntax you see with, say, Scala. The downside is that these functions can fail. I’ll show you some of the ways Erlang lets you compensate for that limitation.

Let’s use some of this newfound power. We’ll use anonymous functions to handle the each, map, and inject concepts that you initially met in Ruby.

Lists and Higher-Order Functions

As you’ve seen, lists and tuples are the heart and soul of functional programming. It’s no accident that the first functional language started with lists, and everything built on that foundation. In this section, you’ll start to apply higher-order functions to lists.

Applying Functions to Lists

By now, the idea should be pretty clear to you. We’re going to use functions to help us manage lists. Some, like ForEach, will iterate over lists. Others, like filter or map, will return lists, either filtered or mapped onto other functions. Still more, like foldl or foldr, will process lists, rolling up results along the way, like Ruby’s inject or Scala’s FoldLeft. Open a fresh console, define a list or two, and get cracking.

First, we’ll handle basic iteration. The lists:foreach method takes a function and a list. The function can be anonymous, like this:

The syntax of line 2 is a little tricky, so we’ll walk through it. We start by invoking a function called lists:foreach. The first argument is the anonymous function fun(Number) -> io:format("~p~n", [Number]) end. That function has one argument and prints the value of whatever you pass in with the io:format function.[16] Finally, the second argument to foreach is Numbers, the list we defined on line 1. We could simplify this by defining the function in a separate line:

Now, Print is bound to the io:format function. We can simplify the code like this:

That’s basic iteration. Let’s move on to a function that maps. The map function works like Ruby’s collect, passing each value of a list to a function and building a list with the results. Like lists:foreach, lists:map takes a function and a list. Let’s use map with our list of numbers, increasing each value by one:

That was easy. This time, our anonymous function was fun(X) -> X + 1 end. It increased each value by one, and lists:map built a list with the results.

Defining map is really easy:

Simple enough. The map of F over a list is F(head) plus map(F, tail). We’ll look at a more concise version when we look at list comprehensions.

Moving on, we can filter lists with a boolean. Let’s define an anonymous function and assign it to Small:

Now, we can take that function and use it to filter the list. The function lists:filter will build a list of all the elements that satisfy Small or those less than three:

You can see that Erlang is making it very easy to code in this way. Alternatively, we can use the Small function to test lists with all and any. lists:all returns true only if all the items in a list satisfy the filter, like this:

Alternatively, lists:any returns true if any of the items in the list satisfies the filter:

Let’s see what happens with empty lists:

As you’d expect, all returns true (meaning all of the items present in the list satisfy the filter, though there are no items in the list), and any returns false (meaning no element in the empty list satisfies the filter). In these cases, it doesn’t matter what the filter is.

You can also make a list of all the elements at the head of a list that match a filter or discard all the items at the front of a list that satisfy the filter:

These tests are useful to do things such as process or discard headers of messages. Let’s finish this whirlwind with foldl and foldr.

foldl

I realize that you’ve seen these concepts before. If you’re Neo and you’ve mastered this part of the matrix, read the basic example and fight on. For some, foldl takes a little while to master, so I’m going to teach it a few different ways.

Remember, these functions are useful for rolling up the results of a function across a list. One of the arguments serves as an accumulator, and the other represents each item. lists:foldl takes a function, the initial value of the accumulator, and the list:

To simplify a little bit, let’s break that anonymous function into a variable and make our intentions clear with better variable names:

Ah, that’s better. So, we are going to keep a running sum. We’re going to pass the SumSoFar and each number from Numbers into a function called Adder, one at a time. Each time, the sum will get bigger, and the lists:foldl function will remember the running total and pass it back into Adder. Ultimately, the function will return the last running sum.

So far, all you’ve seen are functions that work on existing lists. I haven’t shown you how to build a list a piece at a time. Let’s shift gears toward list building.

Advanced List Concepts

All of the list concepts I’ve introduced are extensions of the ideas you’ve seen in the other languages. But we can get a little more sophisticated. We haven’t yet talked about building lists, and we’ve only used pretty basic abstractions with simple code blocks.

List Construction

On the surface, it may seem difficult to build lists without mutable state. With Ruby or Io, you would continually add items to a list. There’s another way. You can return a new list with the list item added. Often, you’ll add items to a list headfirst. You’ll use the [H|T] construct but in the right side of a match instead. This program uses the list construction technique to double each item of a list:

The module exports one function, called double_all. That function has two distinct clauses. The first says that double_all for an empty list returns an empty list. This rule stops the recursion.

The second rule uses the [H|T] construct, but in the predicate of the match as well as the function definition. You’ve already seen something like [First|Rest] on the left side of a match. It lets you break a list into the first element and the rest of the list.

Using it on the right side does list construction instead of destruction. In this case, [First + First|double_all(Rest)] means build a list with First + First as the first element and double_all(Rest) as the rest of the list.

You can compile and run the program as usual:

Let’s take another look at list construction with | from the console:

There should be no surprises in there. The second argument must be a list. Whatever is on the left side will be added as the first element of a new list.

Let’s look at a more advanced Erlang concept, called list comprehensions. They combine some of the concepts we have been talking about so far.

List Comprehensions

One of the most important functions in just about any functional language is map. With it, your lists can mutate, just like The Matrix enemies. Since the feature is so important, Erlang provides a more powerful form that is concise and allows you to do multiple transformations at once.

Let’s start things off with a fresh console. We’ll do a map the old-fashioned way:

We have a list of numbers called Fibs and an anonymous function called Double that will double whatever you pass in. Then, we called lists:map to call Double on each element and build a list out of the result. That’s a great tool, but it’s used often enough that Erlang provides a much more concise way to provide the same syntax. The construct is called a list comprehension. Here’s the equivalent to what we just typed, with a list comprehension:

In English, we’re saying compute the Double of X for each X taken from the list called Fibs. If you’d prefer, we can cut out the middleman:

The concept is the same. We’re computing X * 2 for each X taken from the list called [1, 1, 2, 3, 5]. This feature is a bit more than syntactic sugar. Let’s build some more sophisticated list comprehensions. We will start with a more concise definition of map:

In English, the map of some function F over some list L is the collection of F(X) for each X that is a member of L. Now, let’s use a list comprehension to work with a catalog having a product, quantity, and price:

Say that I need to add a tax that is eight cents on the dollar. I can add a simple list comprehension to roll up the new cart with tax with a single list comprehension, like this:

All the earlier Erlang concepts you’ve learned still apply: there’s pattern matching going on here! So in English, we’re returning a list of tuples having a Product, Price, Quantity, and tax (Price * Quantity * 0.08), for each tuple of {Product, Quantity, Price} taken from the list called Cart. This code is absolutely beautiful to me. This syntax allows me to change the form of my list, literally on demand.

As another example, say I have a catalog and I want to provide a similar catalog to my preferred customers with a 50 percent discount. The catalog could look something like this. I’ll just take the catalog from the cart, ignoring quantity:

In English, give me tuples with Product and Price for each tuple of Product, and Price (ignoring the second attribute) taken from the Cart list. Now, I can provide my discount:

It’s concise, readable, and powerful. It’s a beautiful abstraction.

In truth, I’ve showed you only part of the power of a list comprehension. The full form can be even more powerful:

• A list comprehension takes the form of [Expression || Clause1, Clause2, ..., ClauseN].

• List comprehensions can have an arbitrary number of clauses.

• The clauses can be generators or filters.

• A filter can be a boolean expression or a function returning a boolean.

• A generator, of the form Match <-List, matches a pattern on the left to the elements of a list on the right.

Really, it’s not too hard. Generators add, and filters remove. There’s a lot of Prolog influence here. Generators determine the possible values, and filters trim the list down to the specified conditions. Here are a couple of examples:

In English, return X, where X is taken from [1, 2, 3, 4], X is less than four, and X is greater than one. You can also have multiple generators:

This one makes a tuple {X, Y} by combining X values from [1, 2, 3, 4] that are less than 3 with Y values from [5, 6]. You wind up with two X values and two Y values, and Erlang computes a Cartesian product.

And that’s the whole story. You’ve learned to use Erlang to do sequential programming. Let’s take a break to wrap up and put this stuff into practice.

What We Learned in Day 2

Admittedly, we didn’t go into deep detail about Erlang expressions or the library, but you are now armed with enough information to write functional programs. You started the day with some mundane control structures, but we picked up the pace quickly.

Next, we covered higher-order functions. You used higher-order functions within lists to iterate through lists, filter them, and modify them. You also learned to use foldl to roll up results, just as you did with Scala.

Finally, we moved on to advanced list concepts. We used [H|T] on the left side of a match to deconstruct a list into the first element of the list and the rest. We used [H|T] on the right side of a match, or solo, to construct lists, headfirst. We then moved on to list comprehensions, an elegant and powerful abstraction that can quickly transform lists with generators and filters.

The syntax was a mixed bag. You could cruise through the higher concepts with very little typing, thanks to Erlang’s dynamic typing strategy. Still, there were some awkward moments, especially with the semicolons after the various pieces of case and if clauses.

In the next section, we’ll learn what all of the fuss was about. We’ll tackle concurrency.

Day 2 Self-Study

Do:

• Consider a list of keyword-value tuples, such as [{erlang, "a functional language"}, {ruby, "an OO language"}]. Write a function that accepts the list and a keyword and returns the associated value for the keyword.

• Consider a shopping list that looks like [{item quantity price}, ...]. Write a list comprehension that builds a list of items of the form [{item total_price}, ...], where total_price is quantity times price.

Bonus problem:

• Write a program that reads a tic-tac-toe board presented as a list or a tuple of size nine. Return the winner (x or o) if a winner has been determined, cat if there are no more possible moves, or no_winner if no player has won yet.