Haskell/Lists and tuples

From Wikibooks, the open-content textbooks collection

Lists and tuples are two ways of binding several values down into a single value.

[edit] Lists

[edit] The functional programmer's next best friend

In the last section we introduced the concept of variables and functions in Haskell. Functions are one of the two major building blocks of any Haskell program. The other is the versatile list. So, without further ado, let's switch over to the interpreter and build some lists:

[edit] Example - Building Lists in the Interpreter

Prelude> let numbers = [1,2,3,4]
Prelude> let truths  = [True, False, False]
Prelude> let strings = ["here", "are", "some", "strings"]

The square brackets denote the beginning and the end of the list. List elements are separated by the comma "," operator. Further, list elements must be all of the same type. Therefore, [42, "life, universe and everything else"] is not a valid list because it contains two elements of different types, namely, integer and string respectively. However, [12, 80] or, ["beer", "sandwiches"] are valid lists because they are both type-homogeneous.

Here is what happens if you try to define a list with mixed-type elements:

Prelude> let mixed = [True, "bonjour"]

<interactive>:1:19:
    Couldn't match `Bool' against `[Char]'
      Expected type: Bool
      Inferred type: [Char]
    In the list element: "bonjour"
    In the definition of `mixed': mixed = [True, "bonjour"]

If you're confused about this business of lists and types, don't worry about it. We haven't talked very much about types yet and we are confident that this will clear up as the book progresses.

[edit] Building lists

Square brackets and commas aren't the only way to build up a list. Another thing you can do with them is to build them up piece by piece, by consing^[1] things on to them, via the (:) operator.

When you cons something on to a list (something:someList), what you get back is another list. So, unsurprisingly, you could keep on consing your way up.

In fact, this is just about how all lists are built, by consing them up from the empty list ([]). The commas and brackets notation is actually a pleasant form or syntactic sugar. In other words, a list like [1,2,3,4,5] is exactly equivalent to 1:2:3:4:5:[]

You will, however, want to watch out for a potential pitfall in list construction. Whereas 1:2:[] is perfectly good Haskell, 1:2 is not. In fact, if you try it out in the interpreter, you get a nasty error message.

Well, to be fair, the error message is nastier than usual because numbers are slightly funny beasts in Haskell. Let's try this again with something simpler, but still wrong, True:False

The basic intuition for this is that the cons operator, (:) works with this pattern something:someList ; however, what we gave it is more something:somethingElse. Cons only knows how to stick things onto lists. We're starting to run into a bit of reasoning about types. Let's summarize so far:

• The elements of the list must have the same type.
• You can only cons (:) something onto a list.

Well, sheesh, aren't types annoying? They are indeed, but as we will see in Type basics, they can also be a life saver. In either case, when you are programming in Haskell and something blows up, you'll probably want to get used to thinking "probably a type error".

Exercises

Would the following piece of Haskell work: 3:[True,False]? Why or why not? Write a function cons8 that takes a list and conses 8 on to it. Test it out on the following lists by doing: cons8 [] cons8 [1,2,3] cons8 [True,False] let foo = cons8 [1,2,3] cons8 foo Write a function that takes two arguments, a list and a thing, and conses the thing onto the list. You should start out with:      let myCons list thing =

[edit] Lists within lists

Lists can contain anything, just as long as they are all of the same type. Well, then, chew on this: lists are things too, therefore, lists can contain... yes indeed, other lists! Try the following in the interpreter:

Lists of lists can be pretty tricky sometimes, because a list of things does not have the same type as a thing all by itself. Let's sort through these implications with a few exercises:

Exercises

Which of these are valid Haskell and which are not? Rewrite in cons notation. [1,2,3,[]] [1,[2,3],4] [[1,2,3],[]] Which of these are valid Haskell, and which are not? Rewrite in comma and bracket notation. []:[[1,2,3],[4,5,6]] []:[] []:[]:[] [1]:[]:[] Can Haskell have lists of lists of lists? Why or why not? Why is the following list invalid in Haskell? Don't worry too much if you don't get this one yet. [[1,2],3,[4,5]]

