COMP1011 Exercises for Week 06
Computing 1A 05s2 Last updated Tue 19 Jul 2005 14:37
Mail cs1011@cse.unsw.edu.au

Tute Exercises Week 6

Patterns of Recursion & Higher-Order Functions

Patterns

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.

Nested lists & accumulators

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

Delete characters from a list - revisted

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.

Substitute characters in a list - revisited

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.