22 09 15

Page 1

Principles of Programming Languages 2015.09.22 Notes • NAME: __________________________________ • Did you present a small project? YES / NO • Total available time: 2h. • Y ou may use any written material you need. • Y ou cannot use computers or phones during the exam. 1 Scheme 1.1 Co-sublist (5 points) Consider a list(x0x1 . . . xn). Its sublist from i to j is the list(xi, xi+1 . . . xj). Define the procedure co-sublist which, given a list L and two indexes i and j, i ≤ j, returns the list of ordered elements of L that are not in the sublist from i to j. Y ou cannot use procedures with side effects in your code (e.g.set!). E.g. (co-sublist ’(1 2 3 4 5 6) 1 3) should be (1 5 6) . 1.2 Fancy Sublist (5 points) Define this construct: (subl e1e2 . . . -> ei . . . ej <- ej+1 . . . en); its evalutation returns the sublist (ei . . . ej). E.g. (subl 1 -> 2 3 4 <- 5 6) should be (2 3 4) . 2 Haskell 2.1 Type definition and accessor (3 points) Define the Bilist data-type, which is a container of two homogeneous lists. Define an accessor for Blist, called bilist_ref, that, given an index i, returns the pair of values at position i in both lists. E.g. bilist_ref (Bilist [1,2,3] [4,5,6]) 1 should return (2,5). 2.2 Oddeven (5 points) Define a function, called oddeven, that is used to build a Bilist x y from a simple list. oddeven takes all the elements at odd positions and put them in y, while all the other elements are put in x, maintaining their order. Y ou may assume that the given list has an even length (or 0). Write also all the types of the functions you define. E.g. oddeven [1,2,3,4] must be Bilist [1,3] [2,4] . 1 2.3 Inverse oddeven (5 points) Define an inverse of oddeven, e.g. inv_oddeven $ oddeven [1,2,3,4] must be [1,2,3,4]. Write also all the types of the functions you define. 2.4…