Exercises week 3: lists and lists comprehensions

0 (*). Defining Functions over Lists

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"

take :: Int -> [a] -> [a]
take n _      | n <= 0 =  []
take _ []              =  []
take n (x:xs)          =  x : take (n-1) xs

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

isPermutation :: Eq a => [a] -> [a] -> Bool

Express suitable properties of the reverse function in the context of permutations.

2 (*). Sorting

Just 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

For example,

sorted [1,2,3,4,5,6,7] True sorted [1,2,3,2,4]> False

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]

insert' 2 [1,3,4] [1,2,3,4]

Define insert' and test it, by QuickChecking the following property:

prop_insert :: Integer -> [Integer] -> Property
prop_insert x xs = sorted xs ==> sorted (insert' x xs)

Now use insert' to define

isort :: Ord a => [a] -> [a]

which sorts any list into order, using the insertion sort method. For example,

isort "hello" "ehllo" isort ["hello","clouds","hello","sky"] ["clouds","hello","hello",";sky"]

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 failsfor this incorrect definition of isort: isort xs = []).

3. Pascal's Triangle

	1
       1 1
      1 2 1
    1  3 3  1
   1 4  6  4 1
  1 5 10 10 5 1
  .............

• 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]

4. Erastosthenes' sieve

Define a function

crossOut :: Int -> [Int] -> [Int]

Now define a (recursive!) function

sieve :: [Int] -> [Int]

Use sieve to construct the list of primes from 2 to 100.

5. Number Games

• 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

• occursIn x xs, which returns True if x is an element of xs.
• allOccurIn xs ys, which returns True if all of the elements of xs are also elements of ys.
• sameElements xs ys, which returns True if xs and ys have exactly the same elements.
• numOccurrences x xs, which returns the number of times x occurs in xs.

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)]

bag "hello"

[('h',1),('e',1),('l',2),('o',1)]

7 Elements and Positions

• positions xs, which converts a list into a list of pairs of elements and their positions. Hint: Make use of the standard function zip.
• 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 (*). List Comprehensions

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 a² + b² = c². Find all Pythagorean triads with a≤b≤c≤100.