UNIVERSITY COLLEGE LONDON University of London EXAMINATION FOR INTERNAL STUDENTS For the following qualifications M.Sc , M.Sc / Coll Dip COURSE CODE : COMPOD16 TITLE OF EXAMINATION : D16: Functional Programming DATE : 05-MAY-95 TIME : 14.30 TIME ALLOWED : 2 hours 30 minutes Answer Question 1 and any TWO other questions. The use of Electronic Calculators is NOT permitted. You may find the following definitions useful throughout this paper: fun id x = x fun K x y = x fun C f x y = f y x fun cons a b = (a :: b) fun plus x y = x + y fun length nil = 0 | length (front :: rest) = 1 + (length rest) fun append a nil = a | append nil b = b | append (front :: rest) b = front :: (append rest b) fun reduce f def nil = def | reduce f def (front :: rest) = f front (reduce f def rest) fun accumulate f acc nil = acc | accumulate f acc (front :: rest) = accumulate f (f acc front) rest fun filter pred nil = nil | filter pred (front :: rest) = if (pred front) then front :: (filter pred rest) else filter pred rest 1.a) What is a recursive function? Give example function definitions in SML for both a stack recursive function and an accumulative recursive function. For each function, provide an example application and give a hand evaluation of that application. [5 Marks] (b) What is a recursive type? Give an example of a built-in recursive type in SML. How can you define your own recursive type? Give an exarnple in SML of a user-defined type which is recursive. [4 Marks] (c) Evaluate each of the following SML expressions. If you think that an expression gives an error, say why (if there is more than one error in an expression, explain all of them): [ [ ] ] :: [ [ [ ] ] ] [ [ [ ] ] ] :: [ [ ] ] [ ] : [ ] : [ ] ((3-3)=O) andalso ((23 div 0) = 0) ((3-3)=O) orelse ((23 div 0) = 0) if (3 < 5 < 27) then 25 else false (if true then 3 else 5) 5 (if false then id else (K 3)) 5 [8 Marks] (d) Explain, with examples, what is meant by the following terms: higher-order function currying partial application Explain how the above terms are related. [8 Marks] [Total 25] 2. Here are three versions of a function which takes a list of items and produces a list with the same items in reverse order: (* auxiliary functions: *) fun rcons a f b = f (a :: b) (* three versions of reverse: *) fun rev1 nil = nil | rev1 (front :: rest) = append (rev1 rest) [front] fun rev2 items = reduce rcons id items nil val rev3 = accumulate (C cons) nil Add type constraints to rev1, rev2 and rev3 so that input and output types are completely defined (use polytypes where appropriate to give the most general type). Provide hand evaluations for the following five applications: (rev1 [1,2,3,4]) (rev2 [1,2,3,4]) (rev3 (1,2,3,4]) Which of the three versions is the slowest (i.e. takes the most evaluation steps)? In terms of the length n of an arbitrary input list, how many evaluation steps are required for each version? Explain why the slowest version takes so many evaluation steps. [Total 25 Marks] 3. "Functional Languages are ideally suited for programming parallel computers". Discuss this statement with reference to the following: - Graph Reduction - Referential Transparency - Implicit Parallelism [Total 25 Marks] 4. A double-ended queue is similar to a list, except that it is possible to take the head or the tail of either end. For example, the function hdL will return the leftmost element whereas hdR will return the rightmost element. Provide an abstype for a double-ended queue, including definitions (with types) for the following functions: hdL (which gives the leftmost element) hdR (which gives the rightmost element) tlL (which gives the list minus the leftmost element) tlR (which gives the list minus the rightmost element) consL (which puts an element on the left end) consR (which puts an element on the right end) nildeq (this value is the empty double-ended queue) isemptydeq (this tests whether its argument is nildeq) Write a function called insertdeq which accepts two parameters: a double-ended queue of integers and an integer. The function should insert the integer into the double-ended queue so that negative numbers are on the left (in ascending order towards the centre) and positive numbers are on the right (in ascending order towards the centre). In the centre of the double-ended queue there should always be a zero. Your function should ignore insertions of the integer zero unless the queue is empty. Thus, the double-ended queue should look something like ths: [-32,-20,-3,0,29,3,2,1 ] Hint: write your function using the abstype interface functions given above.'insertdeq' is not an interface function and therefore should not know how a double-ended queue is implemented. [Total 25 Marks] 5. (a) What is the type of the following expression and what does it do? (reduce plus 0) o (reduce (cons o (length o (c cons nil))) nil) [6 Marks] (b) The following function 'foldiftrue' reduces only those elements of a list which satisfy a given predicate: fun foldiftrue pred ff def nil = def | foldiftrue pred ff def (front :: rest) = if (pred front) then ff front (foldiftrue pred ff def rest) else foldiftrue pred ff def rest Add type constraints to foldiftrue so that input and output types are completely defined (use polytypes where appropriate to give the most general type). Rewrite foldiftrue in terms of reduce and filter. [10 Marks] (c) What is the most general type of each of the following functions: fun lotsoffun a b f x = ((a f) o (b f)) x fun morefun nil j acc = acc | morefun f nil acc = acc | morefun (x :: xs) (y :: ys) acc = morefun xs ys (x y acc) fun mysterious nil y z = 42.0 + z | mysterious (front::rest) y z = mysterious rest y ((front o y) z) [9 Marks] [Total 25 Marks] [END OF PAPER]