Functional Programming -- Exercises 3 | TDA452 & DIT142 | LP2 | HT2011 | [Home] |

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, 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 :: Eq a => [a] -> [a], which removes duplicate elements from a list.

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!

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

that returns True if its arguments are permutations of each other.

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

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

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

which returns True if its argument contains duplicate elements.

Main> duplicates [1,2,3,4,5]

False

Main> duplicates [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

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, called nub).

1 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

pascal :: Int -> [Int]so that pascal n computes the nth row of Pascal's triangle.

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

Use sieve to construct the list of primes from 2 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).

- 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)]Define a function

bag "hello"should be

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

- 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.
- remove1 x xs, which removes the first occurrence of x from xs. For example, remove1 'l' "hello" = "helo"
- remove n x xs, which removes the first n occurrences of x from xs.

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

a^2 + b^2 == c^2Find all Pythagorean triads with a<=b<=c<=100.