Introduction to Functional Programming -- Lab 1: "Power Function"TDA555 / DIT440, LP1, HT2010
Home | Schedule | Labs | Exercises | Exam | AboutFire | Forum | TimeEdit | Links | 2009
(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.

### Assignment 1

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.

### Assignment 2

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.

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.

### Assignment 3

A different approach to calculating the power function uses less 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 not even)

To sum up, to calculate "power n k":

• If k is even, we use (n * n)k/2
• If k is odd, we use n*(nk-1)
• Implement this idea as a Haskell function "power2".

Hints:

• 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 "even" and/or "odd".
• To divide integer numbers, use the function "div" (and not the function "/", which is used to divide floating point and rational numbers)

• ### Assignment 4

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.

### Assignment 5 (extra assignment)

(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!)

Using the techniques you have learnt in the previous course, write a Haskell function that generates the following table in HTML code:

 k 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

Hint: You need to use the module MkHTML.hs for this.

### Submission

• First deadline (Wednesday, Sept. 8 at 9:00): You need to have made a serious effort on completing the complete lab assignment.

• Final deadline (Wednesday, Sept. 15 at 9:00): You need to have gotten a pass on the lab.

Before you submit your code, Clean It Up! Remember, submitting clean code is Really Important, and simply the polite thing to do. After you feel you are done, spend some time on cleaning your code; make it simpler, remove unneccessary things, etc. We will reject your solution if it is not clean. Clean code:

• Does not have long lines (< 78 characters)

• Has a consistent layout (do not use TAB characters in your code)

• Has type signatures for all top-level functions