COMP1011 Exercises for Week 06 | |
---|---|
Computing 1A 05s2 |
Last updated
Tue 19 Jul 2005 14:37
Mail cs1011@cse.unsw.edu.au |
List the templates of the patterns of "structure-preserving structural recursion", "structure-collapsing/mutating structural recursion", "structural recursion over natural numbers", and "generative recursion". Give examples of functions for each pattern.
Two variations on the standard patterns of recursion are functions over
nested structures (such as nested lists) and functions using an
accumulator. The function largest
that, given a list of
lists of natural numbers, determines the largest number in each
sublist combines these two variations. It's type is largest ::
[[Int]] -> [Int]
and it might be used as follows:
Tut06> largest [[1,2,3], [2,3,1], [4,0], []] [3,3,4,0]
Use a local function (in a where
clause) to realise the
inner recursion. This local functions should maintain the currently
largest value in an accumulator (i.e., extra argument). For the purpose
of this function, we assume that the largest number in an empty list is
0
.
Reconsider the recursive function delete
from last week
that given a string and a character, returns the string with all
occurances of the character removed.
For example:
Tut06> delete 'x' "x-files sux" "-files su"
This week, implement delete
using the higher-order function
filter
instead of explicit recursion.
Reconsider the substitute
from last week, which substitutes
a given character with another character (instead of deleting it):
Tut06> substitute 'e' 'i' "eigenvalue" "iiginvalui"
Implement delete
using the higher-order function
map
instead of explicit recursion.