Lesson 6. Lists

After reading lesson 6, you’ll be able to

In many ways, an array is the fundamental data structure for programming in C. If you properly understand arrays in C, you necessarily understand how memory allocation works, how data is stored on a computer, and the basics of pointers and pointer arithmetic. For Haskell (and functional programming in general), the fundamental data structure is a list. Even as you approach some of the more advanced topics in this book, such as functors and monads, the simple list will still be the most useful example.

This lesson provides a proper introduction to this surprisingly important data structure. You’ll learn the basics of taking lists apart and putting them back together, as well as learning some of the essential functions for a list that Haskell provides. Finally, you’ll take a peek at another unique feature of Haskell: lazy evaluation. Lazy evaluation is so powerful that it allows you to represent and work with lists that are infinitely long! If you get stuck on a topic in Haskell, it’s almost always helpful to turn back to lists to see if they can give you some insight.

6.1. The anatomy of a list

Lists are the single most important data structure in functional programming. One of the key reasons is that lists are inherently recursive. A list is either an empty list or an element followed by another list. Taking apart and building lists are fundamental tools for many techniques in functional programming.

When taking apart a list, the main pieces are the head, the tail, and the end (represented by []). The head is just the first element in a list:

The tail is the rest of the list left over, after the head:

The tail of a list with just one element is [], which marks the end of the list. This end of the list is just an empty list. But an empty list is different from other lists, as it has neither a head nor a tail. Calling head or tail on [] will result in an error. If you look at the head and tail, you can start to see the recursive nature of working with lists: a head is an element, and a tail is another list. You can visualize this by imagining tearing the first item off a grocery list, as in figure 6.1.

You can break a list into pieces, but this does you little good if you can’t put them back together again! In functional programming, building lists is just as important as breaking them down. To build a list, you need just one function and the infix operator (:), which is called cons. This term is short for construct and has its origins in Lisp. We’ll refer to this operation as consing, because : looks a bit odd in a sentence.

To make a list, you need to take a value and cons it with another list. The simplest way to make a list is to cons a value with the empty list:

Under the hood, all lists in Haskell are represented as a bunch of consing operations, and the [...] notation is syntactic sugar (a feature of the programming language syntax designed solely to make things easier to read):

Notice that all of these lists end with the empty list []. By definition, a list is always a value consed with another list (which can also be an empty list). You could attach the value to the front of an existing list if you wanted:

It’s worth noting that the strings you’ve seen so far are themselves syntactic sugar for lists of characters (denoted by single quotes rather than double quotes):

An important thing to remember is that in Haskell every element of the list must be the same type. For example, you can cons the letter 'h' to the string "ello" because "ello" is just a list of characters and 'h' (single quotes) is a character:

But you can’t cons "h" (double quotes) to "ello" because "h" is a list of one character and the values inside "ello" are individual characters. This becomes more obvious when you remove the syntactic sugar.

If you do want to combine two lists, you need to concatenate them by using ++. You saw this in lesson 3 with concatenating text, but given that strings are just lists, it will work on any list:

Consing is important to understand because it’s an essential part of writing recursive functions on lists. Nearly all sequential operations in functional programing involve building lists, breaking them apart, or a combination of the two.

6.2. Lists and lazy evaluation

Because lists are so important in Haskell, there are many ways to quickly generate ranges of data. Here are some examples:

These are useful but not particularly interesting. Many programing languages have a range function that works in a similar manner. What happens if you forget to put an upper bound to your range?

An unending list is generated! This is cool but quickly clogs up the terminal and doesn’t seem particularly useful. What’s interesting is that you can assign this list to a variable and even use it in a function:

What’s shocking is that this code compiles just fine. You defined an infinite list and then used it in a function. Why didn’t Haskell get stuck trying to evaluate an infinitely long list? Haskell uses a special form of evaluation called lazy evaluation. In lazy evaluation, no code is evaluated until it’s needed. In the case of longList, none of the values in the list were needed for computation.

