Exercises for Week 3: Lists and List Comprehensions
Here are some exercises designed to help you practice programming with lists
and list comprehensions.
You may need the following useful standard functions:
or :: [Bool] -> Bool
True if any element of its argument list is
and :: [Bool] -> Bool
True if every element of its argument list is
nub :: Eq a => [a] -> [a]
- which removes duplicate elements from a list.
nub is defined in the standard library module
you must write
import Data.List at the beginning of
any Haskell program that uses it.
If you do not have time to do all these exercises, don't worry.
The exercises are intended to provide enough work to keep the most
experienced students busy. If you do all exercises marked with an (*) you have
probably understood this week's material.
0 (*). Defining Functions over Lists
(Based on Thompson's book, Chapter 7)
A. The prelude defines a function
take which is
used to take a given number of elements from a list. For example,
take 5 "Programming in Haskell is fun!" = "Progr"
A possible implementation of
take :: Int -> [a] -> [a]
take 0 _ = 
take _  = 
take n (x:xs) | n > 0 = x : take (n-1) xs
take _ _ = error "PreludeList.take: negative argument"
Use this definition of
take as a guide to
implement the prelude functions
B. How would you define a function
zip3 which zips
together three lists? Try to write a recursive definition and also
one which uses
zip instead; what are the advantages and
disadvantages of the two definitions?
A permutation of a list is another list with the same elements,
but in a possibly different order. For example, [1,2,1] is a permutation
of [2,1,1], but not of [1,2,2].
Write a function
isPermutation :: Eq a => [a] -> [a] -> Bool
True if its arguments are permutations of each other.
Express suitable properties of the
function in the context of permutations.
2. Avoiding Duplicates
(repeated from last week)
In many situations, lists should not contain duplicate elements. For
example, a pack of cards should not contain the same card twice. Define a
duplicates :: Eq a => [a] -> Bool
True if its argument contains duplicate elements.
Hint: the standard function
elem, which tests whether
an element occurs in a list, is helpful here.
One way to ensure a list contains no duplicates is to start with a
list that might contain duplicate elements, and remove them.
Define a function
removeDuplicates :: Eq a => [a] -> [a]
which returns a list containing the same elements as its argument, but
without duplicates. Test it using the following property:
prop_duplicatesRemoved :: [Integer] -> Bool
prop_duplicatesRemoved xs = not (duplicates (removeDuplicates xs))
Does this property guarantee that removeDuplicates behaves correctly?
If not, what is missing?
removeDuplicates is actually a standard function,
3. Pascal's Triangle
Pascal's triangle is a triangle of numbers
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
computed as follows:
Pascal's triangle is related to the binomial theorem.
- The first row just contains a 1.
- The following rows are computed by adding together adjacent numbers in
the row above, and adding a 1 at the beginning and at the end.
Define a function
pascal :: Int -> [Int]
pascal n computes the nth
row of Pascal's triangle.
4. Erastosthenes' sieve
Eratosthenes' sieve is an ancient method for finding prime numbers. Start by
writing out all the numbers from 2 to (say) 100. The first number (2) is
prime. Now cross out all multiples of 2. The first remaining number (3) is
also prime. Cross out all multiples of 3. The first remaining number (5) is
also prime... and so on. When no numbers remain, you have found all the prime
numbers in the range you started with.
Define a function
crossOut :: Int -> [Int] -> [Int]
crossOut m ns
removes all multiples of m from ns. Try to not
but use a list comprehension instead!
Now define a (recursive!) function
sieve :: [Int] -> [Int]
which applies Eratosthenes' sieve to the list of numbers it is given, and
returns a list of all the prime numbers that it found. This is a recursive
function with a list as its argument, so you must see to it that the
list gets smaller in each recursive call. Take an empty argument list as your
Use sieve to construct the list of primes from 2 to 100.
5. Number Games
In these examples we'll investigate the properties of prime numbers in the
range 2 to 100. Define functions
It is hypothesized that every even number greater than two can be expressed as
the sum of two primes. For example, 4 = 2+2, 6 = 3+3, 8 = 3+5. Is this true
for all even numbers in the range 4 to 100?
- To test whether n is a prime (in the range 2 to 100).
- To test whether n is a sum of two primes (in the range 2 to 100).
6 (*). Occurrences in Lists
Define the following functions, and state their (polymorphic) types:
In the implementations of the above functions, try to not use recursion, but
use a list comprehension instead!
occursIn x xs,
x is an element
allOccurIn xs ys,
True if all of the elements of
are also elements of
sameElements xs ys,
have exactly the same elements.
numOccurrences x xs,
which returns the number of times
x occurs in
In some ways, lists are like sets: both are collections of elements. But the
order of elements in a list matters, while it does not matter in a set, and
the number of occurrences in a list matters, while it does not matter in a
The concept of a bag is something between a list and a set: the
number of occurrences matters, but the order of elements does not. One way to
represent a bag is a list of pairs of values and the number of times the value
occurs: for example
Define a function
bag to convert a list into a bag. For example,
7 Elements and Positions
Elements which occur in lists do so at a particular position. For example, 'l'
occurs in "hello" at positions 3 and 4. Define functions
which converts a list into a list of pairs of elements and
their positions. Hint: Make use of the standard function
firstPosition x xs,
which returns the first position at which x occurs in xs.
remove1 x xs,
which removes the first occurrence of x from xs. For
remove1 'l' "hello" == "helo"
remove n x xs,
which removes the first n occurrences of x from xs.
8 (*). More List Comprehensions
Experiment with the function
pairs :: [a] -> [b] -> [(a,b)]
pairs xs ys = [(x,y) | x<-xs, y<-ys]
and see what it does.
A Pythagorean triad is a triple of integers
(a,b,c) such that
a2 + b2 = c2.
Find all Pythagorean triads with a≤b≤c≤100.