CMSC-16100

Honors Introduction to Programming, I

Autumn Quarter, 2016

Home Policies Lectures Notes Labs

---

Piazza

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.,

• There's a natural correspondence between the equations we use to define length and the list constructors ([] and (:)).
• In the case where one of the constituent values of an argument (e.g., the cs in the second line above) has the same type as whole argument, we apply our top-level function to that value.

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.

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

---

© 2009–2016 Ravi Chugh, Stuart A. Kurtz
Last modified: November 30, 2016