COMP1011 Exercises for Week 04 | |
---|---|
Computing 1A 05s2 |
Last updated
Tue 19 Jul 2005 14:37
Mail cs1011@cse.unsw.edu.au |
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.
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]
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.
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).
Write a recursive function sum
to compute the sum of a list
of numerals:
sum [
x_{1},
x_{2},
...,
x_{n}] =
x_{1}+
x_{2}+
...+
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] = ...
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.
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.