23 07 12

Page 1

Principles of Programming Languages, 2012.07.23 Notes: - Total available time: 2h. - You may use any written material you need. - You cannot use computers, phones or laptops during the exam. Exercise 1 (8+8 pts) a) Mushroom Inc. is a software consultant company specialized on functional programming. Its main product is based on “listoid” data structures, that are like lists and contain at least one element. Please define a Haskell type class Listoid that contains all the types having the following operations: • cons: given an element x and a listoid y, return a listoid having x as its first element and y as rest • unit: given an element x, returns a listoid containing x • append: given two listoids, returns the listoid concatenation of them • listoidfirst: returns the first element of the listoid • listoidlast: returns the last element of the listoid • listoidrest: returns all the elements but the first of the input listoid - must return an error if called on a unit listoid LL is one of such data structures: type LL represents lists optimized w.r.t. access to the first and the last element (i.e. accessing them has constant time complexity). Please define LL as an instance of Eq, Listoid, and Show. b) Unfortunately for Mushroom Inc., one of their customers does not like the Haskell language – it prefers C++. In order to avoid losing the customer, Mushroom Inc. has to port LL to C++. While the interface is more or less the same, the C++ version is slightly different from the Haskell one – it must be coded according to C++ idioms. For example, the unit operation can be replaced by a constructor. You are required to build a first prototype of the C++ version of LL. The goal of your project is to test whether its interface matches customer requests, so you can select…