Lazy evaluation has advantages and disadvantages. It’s easy to see some of the advantages. First, you get the computational benefit that any code you don’t absolutely need is never computed. Another benefit is that you can define and use interesting structures such as an infinite list. This can be useful for plenty of practical problems. The disadvantages of lazy evaluation are less obvious. The biggest one is that it’s much harder to reason about the code’s performance. In this trivial example, it’s easy to see that any argument passed to simple won’t be evaluated, but even a bit more complexity makes this less obvious. An even bigger problem is that you can easily build up large collections of unevaluated functions that would be much cheaper to store as values.

6.3. Common functions on lists

Because lists are so important, a wide range of useful functions are built into Haskell’s standard library module, called Prelude. So far, you’ve seen head, tail, : and ++, which allow you to take apart lists and put them back together. There are many other useful functions on lists that will come up so frequently when writing Haskell that it’s worth familiarizing yourself with them.

6.3.1. The !! operator

If you want to access a particular element of a list by its index, you can use the !! operator. The !! operator takes a list and a number, returning the element at that location in the list. Lists in Haskell are indexed starting at 0. If you try to access a value beyond the end of the list, you’ll get an error:

As mentioned in lesson 5, any infix operator (an operator that’s placed between two values, such as +) can also be used like a prefix function by wrapping it in parentheses:

Using prefix notation can often make things such as partial application easier. Prefix notation is also useful for using operators as arguments to other functions. You can still use partial application with an infix operator; you just need to wrap the expression in parentheses:

Notice that in paExample2 you see how partial application works with infix binary operators. To perform partial application on a binary operator, called a section, you need to wrap the expression in parentheses. If you include only the argument on the right, the function will be waiting for the leftmost argument; if you include only the argument on the left, you get a function waiting for the argument on the right. Here’s paExample3, which creates partial application of the right argument:

The important thing to remember about sections is that the parentheses aren’t optional.

6.3.2. length

The length function is obvious; it gives you the length of the list!

6.3.3. reverse

As expected, reverse reverses the list:

You can use reverse to make a basic palindrome checker, as shown in the next listing.

6.3.4. elem

The elem function takes a value and a list and checks whether the value is in the list:

elem is a function that you may want to treat as an infix operator for readability. Any binary function can be treated as an infix operator by wrapping it in back-quotes (`). For example, the function respond returns a different response depending on whether a string has an exclamation mark, as follows.

Whether infix elem adds much readability is certainly debatable, but in the real world you’ll frequently come across infix forms of binary functions.

6.3.5. take and drop

The take function takes a number and a list as arguments and then returns the first n elements of the list:

If you ask for more values then a list has, take gives you what it can, with no error:

take works best by being combined with other functions on lists. For example, you can combine take with reverse to get the last n elements of a list.

The drop function is similar to take, except it removes the first n elements of a list:

6.3.6. zip

You use zip when you want to combine two lists into tuple pairs. The arguments to zip are two lists. If one list happens to be longer, zip will stop whenever one of the two lists is empty:

6.3.7. cycle

The cycle function is particularly interesting, because it uses lazy evaluation to create an infinite list. Given a list, cycle repeats that list endlessly. This may seem somewhat useless but comes in handy in a surprising number of situations. For example, it’s common in numerical computing to need a list of n ones. With cycle, this function is trivial to make.

cycle can be extremely useful for dividing members of a list into groups. Imagine you want to divide a list of files and put them on n number of servers, or similarly spilt up employees onto n teams. The general solution is to create a new function, assignToGroups, that takes a number of groups and a list, and then cycles through the groups, assigning members to them.

These functions are just some of the more common of a wide range of list functions that Haskell offers. Not all of the functions on lists are included in the standard Prelude module. All list functions, including those automatically included in Prelude, are in the Data.List module. An exhaustive list of Data.List functions can be found online in the standard Haskell documentation (https://hackage.haskell.org/package/basedocs/Data-List.html).

Summary

In this lesson, our objective was to go over the basic structure of a list. You learned that a list is made up of a head and a tail that are consed together. We also went over many of the most common functions on a list. Let’s see if you got this.

Q6.1

Haskell has a function called repeat that takes a value and repeats it infinitely. Using the functions you’ve learned so far, implement your own version of repeat.

Q6.2

Write a function subseq that takes three arguments: a start position, an end position, and a list. The function should return the subsequence between the start and end. For example:

Q6.3

Write a function inFirstHalf that returns True if an element is in the first half of a list, and otherwise returns False.