Please prepare yourself for these exercises by printing them out, and also printing out the code samples and documentation that is referred to by links.

If you do not have time to do all these exercises, don't worry. The exercises are intended to provide enough work to keep the most experienced students busy. If you do all exercises marked with an (*) you have probably understood this week's material.

Some of the exercises below involve writing QuickCheck properties. The parts of those exercie that require you to run QuickCheck are obviously not so suited for doing in the group exercises. These parts you can do yourself at home, either before the exercise session (as preparation), or after.

Good luck!

0 (*). Exercises from the Book

Now, do the following exercises: 9.2(*), 9.3, 9.4(*), 9.9, 9.11(*), 9.14, 9.19, 9.20, 9.21(*).

From the book, look at Sections 10.1 and 10.2.

Now, do the following exercises: 10.2(*), 10.3, 10.5, 10.6, 10.7(*).

Do not forget to write suitable QuickCheck properties checking that your definitions behave as expected.

(To QuickCheck properties for all functions, import Text.Show.Functions!)

1 (*). List Comprehensions and Higher-Order Functions

1. [ x+1 | x <- xs ]
2. [ x+y | x <- xs, y <-ys ]
3. [ x+2 | x <- xs, x > 3 ]
4. [ x+3 | (x,_) <- xys ]
5. [ x+4 | (x,y) <- xys, x+y < 5 ]
6. [ x+5 | Just x <- mxs ]

1. map (+3) xs
2. filter (>7) xs
3. concat (map (\x -> map (\y -> (x,y)) ys) xs)
4. filter (>3) (map (\(x,y) -> x+y) xys)

2 (*). Exercises on type Expr from the Lecture

Take a look at the datatype Expr for expressions with variables from the lecture: ExprVar.hs.

In the lecture, I showed a function for differentiating expressions, called diff (Swedish: "derivat").

  diff :: Expr -> Name -> Expr
  diff (Num n)   x = Num 0
  diff (Add a b) x = Add (diff a x) (diff b x)
  diff (Mul a b) x = Add (Mul a (diff b x)) (Mul b (diff a x))
  diff (Var y)   x
    | x == y       = Num 1
    | otherwise    = Num 0

A. Define a property that checks that, for each expression e, the derivative of e to x does not contain more variables than e.

Does the opposite hold also?

The result of the diff function often contains expressions that can be enormously simplified.

B.(*) Define a function simplify that, given an expression e, creates an expression that is equivalent to e, but simplified. Examples of simplifications you could do are:

We have made a small start for you in the file ExprVar.hs

Hint: This exercise is more open-ended.

You can try to define simplify recursively. You will however notice that it is difficult to accomplish many simplifications. Take a look at the function assoc in chapter 14 in the book.

(A different, but more ambitious, approach is to design a new type, that represents a normal form for expressions, for example polynomials. Your simplify function could simply transform an expression into a polynomial, and back into expressions again. How would you model polynomials over multiple variables as a type in Haskell?)

Make sure that the following property holds for your simplify function: For each expression e, evaluating it in an environment generates the same result before and after simplifying:

  prop_SimplifyCorrect e (Env env) =
    eval env e == eval env (simplify e)

C. Define a property:

  prop_SimplifyNoJunk :: Expr -> Bool

This property boils down to defining a function noJunk:: Expr -> Bool. We have already made a small start for you in ExprVar.hs.

D. Define a property:

  prop_SimplifyDiff :: Expr -> Bool

Do you expect it to hold? Does it actually hold for your simplification function?

3. Exercises on Propositional Logic

• a variable name (a string)
• p & q      (and)
• p | q      (or)
• ~p      (not)

where p and q are propositions. For example, p | ~p is a proposition.

A. Design a data type Proposition to represent propositions.

B. Define a function

vars :: Proposition -> [String]

which returns a list of the variables in a proposition. Make sure each variable appears only once in the list you return.

Suppose you are given a list of variable names and their values, of type Bool, for example, [("p",True),("q",False)]. Define a function

truthValue :: Proposition -> [(String,Bool)] -> Bool

which determines whether the proposition is true when the variables have the values given.

C. Define a function

tautology :: Proposition -> Bool

which returns true if the proposition holds for all values of the variables appearing in it.

Congratulations! You have implemented a simple theorem prover.

4. Approximating 0-solutions of functions

solve0 :: (Double -> Double) -> (Double,Double) -> Double

The idea is that solve f (x0,x1) finds a value x in between x0 and x1 such that f x == 0.0.

Examples:

  Main> solve0 (+1) (-3,3)
  -1.0
  Main> solve0 cos (2,5)
  4.71238898031879
  Main> solve0 (\x -> x ^ 2 - 10) (1,10)
  3.16227766017255
  Main> solve0 (\x -> x ^ 3) (1,1)
  Program error: no solution!

  Main> solve0 (\x -> x ^ 2) (1,10)
  Program error: bad interval!

One way to do this is to use the "halving" method: Calculate x that lies somewhere in between x0 and x1. Investigate f x. Then recursively solve f on either the interval (x0,x) or (x,x1).

There are other methods too!