Introduction to Functional Programming -- Exercises Week 3: "Lists" | TDA555 / DIT440, LP1, HT2012 |
Home | Schedule | Labs | Exercises | Exam | About | Fire | Forum | TimeEdit | Links | 2011 |
Here are some exercises designed to help you practice programming with lists
and list comprehensions.
You may need the following useful standard functions:
import Listat 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. Good luck!
0 (*). Exercises from the BookDo exercises 7.14 and 7.16 from the book.1. PermutationsA 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 that returns True if its arguments are permutations of each other.
Express suitable properties of the "reverse" function in the context of permutations. 2 (*). SortingJust as keeping a room tidy can make it easier to find things, so keeping information organised inside a computer can make tasks easier to accomplish. For that reason, lists are often kept sorted, with the least element first, and the greatest element last. In this exercise, we develop functions to take an unsorted list and convert it into a sorted one. First of all, we will need to be able to check that lists are sorted. Define a function sorted :: Ord a => [a] -> Bool which returns True if its argument is a sorted list. (The extra type restriction "Ord a =>" is there because it only works for types that have an ordering, i.e. we can use the operations <, >, >=, etc.) For example, Main> sorted [1,2,3,4,5,6,7] The sorting method we will use is called insertion sort -- imagine sorting a collection of magazines by working through an unsorted pile and building a sorted pile, taking each magazine in turn from the unsorted pile, and inserting it into the right place in the sorted one. Clearly, when there are no magazines left in the unsorted pile, then we will have a pile containing all the magazines in the correct order. Each pile will be represented in our program by a list. The first step is to define a function which inserts an element into a sorted list, in the correct position so that the result is still sorted. We call it insert' :: Ord a => a -> [a] -> [a] (yes, insert is a standard function too) and for example, Main> insert' 2 [1,3,4] Define insert and test it, by QuickChecking the following property: prop_insert :: Integer -> [Integer] -> Property Now use insert' to define isort :: Ord a => [a] -> [a] which sorts any list into order, using the insertion sort method. For example, Main> isort "hello" Write and test a QuickCheck property of isort that only holds if isort is a correct sorting function. (In particular, make sure that your property fails for this incorrect definition of isort: isort xs = []). 3. Avoiding DuplicatesIn many situations, lists should not contain duplicate elements. For example, a pack of cards should not contain the same card twice. Define a function duplicates :: Eq a => [a] -> Bool which returns True if its argument contains duplicate elements. Main> duplicates [1,2,3,4,5] 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 Does this property guarantee that removeDuplicates behaves correctly? If not, what is missing? (removeDuplicates is actually a standard function, called nub). 4. Pascal's TrianglePascal'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:
Define a function pascal :: Int -> [Int]so that pascal n computes the nth row of Pascal's triangle. 5. Erastosthenes' sieveEratosthenes' 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]so that 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 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 base case. Use sieve to construct the list of primes from 2 to 100. 6. Number GamesIn these examples we'll investigate the properties of prime numbers in the range 2 to 100. Define functions
7 (*). Occurrences in ListsDefine the following functions, and state their (polymorphic) types:
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 [("a",1), ("b",2)]Define a function bag to convert a list into a bag. For example, bag "hello"should be [('h',1),('e',1),('l',2),('o',1)] 8. Elements and PositionsElements which occur in lists do so at a particular position. For example, 'l' occurs in "hello" at positions 3 and 4. Define functions
9 (*). List ComprehensionsExperiment with the functionpairs :: [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 a^2 + b^2 == c^2Find all Pythagorean triads with a<=b<=c<=100. |