Section A    Functional programming

Question 1

Except where otherwise stated, any code you write in this question should be in Haskell.

(a) Without using explicit recursion, write a function count  ::  [Int]  ->  Int to count the number of times the ith  entry in a list of integers is smaller than the (i + 1)th  entry.

For example

[4 Marks]

(b) Suppose we generalise countGeneral to lists of any type, with a user-

provided selection function f. Write down the type signature of countGeneral (you do not have to implement it).    [3 Marks]

(c)  Consider a data type for logical expressions

Write a function  collect  ::  Expr  ->  ([String],  Int), which col- lects a list of unique variable names in an expression, and the total number of times a “Not” appears. You may write helper functions if you wish. For example

[10 Marks]

(d)  In lectures, we saw two versions of a left-associative fold, foldl which is lazy in its arguments, and foldl’ which applies the combining operator strictly.   Explain the difference between these two versions, and use an example to illustrate why foldl’ is typically preferred.            [8 Marks]

(e) The Functor typeclass is an example of a so-called “principled” typeclass.

An instance declaration must provide an implementation of a single func- tion fmap  ::  Functor  f  =>  (a  -> b)  ->  f  a  ->  f b, which obeys the two functor  laws.   Explain the computational pattern captured by fmap, and why obeying the two laws ensure that fmap behaves correctly for any type implementing the instance.    [5 Marks]

Question 2

(a)  Haskell, and other programming languages with rich type systems, are in-

creasingly being adopted for critical software where minimising the number of bugs is of paramount importance.

This adoption of “high-level” languages that offer significant capabilities for abstraction is even occurring in projects where the computational per- formance of the resulting software is of high importance.

Discuss some of the  reasons you think that  “high-level”  languages are being adopted, and what benefits they provide to the programmer, as well as possible disadvantages. You could consider:

•  How Haskell’s type system helps programmers build APIs that can’t be misused;

• Whether  it  is  possible to automatically  provide guarantees on the correctness of implementations;

• Whether it is possible to automatically use concurrency or other forms of parallelism (and why);

• Whether the efficiency of software designed in this way might suffer (compared to implementing directly in a low-level language like C), and why (or why not).

You may also consider other points (four to five points in total is sufficient). You may wish to illustrate your arguments with pseudocode, or examples from other programming languages.          [20 Marks]

Section B    Object oriented programming

Except where otherwise stated, the questions in this Section should be answered assuming a C# environment using the Microsoft .NET Framework Class Library.

Question 3

The UK has many charity stores that collect and resell second-hand items to raise funds.  The items are in three types:  clothing, electronics and furniture. One of the stores wants to develop an application for managing its items.  You are asked to design the system architecture to facilitate different functionalities.

For each of the required functionalities below: (1) Draw a fragment of a Unified Modeling Language class diagram using notations as shown below to present your system designs, following good principles of OO design. You can use computer drawing program or scan a hand-drawn picture. (2) Write no more than 80 words to explain your key designs and the OOP concepts employed. You do not need to write source code, but you may reference C# functions and classes if needed.

UML Notations. 

(a) Storing the features of the items sold in the store, which includes “Skirts”,

“Coats”,  “Consoles”,  “Screens”,  “Tables” and  “Bookcases” .  Provide ex- ample features to showcase your design.     [6 Marks]

(b)  Estimating the selling price of all items in the store.  The selling price is

dependent on the age and original price of an item, but different types of item use different formulas to combine the two values.             [4 Marks]

(c)  Printing a line of text for each of the items in the store, which combines the name and age of the item, with the use of the C# IFormattable1  interface. [4 Marks]

(d) Sorting all the items in the store according to their original prices, with the use of the C# IComparable2  and IComparer3  interfaces.  Two sorting functions are required: one in ascending price order and one in descending price order.    [6 Marks]

Question 4

Binary images are images where pixels are either 0 or 1. They are usually stored as a list of Boolean values with the length of w * h, where w is the image width and h is the image height.  It is suggested that this way of storage is memory inefficient. A potentially better way is to use a list to store the positions of only the pixels with a value of 1, which are known as the marked pixels. You are asked to complete the implementation of this idea.

The partial source code of the supporting classes, a main program demonstrating the functionalities and the expected outputs are shown below. You are asked to implement the functionalities that can generate the outputs as shown.  As the aim is to reduce memory usage, you should operate directly on the list of marked positions without creating a new list that requires the full w * h memory.  You should also do proper checking to ensure valid operations and memory storage.

The Pos and BinaryImage Classes

The Main Program

The output of the main program.