Lecture 2: Lists

Lists are an important and useful data structure in functional programming. Indeed, the name of the first widely used functional programming language, Lisp, is a portmanteau of “List Processing.”

In Haskell, a list is a sequence of objects of the same type. Often, we'll describe a list by an explicit enumeration of its elements, e.g.,

[1,2,3,4,5]

This is a nice notation, but it is important to understand that it is syntactic sugar, i.e., a clear and concise notation that reflects a commonly used pattern. For all it's considerable merits, this notation obscures the essential fact that there are only two kinds of lists, empty lists ([]), and lists that contain at least one element, and so are constructed using cons, a.k.a., (:). More pedantically, this list could be written as

1:2:3:4:5:[]

Note that (:) associates to the right, so this is really (and even more pedantically)

1 : (2 : (3 : (4 : (5 : []))))

Now, if you have any syntactic taste at all, you'll prefer the first form, [1,2,3,4,5] to the second and especially the third form. But this misses an important point—it is one thing to have a concise notation for lists, but if you want to write code that manipulates list structure, you have to understand how they're actually constructed.

Defining List Functions By Recursion

Let's start by implementing the standard length function:

length [] = 0 length (c:cs) = 1 + length cs

This is a natural recursion on list structure, i.e.,

The length simply counts the number of elements in a particular list. Let's take this definition apart piece by piece

length [] = ... length (c:cs) = ...

The parentheses around the cons (:) in the second line are not optional. Remember that function application binds more tightly than infix operations, and so, without the parentheses, Haskell would interpret length c:cs as (length c):cs, and interpret your equation as an attempt to define (:)!

Finally, an experienced Haskell programmer would make one further change. Portions of a pattern that we don't need can be matched using just an underscore _, thus,

length [] = 0 length (_:cs) = 1 + length cs

This idiom allows us to focus on the parts of the pattern that are important in reducing an expression.

We can use the same approach in defining the sum of the elements of a list:

sum [] = 0 sum (x:xs) = x + sum xs

Let's consider a slightly different problem—summing the squares of the elements of a list. We're going to consider this simple problem from several angles.

A first approach would be a direct implementation, like this:

sumSquares [] = 0 sumSquares (x:xs) = x^2 + sumSquares xs

You will soon be able to write definitions like this pretty quickly, e.g., a sum of cubes function might be written like this:

sumCubes [] = 0 sumCubes (x:xs) = x^3 + sumCubes xs

Higher Order List Functions

As natural as this is, and as comfortable as it becomes, experienced programmers want to avoid writing the same code over and over again—so this will inspire them to find appropriate abstractions that capture the relevant commonalities, and then to express the particular versions as special cases.

For example, we might abstract away that we're summing functions applied to elements of a list. This gives rise to a definitions like this:

sumf f [] = 0 sumf f (c:cs) = f c + sumf f cs square x = x^2 cube x = x^3 sumSquares xs = sumf square xs sumCubes xs = sumf cubes xs

Although the second implementation of sumSquares is a bit longer (four lines vs. two), this second version is to be preferred because it achieves a clean factoring of the problem into a recursive summing part, and a function computing part, whereas in the first version, these aspects are intertwined. Moreover, we've only started with the second version, and there is considerable room for improvement.

Haskell's use of infix operators is significantly more flexible than we've seen so far. Let's consider the simple exponentiation function ^. We can convert this from an infix operation to a binary prefix operation by putting it in parentheses, thus

x^2 and (^) x 2

are essentially the same expression, just written in a different style.

Moreover, we can create a function via a section, in which we provide either the left or right hand argument to a binary operation, but leave the other missing. For example, (+3) is a function that adds three to its argument, e.g.,

(+3) 7 ==> 7 + 3 ==> 10

We can use this to simplify our code above, writing

square = (^2) cube = (^3)

Note that the parentheses are required for a section, and that the special syntax rules for negative numbers prevent the use of the infix subtraction operator (-) to create a section out of subtraction.

But once we've simplified the definitions of square and cube down to simple constants (without any arguments), we can simply eliminate the definitions altogether, like this:

