Homework answers / question archive / CS-205 – Declarative Programming Question 1: Functional Programming Write a Haskell function that takes the surface of a cube as input and computes the volume of the cube

CS-205 – Declarative Programming Question 1: Functional Programming Write a Haskell function that takes the surface of a cube as input and computes the volume of the cube

Computer Science

Share With

---

CS-205 – Declarative Programming

Question 1: Functional Programming

1. Write a Haskell function that takes the surface of a cube as input and computes the volume of the cube. Within your function you should first compute an intermediate result.

[4 marks]

2. Briefly explain how interactive programs can be written in Haskell. You may use as example a program that reads a string from the keyboard and writes its reverse on the screen. No complete Haskell code is required. Pseudo code or informal explanations are fine.

[6 marks]

3. Write a Haskell function countLarge that counts the numbers in a list of integers that are larger than 100.

Define countLarge in three ways, using

3. 1. recursion;
   2. list comprehension;
   3. higher-order functions.
      6. marks]
4. What are the most general types of the following functions and expressions?
   1. increasingPair (x,y) = x < y
   2. g x y = 2*x + y
   3. [( &&),(|| )]

[3 marks]

5. Consider the following data type of trees and the function flatten that flattens a tree into a list:

data Tree = Leaf | Node Tree Int Tree

flatten :: Tree -> [ Int ] flatten Leaf = []

flatten (Node l n r) = flatten l ++ [n] ++ flatten r

A tree is called search tree if it flattens to a list that is ordered.

1. 1. Give two examples of trees such that one of them is a search tree but the other isn’t. Compute the flattenings of both trees.
   2. Write a function insert such that if n is an integer and t is a search tree then insert n t is again a search tree that contains the nodes of t and in addition the integer n. If n occurs already in t, then insert n t should be equal to t.
      6. marks]

Question 2: Programming in Prolog and Verification in Haskell

1. Indicate for the following pairs of terms whether they are unifiable or not. If a pair is not unifiable, explain why this is the case. If a pair is unifiable, give a unifier.
   1. isMotherOf(elisabeth,X) and isFatherOf(phillip,charles).
   2. isMotherOf(elisabeth,X) and isMotherof(Y,harry).
   3. 2+X and 5.
   4. smaller(X,double(X)) and smaller(double(10),Y).
   5. [X|Y] and [a,b,c,d].

[5 marks]

2. Proof search: Explain which proof search strategy Prolog has, give its advantages and describe how it works by using the following example. Draw a proof tree for lucky(X) and indicate which paths yield solutions.

rich(gareth). plumber(gareth). knows(gareth,mari). lucky(X) :- knows(X,Y), plumber(Y). lucky(X) :- knows(Y,X), plumber(Y). lucky(X) :- rich(X).

[7 marks]

3. Programs with Accumulator: Consider the following Prolog program:

len([],0).

len([_|L],N) :len(L,N1),

N is N1 + 1.

mystery([],0).

mystery([L|Ls],K) :mystery(Ls,K1), len(L,N),

K is N + K1.

1. 1. What does the query ?- mystery([[2],[1,1],[0,0,0]],K) yield?
   2. Show how this program can be modified to be tail recursive using an accumulating parameter in a program mysteryA(Ls,A,K) where A stores intermediate results, so that mystery2(Ls,K), defined by

mystery2(Ls,K) :- mysteryA(Ls,0,K).

will yield the same results as mystery(Ls,K).

[6 marks]

4. Program Verification in Haskell: Consider the following definitions:

(++) :: [a] -> [a] -> [ a ]

[]    ++ ys     = ys

(x:xs) ++ ys = x : (xs ++ ys)

f :: [a] -> [ a ] f [] = [] f (x:xs) = f xs ++ [ x,x ]

Prove by induction on lists xs that

f (xs ++ ys) = f ys ++ f xs.

In the proof you may use that following laws hold for all finite lists xs and ys.

1. 1. (xs ++ ys) ++ zs = xs ++ (ys ++ zs)
   2. xs ++ [] = xs