CSc 372 - Comparative Programming Languages
13 : Haskell -- List Comprehension

Christian Collberg

Department of Computer Science

University of Arizona

1 List Comprehensions

Haskell has a notation called list comprehension (adapted from mathematics where it is used to construct sets) that is very convenient to describe certain kinds of lists. Syntax:
$\begin{gprogram}[ {\em expr} \vert {\em qualifier}, {\em qualifier}, $\cdots$\ ] \end{gprogram}$
In English, this reads:
``Generate a list where the elements are of the form expr, such that the elements fulfill the conditions in the qualifiers.''
The expression can be any valid Haskell expression.
The qualifiers can have three different forms: Generators, Filters, and Local Definitions.

2 Generator Qualifiers

Generate a number of elements that can be used in the expression part of the list comprehension. Syntax:
$\begin{gprogram} pattern <- list\_expr \end{gprogram}$
The pattern is often a simple variable. The list_expr is often an arithmetic sequence.

$\begin{gprogram} \mbox{[n \vert n<-[1..5]]} $\Rightarrow$\ [1,2,3,4,5] \\ \\ \... ...ox{[(n,n*n) \vert n<-[1..3]]} $\Rightarrow$\ [(1,1),(2,4),(3,9)] \end{gprogram}$

3 Filter Qualifiers

A filter is a boolean expression that removes elements that would otherwise have been included in the list comprehension. We often use a generator to produce a sequence of elements, and a filter to remove elements which are not needed.

$\begin{gprogram} \mbox{[n*n \vert n<-[1..9],even n]} $\Rightarrow$\ [4,16,36,64]... ...ox{[(n,n*n) \vert n<-[1..3],n<n*n]} $\Rightarrow$\ [(2,4),(3,9)] \end{gprogram}$

4 Local Definitions

We can define a local variable within the list comprehension. Example:

$\begin{gprogram} \xx \mbox{[n*n \vert n = 2]} $\Rightarrow$\ [4] \end{gprogram}$

5 Qualifiers

Earlier generators (those to the left) vary more slowly than later ones. Compare nested for-loops in procedural languages, where earlier (outer) loop indexes vary more slowly than later (inner) ones.

Pascal:
$\begin{gprogram} for i := 1 to 9 do \\ \x for j := 1 to 3 do \\ \xx print (i, j) \end{gprogram}$

