22 07 16

Page 1

Principles of Programming Languages, 2016.07.22 FAMILY NAME ________________________ GIVEN NAME ________________________ DID YOU PRESENT A SMALL PROJECT? YES [] NO [] Notes: - Total available time: 2h. - You may use any written material you need, and write in Italian, if you prefer. - You cannot use electronic devices during the exam. Exercise 1, Scheme (9 pts) 1) Define the iterate function, with two parameters f and v, that returns the infinite list (v f(v) f2(v) ... fn(v) ...). Hint: use delay and force, as seen in class. 2) Define take, like in Haskell, to get items out of an infinite list. E.g. (take 10 (iterate (lambda (x) (+ x 1)) 0)) should return (0 1 2 3 4 5 6 7 8 9) Exercise 2, Haskell (16 pts) 1) Define iter which works like iterate in the previous exercise. Note that Haskell already has iterate, but of course you cannot use it to define iter. 2) Consider this data type: data Rf a b = Rf [a] (a -> b). Its first component is a list of values representing the domain of the second argument (a function). This means that the values returned from the function are meaningful only if its parameter is taken from the first list. Is it possible to derive Show? Why? If the answer is no, make Rf an instance of Show, so that e.g. Rf [1,2,3] (+1) is represented as: “[1,2,3]-->[2,3,4]” (notice that [2,3,4] is the image of (+1) on the given domain). 3) Make (Rf a) an instance of Functor. 4) The Rf data type is used to represent functions. Given two Rf input values, say of type (Rf a b) and (Rf b c), define a way to compose functions, i.e. write a function compose which returns a value of type (Rf a c). Write the type of compose. E.g. compose (Rf [1,2,3] (+2)) (Rf [2,3,5] (*2)) should be Rf [1,3] (\x -> (x+2)*2). Exercise 3, Prolog (8 pts) Define a predicate called sumoftwo,…