TDA 452
DIT 142
HT 2017

Functional Programming 2017
Exercises for Week 3

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:

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.
The function nub is defined in the standard library module Data.List: you must write
import Data.List
at 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 (*). 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,

take 5 "Programming in Haskell is fun!" = "Progr"
A possible implementation of take is
take :: Int -> [a] -> [a]
take n _      | n <= 0 =  []
take _ []              =  []
take n (x:xs)          =  x : take (n-1) xs
Use this definition of 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

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

duplicates :: Eq a => [a] -> Bool
which returns True if its argument contains duplicate elements.
duplicates [1,2,3,4,5]
duplicates [1,2,3,2]

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

3. Pascal's Triangle

Pascal's triangle is a triangle of numbers
       1 1
      1 2 1
    1  3 3  1
   1 4  6  4 1
  1 5 10 10 5 1
computed as follows: Pascal's triangle is related to the binomial theorem.

Define a function

pascal :: Int -> [Int]
so that 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

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.

5. Number Games

In these examples we'll investigate the properties of prime numbers in the range 2 to 100. Define functions It is hypothesized that every even number greater than two can be expressed as the sum of two primes. For example, 4 = 2+2, 6 = 3+3, 8 = 3+5. Is this true for all even numbers in the range 4 to 100?

6 (*). Occurrences in Lists

Define the following functions, and state their (polymorphic) types: In the implementations of the above functions, try to not use recursion, but use a list comprehension instead!

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

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

8 (*). More List Comprehensions

Experiment with the function
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 a2 + b2 = c2. Find all Pythagorean triads with abc≤100.