Lists of lists are extremely useful, because they allow you to express some very complicated, structured data (two-dimensional matrices, for example). They are also one of the places where the Haskell type system truly shines. Human programmers, or at least this wikibook author, get confused all the time when working with lists of lists, and having restrictions of types often helps in wading through the potential mess.

[edit] Tuples

[edit] A different notion of many

Tuples are another way of storing multiple values in a single value, but they are subtly different in a number of ways. They are useful when you know, in advance, how many values you want to store, and they lift the restriction that all the values have to be of the same type. For example, we might want a type for storing pairs of coordinates. We know how many elements there are going to be (two: an x and y coordinate), so tuples are applicable. Or, if we were writing a phonebook application, we might want to crunch three values into one: the name, phone number and address of someone. Again, we know how many elements there are going to be. Also, those three values aren't likely to have the same type, but that doesn't matter here, because we're using tuples.

Let's look at some sample tuples.

The first example is a tuple containing two elements. The first one is True and the second is 1. The next example again has two elements, the first is "Hello world" and the second, False. The third example is a bit more complex. It's a tuple consisting of five elements, the first is 4 (a number), the second 5 (another number), the third "Six" (a string), the fourth True (a boolean value), and the last one 'b' (a character). So the syntax for tuples is: separate the different elements with a comma, and surround the whole thing in parentheses.

A quick note on nomenclature: in general you write n-tuple for a tuple of size n. 2-tuples (that is, tuples with 2 elements) are normally called 'pairs' and 3-tuples triples. Tuples of greater sizes aren't actually all that common, although, if you were to logically extend the naming system, you'd have 'quadruples', 'quintuples' and so on, hence the general term 'tuple'.

So tuples are a bit like lists, in that they can store multiple values. However, there is a very key difference: pairs don't have the same type as triples, and triples don't have the same type as quadruples, and in general, two tuples of different sizes have different types. You might be getting a little disconcerted because we keep mentioning this word 'type', but for now, it's just important to grasp how lists and tuples differ in their approach to sizes. You can have, say, a list of numbers, and add a new number on the front, and it remains a list of numbers. If you have a pair and wish to add a new element, it becomes a triple, and this is a fundamentally different object ^[2].

Exercises

Write down the 3-tuple whose first element is 4, second element is "hello" and third element is True. Which of the following are valid tuples ? (4, 4) (4, "hello") (True, "Blah", "foo") Lists can be built by consing new elements onto them: you cons a number onto a list of numbers, and get back a list of numbers. It turns out that there is no such way to build up tuples. Why do you think that is? Say for the sake of argument, that there was such a function. What would you get if you "consed" something on a tuple?

[edit] What are tuples for?

Tuples are handy when you want to return more than one value from a function. In most languages trying to return two or more things at once means wrapping them up in a special data structure, maybe one that only gets used in that function. In Haskell, just return them as a tuple.

Haskell records often serve the same purpose but you would have to specify the names of the components then. We'll meet up with records on the way.

You can also use tuples as a primitive kind of data structure. But that needs an understanding of types, which we haven't covered yet.

[edit] Getting data out of tuples

In this section, we concentrate solely on pairs. This is mostly for simplicity's sake, but pairs are far and away the most commonly used size of tuple.

Okay, so we've seen how we can put values into tuples, simply by using the (x, y, z) syntax. How can we get them out again? For example, a typical use of tuples is to store the (x, y) coordinate pair of a point: imagine you have a chess board, and want to specify a specific square. You could do this by labeling all the rows from 1 to 8, and similarly with the columns, then letting, say, (2, 5) represent the square in row 2 and column 5. Say we want to define a function for finding all the pieces in a given row. One way of doing this would be to find the coordinates of all the pieces, then look at the row part and see if it's equal to whatever row we're being asked to examine. This function would need, once it had the coordinate pair (x, y) of a piece, to extract the x (the row part). To do this there are two functions, fst and snd, which project the first and second elements out of a pair, respectively (in math-speak, a function that gets some data out of a structure is called a "Projection"). Let's see some examples:

