Introduction to Functional Programming – Lab 1: “Power Function” | TDA555 / DIT440, LP1 2015 |
Home | Schedule | Labs | Exercises | Exam | About | FAQ | Fire | Forum | TimeEdit | Links |
Introduction to Functional Programming – Lab 1: “Power Function” | TDA555 / DIT440, LP1 2015 |
Home | Schedule | Labs | Exercises | Exam | About | FAQ | Fire | Forum | TimeEdit | Links |
(When you are done, please submit your solution using the Fire system)
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.
Note: Please make sure you follow the submission guidelines when you write your code.
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
.
And so forth.
Write your answer as a comment in the Haskell file you submit.
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 product
.
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!
A. 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.)
B. Implement two functions: One function comparePower1
(which given n
and k
, compares the result of the power
function with your power1
function), and a function comparePower2
(which does the same for power
and power2
). These two functions will make your testing go easier!
C. Write all your test cases as one or two Haskell functions that perform all test cases. It is probably a good idea to use the functions comparePower1
and comparePower2
here.
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. If you are not familiar with list comprehensions, you do not have to use these.
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:
import MeasureTime
Now you can time the power implementations in the following way in the terminal:
*MeasureTime> measureTime2 power 10 100000
Start evaluation
Done after 2.9s
(This is an extra assignment. You do not have to do this assignment to pass the course, but you will learn more when you do!)
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.
Hint: Use show
to convert a number to a string, and use the functions length
and 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.
Use Hoogle to find out more information about these functions and others.
Use the XHtml library to render the above table as an HTML file that you can view in the browser.
You can explore the library yourself, but here is a simple example to get you started:
import Text.XHtml hiding (table)
-- Hiding `table` because it clashes with the function in assignment 5
tab :: Html
tab = simpleTable [] []
[ [toHtml "1", toHtml "2"]
, [toHtml "3", toHtml "4"]
]
main = writeFile "table.html" (renderHtml tab)
Running main
in GHCi produces the file table.html
which, when loaded in a web browser shows the following table:
1 2 3 4