05 09 13

Page 1

Principles of Programming Languages 2013.09.05 Notes • Total available time: 1h 30’. • You may use any written material you need. • You cannot use computers or phones during the exam. 1 Scheme (10 points) Consider the parent-pointer implementation of general trees (PPT), where every node has local data (e.g. a name), and only one pointer, pointing to its parent. Of course, roots nodes do not point to other nodes. PPTs are generally implemented as arrays containing pairs (index of parent, node name), and one of such data structures can contain one or more different trees, e.g. using a Scheme-like syntax: #((? . R) (0 . A) (0 . B) (1 . C) (1 . D) (1 . E) (2 . F) (? . W) (7 . X) (7 . Y)) where root nodes have first component “?”. Nodes are usually referenced through their index. PPTs are efficient for checking if two nodes belong to the same tree (we have just to check if the root is the same for both), so are often used to represent partitions. You are requested to implement a mutable version of PPTs in Scheme. In particular, you must: 1. Define the operation find-root, to obtain the root of the tree containing the given node. 2. Define the operation union!, that takes two nodes and, if they belong to different trees, merges the two trees by making the root of the first node’s tree the parent of the root of the second node’s tree. 2 Haskell (12 points) Define the data structure, findRoot and union operations for immutable PPTs in Haskell. Remainder and hints : immutable arrays are offered by the module Data.Array; an array with index type Int and containing elements of type Type has type Array Int Type . You can use Int for indexes. Typical operations on arrays are ! to access an element (e.g. A ! 3 is equivalent to A[3] in C), and // for updates (e.g. A // [(3, 12)] creates a new…