School of Electrical Engineering & Computer Science

Semester One Examinations, 2024

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]

For what value of b does fold r (++) b xs == foldl (++) b xs

Part (b) [2 marks]

Let maximum ::  [Integer] -> Integer return the largest integer from a list.  Write a useful quick–check for maximum. We presume xs and ys represent arbitrary non-empty integer lists in the solution.

Part (c) [2 marks]

What type will be inferred for the following function? Be sure to include any necessary class constraints.

foo 0 = 1:2:3:[]

foo n = n :  (foo $ n-1)

Part (d) [2 marks]

Let p :: Integer -> Bool and suppose there are at least ten nonzero x  ::  Integer such that

p x == True. Write a Haskell expression that assigns ten such integers to the list xs ::  [Integer].

Part (e) [2 marks]

Add one set of brackets, round braces (), to the following expression so that it can be executed by the Haskell REPL without producing an error.

pure  (,)  <*>  [1]  <*>  pure  (,)  <*>  [2]  <*>  [3]

Part (f) [2 marks]

Define a function f so that

> : type f

f ::   (a -> b -> [c]) -> (a -> b) -> a -> c

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

Part (g) [2 marks]

Use the Maybe applicative to concatenate Just "Exam-" with Just "Bear" to obtain Just "Exam-Bear".

Part (h) [2 marks]

Give an example of “syntactic sugar” being used in the Haskell language.

Part (i) [2 marks]

Recall the cons operator:  (:)  :: a -> [a] -> [a]. What is the type of  (:) . (:)?

Part (j) [2 marks]

Very briefly explain how input/output was made pure in Haskell.

Short Answer

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

Question 2. [5 marks]

For each question give the β normal form for the given λ–calculus expression or show the expression is divergent. You must use Haskell ordering.

Part (a) [3 marks]

((λx.xx)(λy.y)) (λz.zz) ab

Part (b) [2 marks]

x ((λy.yy)(λz.zz))

Question 3. [5 marks]

Write a function

runningSum :: Integer -> IO ()

that repeatedly prompts the user (with add:) for numbers until their sum is divisible by seven. The intermediate sums are printed. The first input is the starting sum.

Sample usage . . .

1        > runningSum 10

2        add: 5

3        15

4        add:  -2

5        13

6        add: 1

7        14

8        >

Question 4. [5 marks]

A boolean expression is one that is built from variables, conjunctions (And), disjunctions (Or), and negation (Not). A datatype for representing such expressions is given by

1       data Bexpr = Var Char | And Bexpr Bexpr | Or Bexpr Bexpr |  Not Bexpr

De Morgan’s laws imply

p or q = not ((not p) and (not q))

so it is therefore possible to rewrite every boolean expression without using Or.

Define a function noOr :: Bexpr -> Bexpr that, given a boolean expression, returns an equiv- alent expression that has no Or’s in it.

2       > noOr $ Or (Var‘p’) (Var‘q’)

3       Not (And (Not (Var ‘p’)) (Not (Var ‘q’)))

Do not simplify or evaluate the expression.

Question 5. [5 marks]

We define unzip to be the inverse of the zip operation:

1       unzip [(1,2), (3,4), (5,6)] == ([1,3,5], [2, 4, 6])

Part (a) [4 marks]

Define unzip using a fold (either left or right).  You must include the type–definition.  Your unzip must be equal to a fold and nothing else to receive marks.

Part (b) [1 mark]

What is the type of the function passed to fold in Part (a) of this question?

Question 6. [5 marks]

Vending machines can only dispense coins.  Suppose someone purchases an item (in Aus– tralia) for $1.55 and pays with a $5 note. The machine will dispense back one $2 coin, one $1 coin, zero $0.50 coins, two $.20 coins, zero $0.10 coins, and one $0.05 coin totalling $3.45 in change.

Write a function

change :: Int -> [Int] -> [Int]

that when given a target sum, and list of coin values returns a list of how many coins of each denomination to give back as change while always choosing the most valuable coin first. To avoid floating–point errors we use 200 for $2, 100 for $1 and so on. . .

1        > change 345 [200, 100, 50, 20, 10, 5]

2       [1,1,0,2,0,1]  -- 1*200 + 1*100 + 0*50 + 2*20 + 0*10 + 1*5 = 345

Assume that: target sum is positive and can be made with the available coins; the machine has infinitely many coins of each denomination; the coin values are given in descending value.

Question 7. [5 marks]

The following is a tail recursive function for multiplying nonnegative integers.

1       trMult :: Integer -> Integer -> Integer -> Integer

2        trMult ans x 0 = ans

3        trMult ans x y = trMult (ans+x) x (y-1)

Prove that trMult 0 x y == x * y for all nonnegative integers x and y.

Question 8. [5 marks]

Define a function

mZipWith ::  (a -> b -> c) -> [Maybe a] -> [Maybe b] -> Maybe [c]

which does a zipWith over Maybe types.  Truncate to the length of the shorter list.  Return Nothing if mZipWith tries to “zip” any value with Nothing.

> mZipWith (+) [Just 1, Just 2] [Just 3, Just 4, Just 5]

Just [4, 6]

> mZipWith (+) [Just 1, Just 2] [Just 3, Nothing]

Nothing

> mZipWith (+) [Just 1, Just 2] [Just 3, Just 4, Nothing]

Just [4, 6]

Question 9. [5 marks]

Implement a function makeUnique which removes duplicates from a list.  Note: The ordering of the output does not matter.

> makeUnique [1, 3, 1, 2, 2]

[1,3,2]

> makeUnique "aaabbbccc"

"abc"

Your solution must include a type declaration.

Long Answer

Show your work. Unsupported solutions will receive few or no marks.

Question 10. [10 marks]

Given the type and instance declaration below, prove the second functor law for the Poly type by using induction.

-- Second functor law

fmap (g . h) = fmap g . fmap h

data Poly a = Mono a Integer | Add (Poly a) (Poly a)

instance Functor Poly where

fmap g (Mono c k)          = Mono (g c) k

fmap g (Add polyA polyB) = Add (fmap g polyA) (fmap g polyB)