This document contains the first hand-in assignment (“lab”) for the course. It’s a small one just to get the ball rolling. See the course home page for the deadline (usually on Wednesday of week 1!).
Use this template file for your solutions.
Find a lab partner and work together in pairs. (When you are done, please submit your solution using the Fire system.)
Please note that lab assignment 2 and onwards must be submitted by groups of exactly two people. If you leave one group to join another group in Fire, save the join code before leaving the first group, in case you need to go back to it later.
In this lab assignment, you will implement the well-known power function in two different new ways. The power function takes two arguments n and k and computes nk. Your implementation only has to work for non-negative k.
We have already seen one implementation of this function in the lecture:
power :: Integer -> Integer -> Integer
power n k
| k < 0 = error "power: negative argument"
power n 0 = 1
power n k = n * power n (k-1)You will implement two more ways in this lab assignment.
In order to calculate power n k, for a given n and k, how many computing “steps” are being used?
Hint:
power n 0 takes 1 step.
power n 1 takes 1 step, and then uses power n 0.
power n 2 takes 1 step, and then uses power n 1.
power n 3 takes 1 step, and then uses power n 2.
…
Write your answer in the form of a function definition:
stepsPower n k = ...Your function should not be recursive.
A different way of computing the power function is to use the standard Haskell function product, which calculates the product (multiplication) of all elements in a list.
(You may not yet have learned about lists, but you can read about them here )
To calculate power n k, first construct a list with k elements, all being n, and then use the function product to multiply them all together.
Implement this idea as a Haskell function power1.
Hint: You have to come up with a way of producing a list with k elements, all being equal to n. Use a list comprehension, or use the standard Haskell function replicate. If you use replicate, you might want to use the function fromInteger too! Use Hoogle to find out more about standard functions.
A different approach to calculating the power function uses fewer computing steps.
We use the fact that, if k is even, we can calculate nk as follows:
nk = (n2)k/2 (k is even)
In other words:
nk = (n ⋅ n)k/2 (k is even)
So, instead of recursively using the case for k − 1, we use the (much smaller) case for k/2.
If k is not even, we simply go one step down in order to arrive at an even k, just as in the original definition of power:
nk = n ⋅ (nk − 1) (k is odd)
To sum up, to calculate power n k
k is even, we use (n ⋅ n)k/2k is odd, we use n ⋅ (nk − 1)Implement this idea as a Haskell function power2.
Hints:
even and/or odd.div (and not the function /, which is used to divide floating point and rational numbers).We would like the three functions power, power1, and power2 to calculate the same thing. It is probably a good idea to test this!
Come up with a number of test cases (inputs you will test your functions on). As a comment in your file, list the test cases and argue why you have chosen each cases. (Think about for what inputs the functions are defined, and for what inputs the functions are not defined.)
Implement a function prop_powers which given n and k checks that power n k, power1 n k, and power2 n k all give the same answer.
Write a Haskell function powerTest that checks whether power, power1 and power2 yield the same result for all the well-behaved test cases from (1), using prop_powers.
Try running quickcheck on the function prop_powers. It will probably fail. If so, define a new version, prop_powers', for which quickcheck succeeds. The new version should of course still test the intended property!
Hint: You can use a list comprehension to combine all possible cases you would like to test for n and k. Use the standard Haskell function and to combine the results.
Write your answers in the template file Lab1.hs. For each part (A-D), use Haskell comments to mark the part of the file that contains the answer to that part. For answers in natural language, use English; write your answers also in Haskell comments.
You must submit using the Fire system, preferably in groups of 2 (from Lab 2 onwards this will be strictly enforced by the fire system).
Note that the fire system automatically enforces the deadlines.
Before you submit your code, Clean It Up!
Keep lines below 80 characters; don’t use tab characters (cause other problems for Haskell).
Give type declarations for (at least) the functions you are asked to write (you may omit them for simple quickCheck properties).
Remove junk (unused or commented-out code, unnecessary comments).
Simplify overcomplicated functions, and avoid cut-and-paste coding.