12 02 15 1

Page 1

Principles of Programming Languages 2015.02.12 Notes • 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 Split (4 points) Define a tail-recursive function split, which, given a list L and a number n, returns a vector of two elements: the prefix sublist of L, with elements up to the n-th, and the remaining suffix. E.g. > (split ’(0 1 2 3 4) 2) ’#((0 1) (2 3 4)) 1.2 Factors (6 points) Use split to define the function 3-factors, which, given a list L, returns all the possible contiguous sublists A, B, C, such that (equal? L (append A B C)) . A,B,C, cannot be empty. E.g. > (3-factors ’(0 1 2 3 4)) ’(((0 1 2) (3) (4)) ((0 1) (2 3) (4)) ((0 1) (2) (3 4)) ((0) (1 2 3) (4)) ((0) (1 2) (3 4)) ((0) (1) (2 3 4))) 2 Haskell 2.1 Split (3 points) Implement split in Haskell, noting that the Scheme version returns a vector: is there a more suitable type in Haskell for the job? If so, use it. 1 2.2 Factors (7 points) Implement 3-factors in Haskell, noting that the Scheme version returns a list of lists: is there a more suitable type in Haskell for the job? If so, use it. 2.3 Types (2 points) Declare all the types of the defined functions. 3 Prolog 3.1 BetweenAB (5 points) Define a predicate betweenAB, which, given a list L, checks if all the atoms a in L are at the beginning, and all the atoms b are at the end of L. E.g. betweenAB([a,a,c,c,d,b,b,b]) is true. 3.2 DeepBetweenAB (6 points) Define a “deep” version of betweenAB, which checks that all the lists in L have the same property of having all the atoms a at the beginning, and all the atoms b at the end. E.g. > deepBetweenAB([a,a,[a,[a,b],b],c,[a,a,c,c,[a,b,b,b],b],b,b]). true 2 Solutions Scheme (define (split lst n) (define (split-h pre lst n) (if (<…