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:
The function
or :: [Bool] -> Bool
- returns
True
if any element of its argument list isTrue
.and :: [Bool] -> Bool
- returns
True
if every element of its argument list isTrue
.nub :: Eq a => [a] -> [a]
- which removes duplicate elements from a list.
nub
is defined in the standard library module
Data.List
:
you must write at the beginning of any Haskell program that uses it.import Data.List
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.
Good luck!
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,
A possible implementation oftake 5 "Programming in Haskell is fun!" = "Progr"
take
is
Use this definition oftake :: Int -> [a] -> [a] take n _ | n <= 0 = [] take _ [] = [] take n (x:xs) = x : take (n-1) xs
take
as a guide to
implement the prelude functions drop
and splitAt
.
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?
1. Permutations
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
that returnsisPermutation :: Eq a => [a] -> [a] -> Bool
True
if its arguments are permutations of each other.
Express suitable properties of the reverse
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 function
which returnsduplicates :: Eq a => [a] -> Bool
True
if its argument contains duplicate elements.
duplicates [1,2,3,4,5]
Falseduplicates [1,2,3,2]
True
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
which returns a list containing the same elements as its argument, but without duplicates. Test it using the following property:removeDuplicates :: Eq a => [a] -> [a]
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,
called nub
).
3. Pascal's Triangle
Pascal's triangle is a triangle of numbers1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 .............computed as follows:
- 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
so thatpascal :: 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
so thatcrossOut :: Int -> [Int] -> [Int]
crossOut
m ns
removes all multiples of m from ns. Try to not
implement crossOut
recursively,
but use a list comprehension instead!
Now define a (recursive!) function
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 base case.sieve :: [Int] -> [Int]
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- 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:occursIn x xs
, which returnsTrue
ifx
is an element ofxs
.allOccurIn xs ys
, which returnsTrue
if all of the elements ofxs
are also elements ofys
.sameElements xs ys
, which returnsTrue
ifxs
andys
have exactly the same elements.numOccurrences x xs
, which returns the number of timesx
occurs inxs
.
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 set.
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[("a",1), ("b",2)]
bag
to convert a list into a bag. For example,
should bebag "hello"
[('h',1),('e',1),('l',2),('o',1)]
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 functionspositions xs
, which converts a list into a list of pairs of elements and their positions. Hint: Make use of the standard functionzip
.firstPosition x xs
, which returns the first position at which x occurs in xs.remove1st x xs
, which removes the first occurrence of x from xs. For example,remove1st 'l' "hello" == "helo"
remove n x xs
, which removes the first n occurrences of x from xs.
8 (*). More List Comprehensions
Experiment with the functionand see what it does.pairs :: [a] -> [b] -> [(a,b)] pairs xs ys = [(x,y) | x<-xs, y<-ys]
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.