Week 48

Lecture Tuesday (30.11.2010)

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 Wednesday (01.12.2010)

1) The fourth 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.

4) The function len for computing the length of a list can be implemented as follows:

len :: [a] -> Int
len xs = len' 0 xs
  where len' n [] = n
        len' n (x:xs) = len' (n+1) xs

Here, we use the auxilliary function len' which has an additional parameter for accumulating the result. The function len' is tail recursive, because the recursive function calls on the right-hand side of its declaration do not occur as arguments to other function. In other words, there is no function symbol above the recursive function call len' (n+1) xs.

Use the technique of tail recursion to implement the following functions in Haskell. Give the type declarations for all main and auxilliary functions.

• fact n computes the factorial of n for all n > 0, i.e., the product of all natural numbers from 1 to n. For example, the expression fact 5 yields the value 120.
• sumsquare xs computes the sum of the squares of all elements in xs. For example, the expression sumsquare [1,2,3] yields the value 14.

Lecture Friday (03.12.2010)

The seventh lecture will continue with the introduction to Haskell.

Topics

types, parametric polymorphism, type declarations

Reading

Lecture Notes in Blackboard (Course Documents)