## 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 is`True`

.

and::[Bool]->Bool- returns
`True`

if every element of its argument list is`True`

.

nub::Eqa=>[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.importData.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 oftake5 "Programming in Haskell is fun!"="Progr"

`take`

is
Use this definition oftake::Int->[a]->[a]taken_|n<=0=[]take_[]=[]taken(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::Eqa=>[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 (*). 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

which returns True if its argument is a sorted list. (The extra type restrictionsorted::Orda=>[a]->Bool

**Ord** `a` **=>**

is there because it only works for types that have an
ordering, i.e. we can use the operations <, >, >=, etc.)
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

(yes,insert'::Orda=>a->[a]->[a]

`insert`

is a standard function too) and for example,
`insert' 2 [1,3,4]`

[1,2,3,4]

Define `insert'`

and test it, by QuickChecking the following property:

prop_insert::Integer->[Integer]->Propertyprop_insertxxs=sortedxs==>sorted(insert'xxs)

Now use insert' to define

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

### 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

`n`th 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 asieve::[Int]->[Int]

*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.

### 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 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

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 functions`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

Experiment with the functionand see what it does.pairs::[a]->[b]->[(a,b)]pairsxsys=[(x,y)|x<-xs,y<-ys]

A Pythagorean triad is a triple of integers
(`a`,`b`,`c`) such that
`a`^{2} + `b`^{2} = `c`^{2}.
Find all Pythagorean triads with `a`≤`b`≤`c`≤100.