Haskell:
$\begin{gprogram}[(i,j) \vert i<-[1..9], j<-[1..3]] $\Rightarrow$\ \\ \xx [\x (1... ...(2,1),(2,2),(2,3),\\ \xxxx $\cdots$\ \\ \xxx (9,1),(9,2),(9,3)] \end{gprogram}$

6 Qualifiers...

Qualifiers to the right may use values generated by qualifiers to the left. Compare Pascal where inner loops may use index values generated by outer loops.

Pascal:
$\begin{gprogram} for i := 1 to 3 do \\ \x for j := i to 4 do \\ \xx print (i, j) \end{gprogram}$

Haskell:
$\begin{gprogram}[(i,j) \vert i<-[1..3], j<-[i..4]] $\Rightarrow$\ \\ \xx [\x (1... ...x{[n*n \vert n<-[1..10], even n]} $\Rightarrow$\ [4,16,36,64,100] \end{gprogram}$

7 Example

Define a function doublePos xs that doubles the positive elements in a list of integers.

In English:

``Generate a list of elements of the form 2*x, where the x:s are the positive elements from the list xs.

In Haskell:
$\begin{gprogram} doublePos :: [Int] -> [Int] \\ doublePos xs = [2*x \vert x<-xs, x>0] \\ \\ \redtt{> doublePos [-1,-2,1,2,3]} \\ \x [2,4,6] \end{gprogram}$

Note that xs is a list-valued expression.

8 Example

Define a function spaces n which returns a string of n spaces.

Example:
$\begin{gprogram} \redtt{> spaces 10} \\ \x ''\ \ \ \ \ \ \ \ \ \ '' \end{gprogram}$

Haskell:
$\begin{gprogram} spaces :: Int -> String \\ spaces n = [' ' \vert i <- [1..n]] \end{gprogram}$

Note that the expression part of the comprehension is of type Char.
Note that the generated values of i are never used.

9 Example

Define a function factors n which returns a list of the integers that divide n. Omit the trivial factors 1 and n.

Examples:
$\begin{gprogram} factors 5 $\Rightarrow$\ [] \\ factors 100 $\Rightarrow$\ [2,4,5,10,20,25,50] \end{gprogram}$

In Haskell:
$\begin{gprogram} factors :: Int -> [Int] \\ factors n = [i \vert i<-[2..n-1], n \lq mod\lq i == 0] \end{gprogram}$

10 Example

Pythagorean Triads:

Generate a list of triples such that and $x,y,z \leq n$ .

$\begin{gprogram} triads n = [(x,y,z)\vert \\ \x x<-[1..n], y<-[1..n], z<-[1..n]... ... == z\verb+^+2] \\ \\ triads 5 $\Rightarrow$\ [(3,4,5),(4,3,5)] \end{gprogram}$

11 Example...

We can easily avoid generating duplicates:

$\begin{gprogram} triads' n = [(x,y,z)\vert \\ \x x<-[1..n], y<-[x..n], z<-[y..n... ...z\verb+^+2] \\ \\ triads' 11 $\Rightarrow$\ [(3,4,5), (6,8,10)] \end{gprogram}$

12 Example - Making Change

Write a function change that computes the optimal (smallest) set of coins to make up a certain amount.

Defining available (UK) coins:
$\begin{gprogram} type Coin = Int \\ coins :: [Coin] \\ coins = reverse (sort [1,2,5,10,20,50,100]) \end{gprogram}$

Example:
$\begin{gprogram} \redtt{> change 23} \\ \x [20,2,1] \\ \redtt{> coins} \\ \x ... ...> all\_change 4} \\ \x [[2,2],[2,1,1],[1,2,1],[1,1,2],[1,1,1,1]] \end{gprogram}$

13 Example - Making Change...

all_change returns all the possible ways of combining coins to make a certain amount.
all_change returns shortest list first. Hence change becomes simple:

$\begin{gprogram} change amount = head (all\_change amount) \end{gprogram}$

all_change returns all possible (decreasing sequences) of change for the given amount.

$\begin{gprogram} all\_change :: Int -> [[Coin]] \\ all\_change 0 = [[]] \\ all... ... \xx c<-coins, amount>=c, \\ \xx cs<-all\_change (amount - c) ] \end{gprogram}$

14 Example - Making Change...

all_change works by recursion from within a list comprehension. To make change for an amount amount we
1. Find the largest coin $\tc{c} \leq \tc{amount}$ : c<-coins,amount>=c.
2. Find how much we now have left to make change for: amount - c.
3. Compute all the ways to make change from the new amount: cs<-all_change (amount - c)
4. Combine c and cs: c:cs.

15 Example - Making Change...

If there is more than one coin $\tc{c} \leq \tc{amount}$ , then c<-coins,amount>=c will produce all of them. Each such coin will then be combined with all possible ways to make change from amount - c.
coins returns the available coins in reverse order. Hence all_change will try larger coins first, and return shorter lists first.

$\begin{gprogram} all\_change :: Int -> [[Coin]] \\ all\_change 0 = [[]] \\ all... ... \xx c<-coins, amount>=c, \\ \xx cs<-all\_change (amount - c) ] \end{gprogram}$

16 Summary

A list comprehension [e|q] generates a list where all the elements have the form e, and fulfill the requirements of the qualifier q. q can be a generator x<-list in which case x takes on the values in list one at a time. Or, q can be a a boolean expression that filters out unwanted values.

17 Homework

Show the lists generated by the following Haskell list expressions.

$\begin{gprogram}[n*n \vert n<-[1..10],even n] \end{gprogram}$
$\begin{gprogram}[7 \vert n<-[1..4]] \end{gprogram}$
$\begin{gprogram}[ (x,y) \vert x<-[1..3], y<-[4..7]] \end{gprogram}$
$\begin{gprogram}[ (m,n) \vert m<-[1..3], n<-[1..m]] \end{gprogram}$
$\begin{gprogram}[j \vert i<-[1,-1,2,-2], i>0, j<-[1..i]] \end{gprogram}$
$\begin{gprogram}[a+b \vert (a,b)<-[(1,2),(3,4),(5,6)]] \end{gprogram}$

18 Homework

Use a list comprehension to define a function neglist xs that computes the number of negative elements in a list xs.

Template:
$\begin{gprogram} neglist :: [Int] -> Int \\ neglist n = $\cdots$ \end{gprogram}$

Examples:
$\begin{gprogram} \redtt{> neglist [1,2,3,4,5]} \\ \x 0 \\ \redtt{> neglist [1,-3,-4,3,4,-5]} \\ \x 3 \end{gprogram}$

19 Homework

Use a list comprehension to define a function gensquares low high that generates a list of squares of all the even numbers from a given lower limit low to an upper limit high.

Template:
$\begin{gprogram} gensquares :: Int -> Int -> [Int] \\ gensquares low high = [ $\cdots$\ \vert $\cdots$\ ] \end{gprogram}$

Examples:
$\begin{gprogram} \redtt{> gensquares 2 5} \\ \x [4, 16] \\ \redtt{> gensquares 3 10} \\ \x [16, 36, 64, 100] \end{gprogram}$

Christian S. Collberg
2005-09-19

CSc 372 - Comparative Programming Languages 13 : Haskell -- List Comprehension

CSc 372 - Comparative Programming Languages
13 : Haskell -- List Comprehension