代做COMP2221 Programming Paradigms 2023代写留学生数据结构程序

日期：2024-07-10 04:40

COMP2221-WE01

Programming Paradigms

2023

Section A Functional programming

Question 1

Any code you write in this question must be in Haskell.

(a) Use an example to explain why lazy evaluation allows for the application of functions over infinite data structures in Haskell. [3 Marks]

(b) A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself (Wikipedia). Write a function isPerfect that determines whether a number is a perfect number. The function should take an arbitrarily large, positive integer as input and return True if the input is a perfect number, and False otherwise. You can write helper functions if you wish. Provide type annotations for all functions you write. [5 Marks]

(c) Consider the following function fun. Explain what the function computes. Further, provide one input for which fun returns True, and another for which it returns False.

fun :: Ord a = > [ a ] -> Bool

fun [] = True

fun [ x ] = True

fun ( x : y : xs )

| x <= y = fun ( y : xs )

| therwise = False

[4 Marks]

(d) Write a Functor instance for the following custom data type MyList.

data MyList a = Empty | Cons a ( MyList a )

[5 Marks]

Question 2

Any code you write in this question must be in Haskell.

(a) Explain the difference between the Haskell keywords type and data based on an example for each. [4 Marks]

(b) Provide type annotations for each of the subsequent definitions and include type constraints where required.

def1 = 9

def2 ( m : n ) = head n

def3 x y = x + y

def4 (m , n ) = m !! n

[10 Marks]

(c) Define a data type Pet which can represent cats and dogs each with their name, colour and age. [3 Marks]

(d) Based on your Pet data type, define a function allCats that takes a list of pets and partitions it into two lists; one containing only cats, the other containing only dogs. Define any helper functions that might be required and provide type annotations for all functions. [6 Marks]

Question 3

This question is concerned with the abstraction, application and reduction rules of the λ-calculus.

(a) Reduce the λ-expression (λx.x)y to normal form. Which functionality does the λ-function λx.x capture? [2 Marks]

(b) Reduce the λ-expression (λx.((λy.(xy))x))(λz.w) to normal form. [5 Marks]

(c) Consider the λ-expression (λx.xx)(λx.xx). Discuss whether this expres-sion can be reduced to normal form. and outline which computational pat-tern it captures. [3 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. For any questions that involve UML, please follow the notations below.

UML Notations

Question 4

The partial source code of the supporting classes, a main function demonstrating the functionalities and the corresponding outputs (after implementing the missing parts) are shown below.

The DoubleIntAbstract Class

public abstract class DoubleIntAbstract

{

protected int i1, i2;

public DoubleIntAbstract(int i1, int i2)

{

this.i1 = i1;

this.i2 = i2;

}

abstract protected double Combine();

public int Compare(DoubleIntAbstract diOther)

{

if (this.Combine() > diOther.Combine())

return 1; // Bigger

else if (this.Combine() < diOther.Combine())

return -1; // Smaller

else

return 0; // The same

}

public void PrintRaw()

{

Console.Write(i1.ToString() + "-" + i2.ToString() + "␣␣");

}

public void PrintCombine()

{

Console.Write(Combine().ToString("N2") + "␣");

}

}

The DoubleInt Class

public class DoubleInt : DoubleIntAbstract

{

public DoubleInt(int i1, int i2) : base(i1, i2)

{

}

// Extra functions to be implemented here

}

The NumberSeries Class

public class NumberSeries

{

public List lstData = new List();

// Extra functions to be implemented here

}

The Main Function

internal class Program

{

static void Main(string[] args)

{

NumberSeries ns = new NumberSeries(15, 2, 6);

Console.WriteLine("15␣random␣DoubleInt␣with␣min=2␣and␣max=6:");

foreach (DoubleInt di in ns.lstData)

di.PrintRaw();

Console.WriteLine();

foreach (DoubleInt di in ns.lstData)

di.PrintCombine();

Console.WriteLine();

Console.WriteLine("SuccessiveDecrease():␣" + ns.SuccessiveDecrease());

Console.WriteLine("LongestUnchange():␣" + ns.LongestUnchange());

}

}

The corresponding outputs of the main program after implementing the missing parts

(annotated with color arrows and boxes for your understanding)

Please implement the functionalities described below. You are not allowed to change the given part of the code. Your implemented code should enable the given main program to generate output in the format as shown above. You should do proper checking to ensure valid operations and minimise computational cost/memory usage.

(a) Write an override function Combine in the DoubleInt class, which returns the combined value of the two class variables i1 and i2 using the equation below. Then, explain the code with at most 50 words. [6 Marks]

(b) Write a constructor in the NumberSeries class that takes n, min and max as inputs. The constructor initialises lstData with n items, in which i1 and i2 of each DoubleInt are random numbers in the range of [min, max]. Then, explain the code with at most 50 words. [8 Marks]

(c) Write the function SuccessiveDecrease in the NumberSeries class, which counts how many times a successive decrease in combined value occurs within three DoubleInt items in lstData. Then, explain the code with at most 50 words. [8 Marks]

(d) Write the function LongestUnchange in the NumberSeries class, which finds out the length of the longest successive unchanged combined values in lstData. Then, explain the code with at most 75 words. [8 Marks]

(e) Draw a UML class diagram for the final version of this program. This question does not require writing code. [8 Marks]

Question 5

(a) The UML diagram below represents a program to manage the products in a store. With at most 100 words, (i) explain 3 errors of object-oriented pro-gramming concepts/implementations contained in the UML, (ii) for each error, suggest one way of correction. [12 Marks]

UML Containing Object-oriented Programming Errors