UNIVERSITY OF LONDON (University College London) B.A. DEGREE; B.Sc. DEGREE 1993 COMPUTER SCIENCE B11A: INTRODUCTORY PROGRAMMING I COMPUTER SCIENCE B11A: INTRODUCTORY PROGRAMMING I RESIT PAPER 19 MAY 1993 : 10 to 12.30 Answer THREE Questions. The Use of Electronic Calculators: is NOT Permitted. l.a) What is a higher order function? [3 marks] b) Consider the foilowing function definitions: > sum (x:xs) = plus x (sum xs) > sum [] = 0 > product (x:xs) times x (product xs) > product [] = 1 > plus x y = x + y > times x y = x * y Construct a higher order function, scan , that abstracts sum and product, so that the definitions of each can be rewritten as: > sum xs = scan plus 0 xs > product xs = scan times 1 xs [13 marks] (c) Use the function scan that you have defined to construct a definition of a function to concatenate together a list of lists to form a single list. [7 marks] (d) Explain why the function: > ordered xs = scan (<) True xs will not confirm that a list of integers is ordered. [10 marks] 2(a)Explain the role of types in a strongly typed language such as Miranda. [6 marks] (b)Explain why it might be useful to define type aliases when writing a Miranda program. Give an example of circumstances under which it might be advantageous to define a type alias for a function type. [8 marks] (c)Why will Miranda not allow the following type alias definition? > funny_type == funny_type -> num [7 marks] (d) Consider the following function definition: > funny h = (apply h) (apply h) > where apply h x = h (x x) Why will Miranda not accept this function definition? [12 marks] 3.(a)What are algebraic data types?Give examples of different uses that might be made of them. [5 marks] (b)Define a type structure to represent binary trees in which the nodes of the tree hold number values and the leaves also hold number values. [4 marks] (c)Define a function to determine the height of a tree represented using your type, where the height of a tree is the number of nodes along the longest branch from the root to a leaf. [9 marks] (d) Consider the following function defined for lists: > map_on_tails f [] = [] > map_on_tails f xs = (f xs):map_on_tails f (tl xs) Define an analogous function for trees represented by your type, where a function is applied to every sub-tree within a tree. [11 marks] (e) Define a function which will take a tree and return a tree containing at each node the height of the corresponding sub-tree in the input tree. [4 marks] 4.(a)What is laziness and how does it allow programs to manipulate unbounded data structures? [5 marks] (b) A list of generators is defined to be a list of distinct positive integers. The closure of a list of generators is defined to be the list of all positive integers which can be obtained by multiplying together one or more copies of one or more of the generators.For example , with generators [2,3], the closure will include 2*2*2*3*3, 2, 2*3, 2*2*2, and so on. Suppose a function, closure, has been defined to take a list of generators and produce its closure.Suppose further that the list it produces is not necessarily sorted, but it is desired to find a sorted version.Why will the following definition not produce the sorted closure? > sorted_closure gs = sort (closure gs) [8 marks] (c) Define a function that will produce the closure in sorted order, given the list of generators. Do not use the function closure in your definition. You may assume that the following functions are available, if they are useful to you in defining your function; sort :: [*] -> [*] The function that sorts a list into ascending order. mkset :: [*] -> [*] The function that removes duplicates from a list. [20 marks] 5.(a) What is a recursive function definition? What parts must such a definition have if the function is to terminate? [3 marks] (b) Consider the following definitions: > up 1 = 0 > up x = 1 + down (3*x+l) > down x = 1 + down (x div 2) , x mod 2 = 0 > = up x, otherwise Construct a single recursive function definition that computes the same function as down without relying on the mutual recursion used here. [5 marks] (c) Consider the following definitions: > flip x = 0, x = 0 > = flip (x-1), conditionl x > = 1 + flop x, otherwise > flop x = 1, x = 0 > = flop (x-1), condition2 x > = 2 + flip (x-1), otherwise where it may be assumed that conditionl and condition2 are defined elsewhere. Why is it not possible to remove the mutual recursion in either of these functions in the same way as for down? [8 marks] (d) By considering the various cases: x = 0; conditionl and condition2 are both true for x; only one of the conditions is true for x; neither of the conditions is true for x; define a single recursive function, flap, so that flip and flop can be redefined as follows: > flip x = fst (flap X) > flop x = snd (flap x) [16 marks] [End of Paper]