CSc 372 - Comparative Programming Languages
6 : Haskell -- Lists

Christian Collberg

Department of Computer Science

University of Arizona

1 The List Datatype

All functional programming languages have the ConsList ADT built-in. It is called so because lists are constructed by ``consing'' (adding) an element on to the beginning of the list.
Lists are defined recursively:
1. The empty list [ ] is a list.
2. An element x followed by a list L (x:L), is a list.
Examples:
$\begin{program}[\ ]\\ 2:[\ ] \\ 3:(2:[\ ]) \\ 4:(3:(2:[\ ])) \end{program}$

2 The List Datatype...

The cons operator ":" is right associative (it binds to the right, i.e.
$\begin{program} 1:2:[\ ] $\equiv$\ 1:(2:[\ ]) \\ \end{program}$
so
$\begin{program} 3:(2:[\ ]) \end{program}$
can be written without brackets as
$\begin{program} 3:2:[\ ] \end{program}$

3 The List Datatype...

Lists can also be written in a convenient bracket notation.
$\begin{gprogram} 2:[\ ] \xxxxx $\Rightarrow$\ [2] \\ 3:(2:[\ ]) \xxxxx $\Rightarrow$\ [3,2] \\ 4:(3:(2:[\ ]) \xxxxx $\Rightarrow$\ [4,3,2] \end{gprogram}$
You can make lists-of-lists ([[1],[5]]), lists-of-lists-of-lists ([[[1,2]],[[3]]]), etc.

4 The List Datatype...

More cons examples:
$\begin{gprogram} \mbox{1:[2,3]} \xxxxx $\Rightarrow$\ [1,2,3] \\ \mbox{[1]:[[2],[3]]} \xxxxx $\Rightarrow$\ [[1],[2],[3]] \end{gprogram}$
Note that the elements of a list must be of the same type!
$\begin{gprogram} \mbox{[1,[1],1]} \xxxxx $\Rightarrow$\ Illegal! \\ \mbox{[[1... ...llegal! \\ \mbox{[1,\tc{True}]} \xxxxx $\Rightarrow$\ Illegal! \end{gprogram}$

5 Internal Representation

Internally, Haskell lists are represented as linked cons-cells.
A cons-cell is like a C struct with two pointer fields head and tail.
The head field points to the first element of the list, the tail field to the rest of the list.
The :-operator creates a new cons-cell (using malloc) and fills in the head and tail fields to point to the first element of the new list, and the rest of the list, respectively.

6 Internal Representation...

Example:
ConsCell

Standard Operations on Lists

7 `head` and `tail`

The Standard Prelude has many built-in operations on lists.
Two principal operators are used to take lists apart:
1. head L - returns the first element of L.
2. tail L - returns L without the first element.
The cons operator ":" is closely related to head and tail:
1. head (x:xs) x
2. tail (x:xs) xs
The cons operator ":" constructs new lists, head and tail take them apart.

8 `head` and `tail`...

$\begin{gprogram} head [1,2,3] \xxxxx $\Rightarrow$\ \x 1 \\ tail [1,2,3] \xxxxx... ...row$\ 2 \\ head (tail [[1],[2],[3,3]]) \xxxxx $\Rightarrow$\ [2] \end{gprogram}$

9 `length` and `++`

length xs - Number of elements in the list xs.
xs ++ ys - The elements of xs followed by the elements of ys.

Examples:
$\begin{gprogram} length [1,2,3] \xxxxxxx $\Rightarrow$\ \x 3 \\ length [\ ] \xx... ...\\ \mbox{[1] ++ [length [2,3]]} \xxxxxxx $\Rightarrow$\ \x [1,2] \end{gprogram}$

10 `concat`

concat xss - all of the lists in xss appended together.

$\begin{gprogram} concat [[1],[4,5],[6]] \xxxxxxxx $\Rightarrow$\ [1,4,5,6] \\ \end{gprogram}$

Note that concat takes a list of lists as argument.

11 `map`

map f xs - list of values obtained by applying the function f to the values in xs.

$\begin{gprogram} map even [1,2,3] \xxxxxx $\Rightarrow$\ [False,True,False] \\ map square [1,2,3] \xxxxxxxx $\Rightarrow$\ [1,4,9] \end{gprogram}$

Note that map takes a function as its first argument. A function which takes a function as an argument or delivers one as its result, is called a higher-order function.
We will talk more about higher-order functions in future lectures.

12 More list operation examples

$\begin{gprogram} head ([1,2] ++ [3,4]) $\Rightarrow$\ \\ \x head [1,2,3,4] $\Ri... ... [1,3,4]) $\Rightarrow$\ \\ \x tail [2,6,8] $\Rightarrow$\ [6,8] \end{gprogram}$

13 The String Type

A Haskell string is a list of characters:
$\begin{gprogram} type String = [Char] \end{gprogram}$
All list manipulation functions can be applied to strings.
Note that "" == [].

$\begin{gprogram} ''Chris'' \xxxx $\Leftrightarrow$\ ['C','h','r','i','s'] \\ he... ...'cow, '',''man!''] \\ \x $\Leftrightarrow$\ ''Have a cow, man!'' \end{gprogram}$

14 Variable Naming Conventions

When we write functions over lists it's convenient to use a consistent variable naming convention. We let
- x, y, z, denote list elements.
- xs, ys, zs, denote lists of elements.
- xss, yss, zss, denote lists of lists of elements.

Recursion Over Lists

15 Recursion on the Tail

Compute the length of a list.
This is called recursion on the tail.

$\begin{program} len :: [Int] -> Int \\ len xs = if xs == [] then \\ \xxx 0\\ \xx else\\ \xxx 1 + len (tail xs) \end{program}$

16 Map Function

Map a list of numbers to a new list of their absolute values.
In the previous examples we returned an Int -- here we're mapping a list to a new list.
This is called a map function.

$\begin{program} abslist :: [Int] -> [Int]\\ abslist xs = if xs == [] then \\ \xxx []\\ \xx else\\ \xxx abs (head xs) : abslist (tail xs) \end{program}$

17 Map Function...

$\begin{program} \redtt{> (abs-list '(1 -1 2 -3 5))} \\ \redtt{ abslist []} \\ ... ...abslist [1]} \\ {[1]} \\ \redtt{ abslist [1,-2]} \\ {[1,2]} \\ \end{program}$

18 Recursion Over Two Lists

listeq xs ys returns True if two lists are equal.

$\begin{program} listeq :: [Int] -> [Int] -> Bool \\ listeq xs ys = if xs==[] \&... ...en \\ \xxx False \\ \xx else \\ \xxx listeq (tail xs) (tail ys) \end{program}$

19 Recursion Over Two Lists...

$\begin{program} \redtt{> listeq [1] [2]}\\ False\\ \redtt{> listeq [1] [1]}\\ ... ...isteq [1] [1,2]}\\ False \\ \redtt{> listeq [1,2] [1,2]}\\ True \end{program}$

20 Append

append xs ys takes two lists as arguments and returns a new list, consisting of the elements of xs followed by the elements of ys.
To do this recursively, we take xs apart on the way down into the recursion, and ``attach'' them to ys on the way up:

$\begin{program} append :: [Int] -> [Int] -> [Int]\\ append xs ys = if xs==[] then\\ \xxx ys\\ \xx else\\ \xxx (head xs) : (append (tail xs) ys) \end{program}$

21 Append...

$\begin{program} \redtt{> append [] []}\\ {[]}\\ \redtt{> append [1] []}\\ {[1... ...\ {[1,2]}\\ \redtt{> append [1,2,3] [4,5,6]} \\ {[1,2,3,4,5,6]} \end{program}$

Arithmetic Sequences

22 Arithmetic Sequences

Haskell provides a convenient notation for lists of numbers where the difference between consecutive numbers is constant.
$\begin{gprogram} \mbox{[1..3]} $\Rightarrow$\ [1,2,3] \\ \mbox{[5..1]} $\Rightarrow$\ [] \end{gprogram}$
A similar notation is used when the difference between consecutive elements is $\neq 1$ : Examples:
$\begin{gprogram} \mbox{[1,3..9]} \xxxx $\Rightarrow$\ [1,3,5,7,9] \\ \mbox{[9... ...row$\ [9,8,7,6,5] \\ \mbox{[9,8..11]} \xxxx $\Rightarrow$\ [] \end{gprogram}$
Or, in general:
$\begin{gprogram}[m,k..n]$\Rightarrow$\ \\ \x [m,m+(k-m)*1,m+(k-m)*2,$\cdots$,n] \end{gprogram}$

23 Arithmetic Sequences...

Or, in English
``m and k are the first two elements of the sequence. All consecutive pairs of elements have the same difference as m and k. No element is greater than n.''
Or, in some other words,
``m and k form a prototype for consecutive element pairs in the list.''
Later in the course we will talk about infinite lists. Haskell has the capability to create infinite arithmetic sequences:
$\begin{gprogram} \mbox{[3..]} \xxx $\Rightarrow$\ [3,4,5,6,7,$\cdots$] \\ \mbox{[4,3..]} \xxx $\Rightarrow$\ [4,3,2,1,0,-1,-2,$\cdots$] \end{gprogram}$

24 Summary

The bracketed list notation [1,2,3] is just an abbreviation for the list contructor notation 1:2:3:[].
Lists can contain anything: integers, characters, tuples, other lists, but every list must contain elements of the same type only.
:, ++, concat, and list comprehensions create lists.
head and tail take lists apart.

25 Summary...

The notation [m..n] generates lists of integers from m to n.
If the difference between consecutive integers is $\neq 1$ , we use the slightly different notation [m,k..n]. The first two elements of the generated list are m and k. The remaining elements are as far appart as m and k.

26 Homework

Which of the following are legal list constructions? First work out the answer in your head, then try it out with the hugs interpreter.

1 : []
1 : [] : []
1 : [1]
[] : [1]
[1] : [1] : []

27 Homework

Show the lists generated by the following Haskell list expressions.

[7..11]
[11..7]
[3,6..12]
[12,9..2]

28 Homework

Write a function getelmt xs n which returns the :th element of a list of integers.
Write a function evenelmts xs which returns a new list consisting of the 0:th, 2:nd, 4:th, ... elements of an integer list xs.

Christian S. Collberg
2005-08-31

CSc 372 - Comparative Programming Languages 6 : Haskell -- Lists

CSc 372 - Comparative Programming Languages
6 : Haskell -- Lists