12 02 14

Page 1

Principles of Programming Languages 2014.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 Consider a procedure string-from-strings that receives as input a list of objects, keeps all the objects that are strings, discarding all the others, and returns the ordered concatenation of all such strings. E.g. (string-from-strings ’(1 "hello" ", " 2 "world")) is "hello, world" 1.1 Recursive (3 pts) Define a functional (non tail) recursive version of string-from-strings (without using map, filter, fold). 1.2 Tail recursive (4 pts) Define a tail recursive version of string-from-strings (without using map, filter, fold). 1.3 Functional higher-order (3 pts) Give an implementation of string-from-strings using the classical functional higher order functions, i.e. map, filter, fold... 2 Haskell 2.1 Tree (2 pts) Define a Tree data structure, where each node contains a value and can have any number of children . 2.2 Visit (4 pts) Define a visit function, that returns a list of all the elements that are contained in the tree data structure defined before (you can choose any order you like). 1 2.3 Equality (2 pts) Two trees are considered equal iff they contain the same elements and those are in the order defined by the vist function defined before (so they could be structurally different). Define == for Tree. 2.4 zipToList (4 pts) Define the zipToList :: [(a,a)] -> [a] function, that, given a list of pairs, returns a flat list containing all the elements found in the pairs. E.g. zipToList [(1,2),(3,4)] is [1,2,3,4]. 2.5 Free monoid (4 pts) Define an infinite list containing all the elements of the free monoid{a, b}∗ (i.e. all the strings defined on the alphabet{a, b}, empty string included). 3 Prolog…