Homework answers / question archive / Swansea University College of Science Prifysgol Abertawe Coleg Gwyddoniaeth January 2019 CS-205 Declarative Programming Time Available: 2 hours Coordinator: Dr M Seisenberger Queries: The Exams Office hold contact details for this paper Only University-supplied dictionaries are permitted Calculators? Not Permitted Attempt all questions

Swansea University College of Science Prifysgol Abertawe Coleg Gwyddoniaeth January 2019 CS-205 Declarative Programming Time Available: 2 hours Coordinator: Dr M Seisenberger Queries: The Exams Office hold contact details for this paper Only University-supplied dictionaries are permitted Calculators? Not Permitted Attempt all questions

Computer Science

Share With

---

Swansea University College of Science

Prifysgol Abertawe Coleg Gwyddoniaeth

January 2019

CS-205

Declarative Programming

Time Available: 2 hours

Coordinator: Dr M Seisenberger

Queries: The Exams Office hold contact details for this paper

Only University-supplied dictionaries are permitted

Calculators? Not Permitted

Attempt all questions.

ANSWER BOTH QUESTIONS

Question 1: Functional Programming

(a) Write two different functions maximum1 and maximum2 that compute the maximum of three numbers. (Note: your two functions should be com-putationally different, and not use the built in maximum function.)

Explain how you can increase your confidence in the correctness of your implementations.  [7 marks]

(b) What are the values of the following expressions?

(i) map (27) [0,4,3,7]

(ii) [(x,y)| x <- [0..3], y <-[1..x]]

(iii) filter (\ x -> x ‘mod‘ 2 == 1) [2,3,4,5,6,7] [3 marks|

(c) Consider the following code:

filter :: (a -> Bool) -> [a] -> [al

filter t [] = []

filter t (x:xs) = if t x

then x : filter t xs

else filter t xs

Is the function filter higher-order, polymorphic, recursive? Justify all three answers.    [5 marks]

(d) Suppose you are at your home town which is the city numbered by your

student number. Your goal is to reach city 1. The traveling instructions are as follows:

If you are at city k and k is an even number, then go to city k2. If k is odd, then go to city 3k + 1. Write a function that computes the list of all cities you visit on your journey.    [4 marks]

(e) (i) Consider the following code.

main = do xs <- getLine

t <- return(20 == (read xs))

putStr (show t)

Expain what the program is doing and give the type of main as well as the types of xs and t. Which is the general concept behind IO in Haskell?

(ii) Write an interactive program multiply in Haskell that takes as an argument a number n and asks the user to enter the result of multiplying the numbers 17 and n. If the answer is correct, the program should print “Excellent!”, and return the pair consisting of the number n and the result entered, otherwise the user should be asked again to enter the result.      [6 marks]

Question 2: Prolog Programming

(a) List three advantages of a declarative programming languages over non- declarative programming languages. Justify your answers by listing de- scribing concepts/ideas in Haskell or Prolog which demonstrate these advantages. At least one of your advantages should hold for both lan-guages.

[6 marks]

(b) Do the following pairs unify? Justify your answer, e.g., by providing a unifying substitution in the positive case.

(i) X and 4+4.

(ii) 4*9 and 36.

(iii) f(X,john,[g(Y)]) and f(g(john),Y,[g(john)]).

(iv) [a|rest] and [a,b,c,d].

(v) h(X,f(a),f(g(X))) and h(Z,f(Y),f(Z)).

(vi) [1,2,X] and [1,2,x,4,5].          [6 marks]

(c) Write a program replace/2 that takes two lists of numbers as arguments, and behaves as follows: For every 0 in the first list there is a 1 in the second list (at the same position), all other numbers are the same in both lists.     [4 marks]

(d) Given the following program:  puzzle([],[]).

puzzle([H,_|T],L):-puzzle(T,NewL),append(NewL,[H],L).

(i) What does the query ?- puzzle([10,20,30,40]),X) yield?

(ii) Rewrite it in such a way that it uses an accumulator. [4 marks]

e) The eight queens puzzle is the problem of placing eight chess queens on an 8 × 8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of

n = 2 and n = 3.

(i) We represent board positions with a list of lists, e.g.,

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

denotes the following board:

Q - -

- - Q

- Q -

Write the predicate straight/1 such that given a board position B, straight(B) is true if and only if there are two queens on B aligned in a straight line in the same column. Similarly, the predicate diag/1 is defined such that given a board posi-tion B, diag(B) is true if and only if there are two queens on B aligned diagonally.

(ii) With between/3 defined as follows:

between(N,M,K) :- N=

(Main steps suffice.) Which concept do you use and why? [5 marks]