sumSquares xs = sumf (^2) xs sumCubes xs = sumf (^3) xs

At this point, an experienced Haskell programmer would immediately cancel the xs from both sides of both definitions, writing

sumSquares = sumf (^2) sumCubes = sumf (^3)

What's this all about? Let's say that we have two functions, f and g. And let's say that f and g have the same value at every point of their domain, i.e., f x == g x for all x. Then we'd say that f and g are the same function (even if they're defined differently), and write f == g.

Now, consider the definition

g x = f x

What is the relationship between f and g? Well, it's easy to see that for any x, g x reduces to f x. So it seems that f and g are actually equal, which means we could have just written

g = f

In the literature of the λ-calculus (λ is the Greek letter "lambda"), the formal mathematical model of computation that Haskell builds on, the reduction of a function definition of the form.

g x = f x

to

g = f is called an η-reduction (η is the Greek letter "eta"), and Haskell programmers (who generally have very high levels of mathematical literacy) call it that too. Note that η-reduction can only be used when the variable being "cancelled" has no other occurrences in the definition. Consider, e.g.,

double x = x + x

we couldn't just cancel the x, writing

double = x +

as this leaves the remaining occurrence of x unbound. Haskell programmers look for opportunities to η-reduce their definitions, and will play algebraic games with their function definitions to set up an η-reduction. This is really just a simple case of the common mathematical aesthetic that prefers economy, in this particular case, by minimizing the number of new names introduced in a definition. We'll see this throughout the quarter, and it raises an important point: Haskell programmers care a lot about code quality, and they think hard about their code. Mere correctness does not excite a Haskell programmer as much as correctness expressed with elegance and concision. This is not just a conceit. The process of algebraic simplification of code often reveals opportunities for better factoring and a deeper understanding of the problem at hand, while honing skills for the next problem.

But, as they say on late-night commercials, we're not done yet!

Let's factor the problem somewhat differently. In the current implementation, the process of building the sum and evaluating the function remain intertwined, even as we've abstracted out the particular function being evaluated. They can be separated. To that end, let's consider the map function, which might be implemented as follows:

map f [] = [] map f (x:xs) = f x : map f xs

This is another natural recursion, which builds a new list, gathering into a list the image under the given function of each of the elements of the original list. For example

> map square [1..4] [1,4,9,16]

Note also another Haskellism for constructing a list. Certainly, writing [1..1000] is a lot easier than writing out the list long hand, but it's also, and more importantly, clearer and less error prone.

With map in hand, we can write

sumSquares xs = sum (map (^2) xs)

This is literally a one-liner, because sum and map are predefined in Prelude.hs, and it's superfluous to code them ourselves. It may not be clear that we've gained anything, but we're not done yet. Remember what we said about Haskell programmers liking to η-reduce? This expression has only a single occurrence of xs on the right hand side, and so it seems like a candidate for η-reduction. But how? That occurrence is inside a set of parentheses, so we can't just cancel.

Haskell is actually a curried language, in which all functions are unary. Thus, a function like map, formally takes a single argument (e.g., (^2) in the example above), which returns a unary function. In Haskell, application associates to the left, so the right hand side of this is actually

sum ((map (^2)) xs)

The pattern f (g x) appears a lot in functional code, so naturally enough there's an operator (.), called composition such that f (g x) == (f . g) x. We can use this to re-write the definition above as

sumSquares xs = (sum . map (^2)) xs

and η-reduce to

sumSquares = sum . map (^2)

which is pretty tight. But was this all worth the effort? For a programmer, this is going to boil down to clarity, efficiency, and maintainability. This may not seem too clear to you just yet, but it will grow on you. You can think about a succession of functions that get applied to a list, read right-to-left, possibly including a summarization function (like sum) at the end. And it's very easy to think about changing the parts or order, e.g., altering the summarization function so that a sum is replace by a product. This kind of programming is sometimes called “point-free,” because we're defining functions via function combinators directly, rather than by referring to specific points in the domain.

*Exercise 2.1. Implement the product function. This should take a list of numbers, and return their product.

Note that this function is already present in Prelude.hs, and that creates a conflict. The simple solution, which is mostly relevent for these early programming exercises, is to explicitly hide definitions in the Prelude that we're reimplementing as exercises, e.g.,

import Prelude hiding (sum,product)

Use your implementation of product to determine the product of the squares of the first numbers 1 through 10.

Let's suppose now that we wanted to sum the squares of the odd numbers from one to one-hundred. We could approach this directly:

sumSquaresOfOdds [] = 0 sumSquaresOfOdds (x:xs) | odd x = x^2 + sumSquaresOfOdds xs | otherwise = sumSquaresOfOdds xs

This definition involves a programming new construct, guarded equations. The idea here is that we'll define a function by cases through a sequence of predicates (tests/guards) and equations. The reduction of a term will evaluate each of the predicates in turn, until a predicate evaluates to True. Once this happens, the corresponding equation defines the value of the construct.

Note here the use of otherwise as a catch-all guard; otherwise isn't a keyword, it's an ordinary variable that's bound to True for improved readability and conformance with standard mathematical terminology.

Syntactically, Haskell uses indentation to indicate structure. The guarded equations must be indented, and indented by exactly the same amount within any definition.

After our discussion of map, we hope you can anticipate a bit. Here we're actually mixing together three distinct things: filtering a list for elements that meet a particular test, squaring each resulting element, and combining the results via sum. In this case, the filtering is the new part:

filter p [] = [] filter p (x:xs) | p x = x : filter p xs | otherwise = filter p xs

Again, this is a built-in function in Prelude.hs, so we don't actually need to implement it. But after our experience from simplifying sumSquares, the final form of our solution practically writes itself:

sumSquaresOfOdds = sum . map (^2) . filter odd

*Exercise 2.2 Let's consider the following problem: compute the sum of the first 100 natural numbers which are divisible by 2 and 3, but not 4 or 9. We'd like to do this in a way that makes it easy to perform similar computations in the future.

It's not hard to see that we're going to need to use sum and filter. There's a very nice function in the Prelude named take, which will return the first n elements of a list. With this, the problem boils down to

result = sum . take 100 . ?? $ [0..]

There's some new syntax here:

How can we fill in the ??? First off, it would be nice to have a predicate divisibleBy such that divisibleBy d n evaluates to True if and only if d evenly divides n. With such a predicate, we could solve the problem this way:

result = sum . take 100 . filter (divisibleBy 2) . filter (divisibleBy 3) . filter (not . divisibleBy 4) . filter (not . divisibleBy 9) $ [0..]

This isn't terrible, but it feels just a bit cumbersome. It would be nice to have a function allp which takes two arguments, a list of predicates ps, and a value x, and which returns True if and only if p x evaluates to True for every p in ps. With this, we could write:

result2 = sum . take 100 . filter (allp [ divisibleBy 2 , divisibleBy 3 , not . divisibleBy 4 , not . divisibleBy 9 ]) $ [0..]

This feels a lot better, because it is fairly easy for us to insert or delete tests. But we can due just a bit better still, writing another function filterAll that combines filter with allp, so that

result3 = sum . take 100 . filterAll [ divisibleBy 2 , divisibleBy 3 , not . divisibleBy 4 , not . divisibleBy 9 ] $ [0..]

For this exercise, you should define

And verify that all three results are the same. Strive for simplicity and clarity in your code.

Exercise 2.3 The definition of allp you gave for the previous exercise was probably an inductive definition in the style of the definition of map or filter. If you think about the problem a bit, you'll see that you the definition can be reduced to mapping application of a list of functions to a given point with a function that takes a list of booleans, and returns True if and only if all of the elements of that list are True. The later function already exists in the Prelude, as and. This means that you can define allp without an explicitly recursive definition, all you need to do is come up with a function that evaluates another function at a given point.

Give such a definition of allp. Hint: remember that $ is an application operator, and think about building a section.