Lab Assignment 1: Power to the People
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:
You will implement two more ways in this lab assignment.
Note: Please make sure you follow the submission instructions when you write your code. Start by downloading a Haskell file Lab1.hs and add your solutions to your copy of this file.
First deadline (Monday, Sept. 9 at 12:00 2019): You need to have made a serious effort on completing the complete lab assignment.
Final deadline (Wednesday, Sept. 18 2019): You need to have gotten a pass on the lab.
Assignment (Parts A - D)
In order to calculate
power n k, for a given
k, how many computing “steps” are being used?
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:
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 )
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
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/2
k is odd, we use n ⋅ (nk − 1)
Implement this idea as a Haskell function
- Do not forget to add a base case (what do you do when k = 0?)
- You need to find out when numbers are even or odd. Use the standard Haskell functions
- To divide integer numbers, use the function
div (and not the function
/, which is used to divide floating point and rational numbers).
We would like the three functions
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).
Argue why you have chosen these test cases. (Think about for what inputs the functions are defined, and for what inputs the functions are not defined.)
Implement two functions: One function
comparePower1 (which given
k, compares the result of the
power function with your
power1 function), and a function
comparePower2 (which does the same for
power2). Your tests should give the result
True when the test succeeds, and
False if it runs without an error but does not give the same result in both cases. These two functions will make your tests easier to write!
Write all your test cases as one or two Haskell functions that perform all tests. It is probably a good idea to use the functions
Hint: You can use a list comprehension to combine all possible cases you would like to test for
k. Use the standard Haskell function
and to combine the results. If you are not familiar with list comprehensions, you do not have to use these.
This is an optional extra assignment.
Just for fun, measure and compare the speed of the different power implementations. You can do this by downloading the MeasureTime module to the same directory as the file for lab 1. Then add the following line at the top of the file for lab 1:
Now you can time the power implementations in the following way in the terminal:
*MeasureTime> measureTime2 power 10 100000
Done after 2.9s
Write a Haskell function
table that takes
x and a maximum
n as an argument, and then generates a table in the following way:
*Main> table 2 10
n power power1 power2
0 1 1 1
1 2 2 2
2 4 4 4
3 8 8 8
4 16 16 16
5 32 32 32
6 64 64 64
7 128 128 128
8 256 256 256
9 512 512 512
10 1024 1024 1024
Exact details on how many spaces to insert where, how to line up the numbers, etc. are freely choosable for you.
show to convert a number to a string, and use the functions
replicate to calculate the right number of spaces between the strings. Use
unlines to convert a list of lines into one big text. Use
putStr to display the generated string on the screen. It would be cool to try to add a list of the speeds to the table. Go wild.
Use Hoogle to find out more information about these functions and others.
You must submit using the Fire system, preferably in groups of 3 (from Lab 2 onwards this will be strictly enforced by the Fire system).
When you register in Fire, make sure you use the same name and personal number as in Canvas/Ladok, and make sure you use the correct course code (TDA555 for Chalmers students, DIT440 for GU students).
Before you submit your code,
spend some time on cleaning up your code; make it simpler,
remove unneccessary things, etc.
We will reject your solution if it is not clean. Clean code:
Feel free to use the
program to help with many of these issues and other haskell style issues.
If a the suggestion from hlint looks like it assumes knowledge about things
we haven't covered yet in the lectures, you can ignore it
(or possibly include it in a comment in your code).
- Does not have long lines (< 78 characters)
- Has a consistent layout (avoid using TAB characters in your code)
- Has type signatures for all top-level functions
that you are asked to write
- Has good comments
- Has no junk (junk is unused code, commented code, unneccessary comments)
- Has no overly complicated function definitions
- Does not contain any repetitive code (copy-and-paste programming)
To the Fire System
- 2019-08-29 Reformatted, updated submission instructions for 2019 (TH)
- 2018-08-30 Reformatted, minor changes (DS)