1. Lists, recursively defined
Lists—as in linked lists—are pretty much Haskell's most fundamental data structure. We will certainly use them a lot this semester.
Like most things in Haskell, lists are defined entirely recursively:
- Base case: the empty list is written 
- Recursive case: a non-empty list is written x:list where x is the list's first element, and list is the rest of the list (which is itself a list).
In other words, to build a list in Haskell, you start with  and prepend elements one at a time with : until you are done.
Here's an example of such a list of characters:
Of course, we don't actually write lists recursively like that. Here's an equivalent expression:
1.2 Generate a list
When we get tired of typing out long lists, we can also generate them using range notation.
To generate the list
[1,2,3,4,5,6], we could just write
It also works with characters:
You can also control the step size by giving the first two elements:
In fact, there's no need to place an upper bound at all. Try entering the following lists into ghci:
2. List's pattern matching
2.1 Functions with lists
When writing functions with lists (recursive functions, of course), we often find two cases:
- the base case, where we handle the empty list (or, sometimes, a list of one element)
- the recursive case, where we process the first element in the list and recursively process the rest of the list
Since lists themselves are defined recursively, writing such functions is pretty easy using pattern matching and :.
For example, here's a simple recursive function to add together the numbers in a list of integers:
sum :: [Int] -> Int sum  = 0 sum (x:xs) = x + sum xs
See the pattern
(x:xs) in the second equation? Remember that a list is defined one element at a time using the
x:xs means a list where the first element is
x and the remaining elements are another list called
Thus, this pattern will match any non-empty list, assigning the first element to
x and the remaining elements to
Don't forget the parentheses!
If you don't include the parentheses in the recursive case above, Haskell will read the equation as (sum x):xs = x + sum xs, which makes no sense!
Here's another example of a recursive list function. This time, it finds the maximum element of a non-empty list of integers.
Check out the base case: it's not the empty list this time.
maximum :: [Int] -> Int maximum [x] = x maximum (x:xs) | x > maxxs = x | otherwise = maxxs where maxxs = maximum xs
This example is also the first time we have a chance to show off one of Haskell's nice features for containing complex expressions:
As you can see, you can use
where to define 'helper' variables and functions to avoid repetition of code and computation.
A common beginner's mistake is to read maximum [x] as "maximum of the list x". However, it is [x] that is a list; it is a list which has just one element, namely x. In the definition above, [x] is a pattern which will match any singleton list (any list of one element), and only such lists.
Don't forget | before the otherwise.
3. List functions
3.1 Standard functions
Common list functions like
maximum are already defined for you out of the box. Indeed, if you tried to re-define them, you would see an error, but still be able to run the in-built versions.
Actually, your own function search is provided for us too, but it's called elem.
There are plenty of other such in-built functions; here are a few of the most useful:
lengthcomputes the number of elements in a list
nullreturns True if a list is empty, and False otherwise
!!operator gets the nth element of a list, as in
[1,2,3,4] !! 2, which gives us 3 (note zero-based list indexing).
++operator joins two lists together, as in
[1,2] ++ [3,4], which gives us [1,2,3,4]
As you use these in-built functions, you might like to think about how you could implement each of them yourself using a simple recursive Haskell function.
3.2 More functions
Some other common list functions are
drop. These functions provide different ways of taking apart lists, as shown in the examples below. In each example, we'll show the functions applied to the list
tailseparate a list into its first and remaining elements:
1 [2, 3, 4, 5, 6, 7, 8, 9, 10] head --' <--------------tail-------------->
initdo just the opposite:
[1, 2, 3, 4, 5, 6, 7, 8, 9] 10 <---------------init------------> '-- last
drop nsplit the list at an arbitrary point. For example, using 4 for n:
[1, 2, 3, 4] [5, 6, 7, 8, 9, 10] <--take 4---> <-------drop 4------->
These function will not modify the list itself.
4. Higher-order functions
You may remember that in the previous module, we mentioned that in Haskell, you can pass around functions as arguments and return values in just the same way as you can pass around integers, strings or Boolean values. Functions that take other functions as arguments, or return other functions, are called higher-order functions. Such functions are used all the time in Haskell programming.
An example of when a Haskell programmer would reach for a higher order function is as follows:
Consider our linear search function from a few exercises ago. It traverses a list of integers and returns True when it finds an integer equal to the search integer, which we provide as an argument.
Let's say I wanted to carry out a linear search in a list, but instead of looking for an instance of a particular integer, I wanted to look for any even integer.
Or maybe I want to look for any integer greater than 100.
Or maybe I want to find an integer that contains the digit 3.
Or maybe I want to do all of these things!
A higher-order search function would allow us to provide the function that decides when to stop searching as an argument.
For example, lets say we had the following helper functions available:
evn :: Int -> Bool evn x = (x `mod` 2 == 0) big :: Int -> Bool big x = (x > 100)
It'd be great if we could pass these functions as arguments to our search function. Something like this:
Main> search evn [1, 2, 3, 4, 5] 2 Main> search big [1, 2, 101, 4, 5] 101 Main> search evn [1, 3, 5, 7, 9] error: search: no matching item found
So what we want is a search function that takes two arguments:
- A function which can test each integer in the list and tell us True if there's a match. Its type should be Int -> Bool. Let's call this argument tst, for 'test function'.
- A list of integers to search through, of type [Int]
Here we go:
search :: (Int -> Bool) -> [Int] -> Int search tst  = error "search: no matching number found" search tst (x:xs) | tst x = x | otherwise = search tst xs
We just passed around tst like any other argument, and then we used it in the first guard as if it were a normal function:
tst x will apply the provided test function to
x and return
False, depending on the function.
Notice how we give the type as (Int -> Bool) -> [Int] -> Int. This says that search's first argument is of type Int -> Bool. If we forgot the parentheses, that'd give us a function with three arguments (Int, Bool and [Int]).
4.2 Filter and abstraction
Higher-order functions like
filter provide a layer of abstraction above writing the same recursive list traversal code over and over again; by using functions as arguments we can write general recursive code once and reuse it whenever we need.
Using the higher order function
filter (or our allsearch function) and a little more Haskell magic (see note below), a Haskell implementation of a naive quicksort clocks in at 5 lines of code:
qsort :: [Int] -> [Int] qsort  =  qsort (pivot:others) = (qsort lowers) ++ [pivot] ++ (qsort highers) where lowers = filter (<pivot) others highers = filter (>=pivot) others
In the above function there's some never-before-seen stuff happening. Namely, we are passing something that doesn't really look like much of a function to filter:
What is this (<pivot) thing?
Well, in Haskell, (<x) is a shortcut for a function that takes one argument and returns True if the argument is less than x, and False otherwise. We might come back to this later, it can prove pretty useful. In the meantime, if you're especially keen, go look up operator sections.
5. More list functions
5.1 Import Data.List
If you do ever need to sort a list, a pre-implemented
sort function is available. But it's not there by default; you'll need to import a module to get it.
The module that contains sort is called
Data.List. You can access it by adding the line import Data.List to your program:
The Data.List module contains plenty more useful functions for manipulating lists. Here's a short list with a few functions you might find useful this semester, aside from the sort function:
groupseparates a list into sublists of adjacent, matching numbers. For example,
group [1,1,3,3,2,1]gives [[1,1],[3,3],,].
nubremoves all duplicates from a list. That is,
nub [1,1,3,3,2,1]gives [1,3,2].
delete xremoves the first occurrence of x from a list. For example,
delete 3 [2,3,4,3]gives [2,4,3].
- The operator
\\deletes each of the elements of one list from another list:
[1,2,3,2] \\ [2,1]gives [3,2].
Remember, your program needs to import Data.List if you want to use these extra list functions.
In all of the functions on the previous slide, we were making a new list by applying a single function to every element of an input list. It simplifies our group of functions quite nicely:
- Instead of
absAll xs, just write
map abs xs.
- Instead of
evenAll xs, just write
map even xs.
- Instead of
squareAll xs, just write
map (^2) xs.