Tute Exercises Week 4

Recursion

Recursion is an important topic so you will need to prepare for this tutorial. Attempt solutions for each of the questions beforehand. In particular, test the expressions from the first question in GHCi and note the results. When developing the functions below, follow the Five Steps and use examples to guide the development process.

Representation of Lists

What are the values of the following expressions and what is wrong with the ones that give errors?

1:[2,3,4]       
1:2:3:4:[]
[1,2,3]:[4..7]  
[1,2,3] ++ [4..7]       
1:['a','b']     
"abc"++"cd"
"a":"bCc"
"a" ++ "bCc"
'a':'b'
'a':"b"
[1,4,7] ++ 4:[5:[]]     
[True,True:[]]  
True:[True,False]
    

Factorial

Write a recursive function fact to compute the factorial of a given positive number (ignore the case of 0 for this exercises).

fact n = 1 * 2 * ... * n

Why is the function fact a partial function? Add an appropriate error case to the function definition.

Generate a List of Integers

Write a recursive function enumFromTo that computes a list of integer numbers in a given range:

enumFromTo m n = [ m, m + 1, ..., n]

This function is an example of so-called generative recursion, where we produce structured data (in this case, a list) from unstructured data (the integer numbers).

Summing a List of Numerals

Write a recursive function sum to compute the sum of a list of numerals:

sum [ x₁, x₂, ..., x_n ] = x₁ + x₂ + ... + x_n

Justify the use of the following type signature:

sum :: Num a => [a] -> a

Here is a list of common mistakes made when defining sum. Discuss what is wrong and why.

• sum x:xs = ...
• sum [x:xs] = ...
• sum [xs] = ...
• forgotten base case

This function is an example of structural recursion; i.e., where recursion proceeds according to the structure of the input data (in this case, a list). Discuss how generative and structural recursion differ.

Removing Odd Numbers

Write a recursive function removeOdd that, given a list of integers, removes all odd numbers from the list, e.g.,

removeOdd [1, 4, 5, 7, 10] = [4,10]

Hint: You can use the function odd :: Int -> Bool, which tests whether a number is odd.