It should be fairly obvious what these functions do. Note that you can only use these functions on pairs. Why? It all harks back to the fact that tuples of different sizes are different beasts entirely. fst and snd are specialized to pairs, and so you can't use them on anything else ^[3].

Exercises
Use a combination of fst and snd to extract the 4 from the tuple (("Hello", 4), True). Normal chess notation is somewhat different to ours: it numbers the rows from 1-8 and the columns a-h; and the column label is customarily given first. Could we label a specific point with a character and a number, like ('a', 4)? What important difference with lists does this illustrate?

The general technique for extracting a component out of a tuple is pattern matching (yep, we'll talk about it in great detail later on, as this is one of the distinctive features of functional languages). Without making things more complicated than they ought to be at this point, let me just show you how I can write a function named first that does the same thing as fst:

This just says that given a pair (x, y), first (x, y) gives you x.

[edit] Tuples within tuples (and other combinations)

We can apply the same reasoning to tuples about storing lists within lists. Tuples are things too, so you can store tuples with tuples (within tuples up to any arbitrary level of complexity). Likewise, you could also have lists of tuples, tuples of lists, all sorts of combinations along the same lines.

Some discussion about this - what you get out of this, maybe, what's the big idea behind grouping things together

There is one bit of trickiness to watch out for, however. The type of a tuple is defined not only by its size, but by the types of objects it contains. For example, the tuples ("Hello",32) and (47,"World") are fundamentally different. One is of type (String,Int), whereas the other is (Int,String). This has implications for building up lists of tuples. We could very well have lists like [("a",1),("b",9),("c",9)], but having a list like [("a",1),(2,"b"),(9,"c")] is right out. Can you spot the difference?

Exercises
Which of these are valid Haskell, and why? fst [1,2] 1:(2,3) (2,4):(2,3) (2,4):[] [(2,4),(5,5),('a','b')] ([2,4],[2,2]) FIXME: [(1::Integer,"a"),(2.2,"b"),(9.0,"c")]

[edit] Summary

We have introduced two new notions in this chapter, lists and tuples. To sum up:

1. Lists are defined by square brackets and commas : [1,2,3].
   • They can contain anything as long as all the candidate elements of the list are of the same type
   • They can also be built by the cons operator, (:), but you can only cons things onto lists
2. Tuples are defined by parentheses and commas : ("Bob",32)
   • They can contain anything, even things of different types
   • They have a fixed length, or at least their length is encoded in their type. That is, two tuples with different lengths will have different types.
3. Lists and tuples can be combined in any number of ways: lists within lists, tuples with lists, etc

We hope that at this point, you're somewhat comfortable enough manipulating them as part of the fundamental Haskell building blocks (variables, functions and lists), because we're now going to move to some potentially heady topics, types and recursion. We have alluded to types thrice in this chapter without really saying what they are, so these shall be the next major topic that we cover. But before we get to that, we're going to make a short detour to help you make better use of the GHC interpreter.

[edit] Notes

1. ↑ You might object that that isn't even a proper word. Well, it isn't. Among programmers, the tradition started from LISP, to call this specific task of appending an element in front of a list "consing". The verb here is "cons", which happens to be a mnemonic for "constructor", as it is the way lists are constructed.
2. ↑ At least as far as types are concerned, but we're trying to avoid that word :)
3. ↑ More technically, fst and snd have types which limit them to pairs. It would be impossible to define projection functions on tuples in general, because they'd have to be able to accept tuples of different sizes, so the type of the function would vary.

[edit] Notes