Week 38

Lecture Tuesday (18.9.2011)

The sixth lecture will continue with the introduction to Haskell. After repeating guards, we will introduce pattern matching and learn about more advanced ways of declaring functions.

Topics

pattern matching, guards, local declarations, operators, expressions, patterns

Reading

Lecture Notes in Blackboard (Course Documents)

Exercise Tuesday (18.9.2011)

1) The fourth lecture introduced the cut operator. Consider the following logic program:

a :- b, c.
a :- b.
b.
b.
c :- e.
c :- e, b, f.
c :- b.
e :- fail.
e.
f.
f.
f.

Draw the SLD tree and indicate all finite failures.
Now change the 6th clause from c :- e, b, f. to c :- e, b, !, f. and indicate all branches that are cut.

2) Implement the programs from the previous exercise and use the cut operator where it makes sense.

3) Consider the following Prolog program (introduced exactly like this in lecture notes for DM509 at least 5 years old):

income(peter,400000).
foreigner(peter).
average_taxpayerWrong(X) :- foreigner(X), fail.
average_taxpayerWrong(X) :- income(X,I), I < 500000.

Here, fail/0 is used to force a finite failure. The query ?- average_taxpayerWrong(peter). should clearly fail since Peter is a foreigner. Why does it not fail? How can you repair the program such that it works as one would expect?

Shorten the program to three clauses by having just one clause for average_taxpayer/1 and keeping the clauses for income/2 and foreigner/1.

4) Write definitions for a predicate divide/3 that performs division of natural numbers. For example, the query ?- divide(13,3,D) should yield the answer D = 4. Use a generate-and-test approach, i.e., use a predicate is_nat/1 defined as follows:

is_nat(0).
is_nat(X) :- is_nat(Y), X is Y+1.

Calling is_nat/1 with a variable as the argument will successively enumerate all natural numbers by backtracking. Now, define a predicate that tests whether a given natural number is a solution to the division problem. Finally, define divide using the generating predicate and the test.

5) A program that uses "," for conjunction and ";" for disjunction can always be written only using "," for conjunction. Discuss how to transform a clause with a right-hand side that is an arbitrary Boolean expression using "," and ";" step by step to a number of clauses that yield the same behaviour.

Apply your transformation to the following clause:

f(X,Y) :- X =:= 0, Y = 0; X > 0, (X > 1, X1 is X-1, X2 is X-2, f(X1,Y1), f(X2,Y2), Y is Y1+Y2; X =:= 1, Y is 1).

Simplify the resulting clauses. What does f actually compute?

6) Read Section 2.8 (Input/Output) in the lecture notes. Follow the example both with user interactions and with files.

Write a program that asks the user for a query until the user inputs stop. and executes each query. The user should then be informed whether the query succeeded or not.

7) Read Section 2.9 (Constraint Programming) in the lecture notes. Follow the SEND+MORE=MONEY example.

Then apply constraint programming to find a 3x3 magic square. Here, a nxn magic square is a field where each cell has a different number from 1 to nxn, but all rows and columns have the same sum.

Find a more magic square by adding constraints for the diagonals.

How can you change your logic program such that it can find magic squares of any given size?

Lecture Friday (21.9.2012)

The seventh lecture will continue with the introduction to Haskell.

Topics

types, parametric polymorphism, type declarations

Reading

Lecture Notes in Blackboard (Course Documents)

Exercise Friday (21.9.2012)

1) The previous exercise and the fifth lecture lecture showed how to use constraint programming to solve non-trivial search problems. Constraint programming consists of two phases. In the first phase, a given problem description is translated into constraints. In the second phase, the constraint solver looks for an assignment of the constraint variables such that all constraints are satisfied. In the examples so far, the first phase was performed manually, i.e., by the programmer. Given for example the SEND+MORE=MONEY problem, the programmer came up with the corresponding constraints. In this exercise, you will learn how to write a program that generates constraints from a given problem description. The numbers 1-26 have been randomly assigned to the 26 letters of the alphabet. As input, we are given a list of equations each consisting of a word (represented by a list of variables) and a value representing the sum of the numbers corresponding to these letters. A possible input is:

[[B,A,L,L,E,T]=45, [G,L,E,E]=66, [P,O,L,K,A]=59, [S,O,N,G]=61,
[C,E,L,L,O]=43, [J,A,Z,Z]=58, [Q,U,A,R,T,E,T]=50, [S,O,P,R,A,N,O]=82,
[C,O,N,C,E,R,T]=74, [L,Y,R,E]=47, [S,A,X,O,P,H,O,N,E]=134, [T,H,E,M,E]=72,
[F,L,U,T,E]=30, [O,B,O,E]=53, [S,C,A,L,E]=51, [V,I,O,L,I,N]=100,
[F,U,G,U,E]=50, [O,P,E,R,A]=65, [S,O,L,O]=37, [W,A,L,T,Z]=34].

Consider for example [L,Y,R,E]=47. The numbers for the letters could for example be 5,9,20 and 13 (or any other combination that add up to 47). The problem is to find the value of each letter such that all the equations are satisfied at the same time.

Discuss how to write a Prolog program that generates the constraints for an arbitrary list of equations. Implement the program and test it with at least the equations given before.

2) Let xs and ys be lists of integers and let x and y be integers. The function ++ concatenates two lists. For example, we have [1,2,3] ++ [4,5] = [1,2,3,4,5]. Which of the following equations between lists are right and which are not? Give reasons for your answers.

  • [x] = x
  • x:xs = [x ++ xs]
  • x:xs = [x,xs]
  • x:y:[] = [x:y]
  • xs ++ ys = [xs,ys]
  • xs:[] = [xs ++ []]
  • ys:x = ys ++ [x]
  • x:xs:ys = (x:xs) ++ ys
  • [x] : [] = [x] ++ []
  • xs ++ [] = xs
  • (x : ys) ++ zs = x : (ys ++ zs)

3) Implement the following functions in Haskell. Make sure these work correct on natural numbers and lists of natural numbers. You may use the pre-defined functions if ... then ... else ..., +, and >. You may not use other pre-defined functions such as *, sum, < etc.

  • times :: Int -> Int -> Int
    The expression times x y computes the product of x and y. For example, the expression times 3 4 evaluates to 12.
  • intsum :: [Int] -> Int
    The expression intsum xs computes the sum of all elements in xs. For example, the expression sum [3,4] evaluates to 7.
  • squareroot :: Int -> Int
    The expression squareroot x computes the rounded-off square root of x. For example, the expression squareroot 24 evaluates to 4 while the expression squareroot 25 evaluates to 5.
  • sumroot :: [Int] -> Int
    The expression sumroot xs computes the sum of the rounded-off square roots of all elements in xs. For example, the expression sumroot [24,16] evaluates to 8.

Design by 1234.info | Modified by Peter Schneider-Kamp | CSS 2.0