Lists

So far we’ve always worked with single values like number or booleans. Strings contain multiple characters, but still in some sense a string is just one piece of information. In order to be able to do actual programming, we need to handle variable numbers of items. For this we need data structures.

The basic datastructure in Haskell is the list. Lists are used to store multiple values of the same type (in other words, Haskell lists are homogeneous). This is what a list literal looks like:

[0,3,4,1+1]

A list type is written as [Element], where Element is the type of the lists elements. Here are some more list expressions and their types:

[True,True,False] :: [Bool]
["Moi","Hei"] :: [String]
[] :: [a]                   -- more about this later
[[1,2],[3,4]] :: [[Int]]    -- a list of lists
[1..7] :: [Int]             -- range syntax, value [1,2,3,4,5,6,7]

Haskell lists are implemented as singly-linked lists. We’ll return to this later.

List Operations

The Haskell standard library comes with lots of functions that operate on lists. Here are some of the most important ones, together with their types. We’ll get back to what [a] actually means in a second, but for now you can imagine it means “any list”.

head :: [a] -> a            -- returns the first element
last :: [a] -> a            -- returns the last element
tail :: [a] -> [a]          -- returns everything except the first element
init :: [a] -> [a]          -- returns everything except the last element
take :: Int -> [a] -> [a]   -- returns the n first elements
drop :: Int -> [a] -> [a]   -- returns everything except the n first elements
(++) :: [a] -> [a] -> [a]   -- lists are catenated with the ++ operator
(!!) :: [a] -> Int -> a     -- lists are indexed with the !! operator
reverse :: [a] -> [a]       -- reverse a list
null :: [a] -> Bool         -- is this list empty?
length :: [a] -> Int        -- the length of a list

Sidenote: the last two operations (null and length) actually have more generic types, but here I’m pretending that you can only use them on lists.

Lists can be compared with the familiar == operator.

Do you remember this from our first GHCi session?

Prelude> :t "asdf"
"asdf" :: [Char]

This means that String is just an alias for [Char], which means string is a list of characters. This means you can use all list operations on strings!

Some list operations come from the module Data.List. You can import a module in code or in GHCi with the import Data.List syntax. One example is the sort function which sorts a list:

Prelude> import Data.List
Prelude Data.List> sort [1,0,5,3]
[0,1,3,5]

Note how the set of imported modules shows up in the GHCi prompt.

Examples

Here are some examples of working with lists. In this case, instead of showing you output from GHCi, I merely use ==> to show what an expression evaluates to.

Indexing a list:

[7,10,4,5] !! 2
    ==> 4

Defining a function that discards the 3rd and 4th elements of a list using take and drop:

f xs = take 2 xs ++ drop 4 xs

f [1,2,3,4,5,6]  ==>  [1,2,5,6]
f [1,2,3]        ==>  [1,2]

Rotating a list by taking the first element and moving it to the end:

g xs = tail xs ++ [head xs]

g [1,2,3]      ==>  [2,3,1]
g (g [1,2,3])  ==>  [3,1,2]

Here’s an example of the range syntax:

reverse [1..4] ==> [4,3,2,1]

Using ranges

(from You learn Haskell)

What if we want a list of all numbers between 1 and 20? Sure, we could just type them all out but obviously that's not en elegant way to go about it. Instead, we'll use ranges. Ranges are a way of making lists that are arithmetic sequences of elements that can be enumerated. Numbers can be enumerated. One, two, three, four, etc. Characters can also be enumerated. The alphabet is an enumeration of characters from A to Z. Names can't be enumerated. What comes after "John"? I don't know.

To make a list containing all the natural numbers from 1 to 20, you just write [1..20]. That is the equivalent of writing [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] and there's no difference between writing one or the other except that writing out long enumeration sequences manually is tedious.

ghci> [1..20]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
ghci> ['a'..'z']
"abcdefghijklmnopqrstuvwxyz"
ghci> ['K'..'Z']
"KLMNOPQRSTUVWXYZ"

Ranges are cool because you can also specify a step. What if we want all even numbers between 1 and 20? Or every third number between 1 and 20?

ghci> [2,4..20]
[2,4,6,8,10,12,14,16,18,20]
ghci> [3,6..20]
[3,6,9,12,15,18]

It's simply a matter of separating the first two elements with a comma and then specifying what the upper limit is. While pretty smart, ranges with steps aren't as smart as some people expect them to be. You can't do [1,2,4,8,16..100] and expect to get all the powers of 2. Firstly because you can only specify one step. And secondly because some sequences that aren't arithmetic are ambiguous if given only by a few of their first terms.

To make a list with all the numbers from 20 to 1, you can't just do [20..1], you have to do [20,19..1].

Watch out when using floating point numbers in ranges! Because they are not completely precise (by definition), their use in ranges can yield some pretty funky results.

ghci> [0.1, 0.3 .. 1]
[0.1,0.3,0.5,0.7,0.8999999999999999,1.0999999999999999]

My advice is not to use them in list ranges.

You can also use ranges to make infinite lists by just not specifying an upper limit. Later we'll go into more detail on infinite lists. For now, let's examine how you would get the first 24 multiples of 13. Sure, you could do [13,26..24*13]. But there's a better way: take 24 [13,26..]. Because Haskell is lazy, it won't try to evaluate the infinite list immediately because it would never finish. It'll wait to see what you want to get out of that infinite lists. And here it sees you just want the first 24 elements and it gladly obliges.

A handful of functions that produce infinite lists:

cycle takes a list and cycles it into an infinite list. If you just try to display the result, it will go on forever so you have to slice it off somewhere.

ghci> take 10 (cycle [1,2,3])
[1,2,3,1,2,3,1,2,3,1]
ghci> take 12 (cycle "LOL ")
"LOL LOL LOL "

repeat takes an element and produces an infinite list of just that element. It's like cycling a list with only one element.

ghci> take 10 (repeat 5)
[5,5,5,5,5,5,5,5,5,5]

Although it's simpler to just use the replicate function if you want some number of the same element in a list. replicate 3 10 returns [10,10,10].

Exercises

All exercises can be found in Set2a and Set2b. Please pay attention in the title of the exercise in which file the exercises of this section can be found.

Exercises from 2a:

Exercises from 2b:

You can check your current points from the blue blob in the bottom-right corner of the page.