COMP1011 Exercises for Week 06
Computing 1A 05s2 Last updated Tue 19 Jul 2005 14:37

Tute Exercises Week 6

Patterns of Recursion & Higher-Order Functions


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], []]

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"

Implement delete using the higher-order function map instead of explicit recursion.