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.