代做COMP3400 Functional and Logic Programming Semester One Examinations, 2023代写Processing

School of Information Technology and Electrical Engineering

Semester One Examinations, 2023

COMP3400 Functional and Logic Programming

§Very Short Answer

Question 1. [20 marks]

The following ten questions are worth two marks each for a total of 20 marks. Part (a) [2 marks]

A Pythagorean triplet is a triplet of positive integers  (a, b, c) such that a2 + b2  = c2.  Write a Haskell expression that produces a list of a hundred Pythagorean triplets.

Part (b) [2 marks]

Define a function f so that

> : type f

f ::   (a -> a -> a) -> a -> a

up to renaming the type variables. Your implementation does not have to be total.

Part (c) [2 marks]

The zip of two lists xs and ys is given by  [(x,y) | x <- xs, y <- ys]. Use an applicative to generate the zip of two lists.

Part (d) [2 marks]

Very briefly explain what the function foo (_ : x: __) = x does.

Part (e) [2 marks]

For what value of xs does fold r f b xs == foldl f b xs

Part (f) [2 marks]

Let  reverse ::  [Integer] -> [Integer] be a function that reverses a list.   Write a useful quick-check for  reverse.   Just write xs = arbitrary [Integer] to  get  an arbitrary list of integers.

Part (g) [2 marks]

What is the type of the following function. Be sure to include any necessary class constraints. foo x (y: ys) = if x > y then ys else y:[]

Part (h) [2 marks]

What is the β-normal form of λx.x(λy.y)x?

Part (i) [2 marks]

Using the applicative for Either write a Haskell expression that adds Right 1 and Right 2 to get Right 3.

Part (j) [2 marks]

Define map ::  (a -> b) -> [a] -> [b] using the fold r function.

§Short Answer

The following eight questions are worth five marks each for a total of 40 marks.

Question 2. [5 marks]

Give the β normal form for the following λ-calculus expression or show the expression is divergent.

(λx.xx)(λy.y)(λz.z9)(λy.y)

Question 3. [5 marks]

Suppose there is an Integer in the name password which has global scope.  Implement the function verify :: IO () that gives a user three tries to guess the password.

Example usage in REPL:

> password = 1234

> verify

Prompt: 2

Prompt: 10

Prompt: 7

Failure .

> verify

Prompt: 1234

Success

Question 4. [5 marks]

Part (a) [3 marks]

Write a function group :: Eq a => [a] -> [[a]] that groups adjacent equivalent items in the following way

> group [1, 1, 2, 2, 2, 3, 4, 4, 4, 1]

[[1,1],[2,2,2],[3],[4,4,4],[1]]

Hint: Recall the functions dropWhile and takeWhile of type  (a -> Bool) -> [a] -> [a].

Part (b) [2 marks]

Using afold write a function biggest ::  [[a]] -> [a] to find the largest group. If there are ties, the group with least index in the input is returned.

> biggest $ group [1, 1, 2, 2, 2, 3, 4, 4, 4, 1]

[2,2,2]

Question 5. [5 marks]

Consider the higher-order function unfold

unfold p h t x

| p x        = []

| otherwise = h x : unfold p h t (t x)

Part (a) [2 marks]

What is the type of unfold?

Part (b) [3 marks]

Define map ::  (a -> b) -> [a] -> [b] using unfold.

Question 6. [5 marks]

Write a Haskell function

numSums :: Integer -> [Integer] -> Integer

where numSums target xs is the number of ways the target can be computed by summing members of xs.

Preconditions: The members of xs are distinct and positive non-zero.

> numSums 30 [25, 10, 5]

5

because  25+5,  10+10+10,  10+10+5+5,  10+5+5+5+5,  and  5+5+5+5+5+5 are the  comprehensive ways you can make thirty from a 25, 10, and 5.

Question 7. [5 marks]

Define the norm of a list xs to be given by

norm xs = (sum $ map (^2) xs) ** 0.5

(the square root of the sum of squares of the list’s elements).

Part (a) [3 marks]

Define a function trNorm ::  Float -> [Float] -> Float.  that computes the norm of a list tail recursively.

Part (b) [2 marks]

Give an iteration invariant and bound value that proves the correctness of trNorm. Do not prove that your function satisfies this invariant or that your bound value is valid – just state them.

Question 8. [5 marks]

Define a function

mapMaybe ::  (a -> b) -> [Maybe a] -> Maybe [b]

which maps a function over a list of Maybe a.  If Nothing is in the input list the answer is Nothing:

> mapMaybe (>0) [Just 1, Just 0, Just 2]

Just [True,False,True]

> mapMaybe (>0) [Just 1, Nothing, Just 2]

Nothing

Question 9. [5 marks]

Define a custom data type Walker a and the functions

fromList ::  [a] -> Maybe (Walker a); fromList [] = Nothing

stepL :: Walker a -> Walker a

stepR :: Walker a -> Walker a

peek :: Walker a -> a

so that we have the following functionality:

> Just xs = fromList [1,2,3,4]

> peek xs

1

> peek $ stepR xs

2

> peek $ stepL xs

1

> peek $ (stepR . stepR) xs

3

> peek $ (stepL . stepR . stepR) xs

2

> peek $ (stepR . stepR . stepR . stepR) xs

4

§Long Answer

Show your work. Unsupported solutions will receive little or no credit.

Question 10. [10 marks]

Consider the following datatype for representing polynomials with integer degree and coef- ficients from a:

data Polynom a = Mono a Integer

| Add (Polynom a) (Polynom a)

| Mul (Polynom a) (Polynom a) deriving (Show, Eq)

For instance, 2x4 + 3x + 1 is given by Add (Add (Mono 2 4) (Mono 3 1)) (Mono 1 0).

Part (a) [3 marks]

Define a functor for Polynom that maps a function over the coefficients:

> (+1) <$> Add (Add (Mono 2 4) (Mono 3 1)) (Mono 1 0)

Add (Add (Mono 3 4) (Mono 4 1)) (Mono 2 0)

> (/2) <$> Add (Mul (Mono 1 2) (Mono 3 4)) (Mono 5 6)

Add (Mul (Mono 0.5 2) (Mono 1.5 4)) (Mono 2.5 6)

Part (b) [7 marks]

Prove fmap id = id (i.e. the first functor law) for your functor.