Week 51
Lecture Tuesday (15.12.2009)
The tenth lecture will continue with I/O in Haskell. Then we will start with analysis of Haskell programs with respect to space, runtime, and correctness.
Topics
IO monad, space and time consumption, correctness proofs
Reading
Lecture Notes in Blackboard (Course Documents), chapter on correctness (Course Documents), chapter on complexity (Course Documents)
Exercise Wednesday (16.12.2009)
1) Implement a function sumList :: IO () in Haskell. If sumList is executed, the user can type in a list of integers on the keyboard in standard Haskell notation. Afterwards, the sum of these integers is printed on the screen using the function putStr. For example, if the user enters the string [1, -5, 70], then the number 66 is displayed on the screen.
In order to convert a String into an [Int] you may use the built-in function read :: String -> [Int]. For example, read "[1, -5, 70]" :: [Int] will read in the list of integers [1, -5, 70].
2) Consider the following Haskell program
data Nats = Zero | Succ Nats
add :: Int -> Int -> Int
add Zero y = y
add (Succ x) y = Succ (add x y)
mul :: Int -> Int -> Int
mul Zero y = Zero
mul (Succ x) y = plus y (mul x y)
Show that mul x Zero = Zero for all natural numbers x.
Show that add is commutative, i.e., that add x y = add y x for all natural numbers x and y.
3) Write a program in Haskell which tells the user to think of a secret integer number. Then the program asks the user for a lower and an upper bound of an interval containing the secret number. Afterwards, the computer tries to guess the secret number and asks the user if its guess is the right one or the secret number is smaller or bigger. The program repeats guessing until it finds the secret number. It should try to use as few guesses as possible.
Here is a successful session (where inputs by the user are enclosed in underscores):
Try to think of a number in a certain range!
Please enter the lower bound of your range: _1_
Please enter the upper bound of your range: _100_
Searching from 1 to 100
My guess #1: 50
Am I (r)ight or is your number (s)maller or (b)igger? _s_
Smaller? Let me see ...
My guess #2: 25
Am I (r)ight or is your number (s)maller or (b)igger? _b_
Bigger? Well, I think ...
My guess #3: 37
Am I (r)ight or is your number (s)maller or (b)igger? _s_
Smaller? Let me see ...
My guess #4: 31
Am I (r)ight or is your number (s)maller or (b)igger? _b_
Bigger? Well, I think ...
My guess #5: 34
Am I (r)ight or is your number (s)maller or (b)igger? _r_
Yes! I made it!
Here is another successful session:
Try to think of a number in a certain range!
Please enter the lower bound of your range: _1_
Please enter the upper bound of your range: _100_
Searching from 1 to 100
My guess #1: 50
Am I (r)ight or is your number (s)maller or (b)igger? _b_
Bigger? Well, I think ...
My guess #2: 75
Am I (r)ight or is your number (s)maller or (b)igger? _s_
Smaller? Let me see ...
My guess #3: 62
Am I (r)ight or is your number (s)maller or (b)igger? _b_
Bigger? Well, I think ...
My guess #4: 68
Am I (r)ight or is your number (s)maller or (b)igger? _b_
Bigger? Well, I think ...
My guess #5: 71
Am I (r)ight or is your number (s)maller or (b)igger? _b_
Bigger? Well, I think ...
My guess #6: 73
Am I (r)ight or is your number (s)maller or (b)igger? _b_
Bigger? Well, I think ...
... it is 74!
4) Consider the implementation of sets as the data type defined on Page 6 of the notes on complexity available from Blackboard. Discuss how the time complexities given in the table arise.
Discuss what the space complexity for the individual operations is given each of the different data structures.
Lecture Thursday (17.12.2009)
The eleventh and last lecture will continue with correctness proofs for Haskell programs. Finally, we will wrap up the topics of the lecture with respect to the exam.
Topics
correctness proofs, relevant exam topics
Reading
chapter on correctness (Course Documents), chapter on complexity (Course Documents)