1. Lists, recursively defined
1.1 defination
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 nonempty 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:
'h':('e':('l':('l':('o':[]))))
Of course, we don't actually write lists recursively like that. Here's an equivalent expression:
['h','e','l','l','o']
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 [1..6]
It also works with characters:
['a'..'e']
gives ['a','b','c','d','e']
You can also control the step size by giving the first two elements:
[1,2..6]
gives [1,2,3,4,5,6]
[1,3..6]
gives [1,3,5]
[5,4..0]
gives [5,4,3,2,1,0]
In fact, there's no need to place an upper bound at all. Try entering the following lists into ghci:
[1..]
[2,4..]
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 :
operator. x:xs
means a list where the first element is x
and the remaining elements are another list called xs
.
Thus, this pattern will match any nonempty list, assigning the first element to x
and the remaining elements to xs
.
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!
2.2 Guards
Here's another example of a recursive list function. This time, it finds the maximum element of a nonempty 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: where
.
As you can see, you can use where
to define 'helper' variables and functions to avoid repetition of code and computation.
Note:
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.
Note:
Don't forget  before the otherwise.
3. List functions
3.1 Standard functions
Common list functions like sum
and maximum
are already defined for you out of the box. Indeed, if you tried to redefine them, you would see an error, but still be able to run the inbuilt versions.
Actually, your own function search is provided for us too, but it's called elem.
There are plenty of other such inbuilt functions; here are a few of the most useful:

length
computes the number of elements in a list 
null
returns True if a list is empty, and False otherwise 
the
!!
operator gets the nth element of a list, as in[1,2,3,4] !! 2
, which gives us 3 (note zerobased list indexing). 
the
++
operator joins two lists together, as in[1,2] ++ [3,4]
, which gives us [1,2,3,4]
As you use these inbuilt 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 head
, tail
, last
, init
, take
and 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 [1,2,3,4,5,6,7,8,9,10]
.
head
andtail
separate a list into its first and remaining elements:
1 [2, 3, 4, 5, 6, 7, 8, 9, 10]
head ' <tail>
last
andinit
do just the opposite:
[1, 2, 3, 4, 5, 6, 7, 8, 9] 10
<init> ' last
take n
anddrop n
split 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>
Note:
These function will not modify the list itself.
4. Higherorder functions
4.1 给函数里传函数
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 higherorder 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 higherorder 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 True
or False
, depending on the function.
Note:
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
Higherorder 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
What's (<pivot)?
In the above function there's some neverbeforeseen 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 preimplemented 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:
import Data.List
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:
group
separates a list into sublists of adjacent, matching numbers. For example,group [1,1,3,3,2,1]
gives [[1,1],[3,3],[2],[1]].nub
removes all duplicates from a list. That is,nub [1,1,3,3,2,1]
gives [1,3,2].delete x
removes 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.
5.2 Map
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 writemap abs xs
.  Instead of
evenAll xs
, just writemap even xs
.  Instead of
squareAll xs
, just writemap (^2) xs
.
评论区