CA215 Languages and Computability

Functional Programming Lab 4: Defining Functions on Lists

Aim: The aim of this class is to help you learn to define your own functions on lists, especially using recursion and list patterns.

1. Product of the Elements of a List

Define a function myProduct :: [Int] -> Int which multiplies together all the elements of a list of integers.

2. Converting a String to Upper Case

Haskell has a predefined function

toUpper :: Char -> Char

which converts single lower case letters to upper case. This function has to be imported from Char by including the following within your script:

import Char(toUpper)

Experiment with this function to find out exactly how it behaves (i.e. try it on a variety of characters). Define a function

stringToUpper :: String -> String

that converts all the lower case letters in a string to upper case, and leaves the others unchanged (remember that in Haskell the type String is a synonym for [Char]).

Note that Haskell has a predefined function

isAlpha :: Char -> Bool

which returns True if the character is an alphabetic character and False otherwise. This function has to be imported from Char by including the following within your script:

import Char(isAlpha)

3. Adding Two Polynomials

A polynomial in a single variable can be represented rather simply by a list of its coefficients. For example:

[1,7,5,2] represents 2x³ + 5x² + 7x + 1

[42,2,1] represents x² + 2x + 42

[-3,0,0,0,1] represents x⁴ - 3

[0,-2,0,4] represents 4x³ - 2x

Notice how the list index for each element corresponds to the exponent of the term.

Define a type synonym Poly for this representation. Two polynomials can be summed by adding the coefficients of corresponding terms. For example, the sum of 2x³ + x² + 1 and 3x⁴ + 4x² - 7 is 3x⁴ + 2x³ + 5x² - 6.

Define a Haskell function

sumPoly :: Poly -> Poly-> Poly

that sums two polynomials that are represented as above. Take care with the case of polynomials with different degrees. For example:

> sumPoly [1,7,5,2] [42,2,1]

[43,9,6,2]

> sumPoly [-3,0,0,0,1] [1,7,5,2]

[2,7,5,2,1]

> sumPoly [0,-2,0,4] [1,7,5,2]

[1,5,5,6]

4. Evaluating a Polynomial

Define a Haskell function

evalPoly :: Int -> [Int] -> Int

which, given a polynomial and a value for x, will calculate the value of the polynomial for that value of x. For example:

> evalPoly 3 [1,7,5,2]

121

> evalPoly (-2) [0,-2,0,4]

28

> evalPoly 4 (sumPoly [0,-2,0,4] [1,7,5,2])

485

There are many ways to do this, but an identity that you may find helpful is the following:

a_nxⁿ + ... + a₂x² + a₁x + a₀ = a₀ + x(a₁ + x(a₂ + x(... a_n) ...) )

For example:

2x³ + 5x² + 7x + 1 is equal to

1 + 7x + 5x² +2x³ which is also equal to

1 + x(7 + x(5 + x(2))) and is represented by

[1,7,5,2]