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 n^k. 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)

Note: Please make sure you follow the submission guidelines when you write your code.

Assignment 1

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

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

We use the fact that, if k is even, we can calculate n^k as follows:

n^k = (n²)^k/2        (k is even)

n^k = (n * n)^k/2        (k is even)

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:

n^k = n * (n^k-1)        (k is not even)

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

Hints:

Assignment 4

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)

write a Haskell function table that takes x and a maximum n as an argument, and then generates the following table:

  GHCi> 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

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.

Write your answers in one file, called Lab1.hs. For each assignment, use Haskell comments to indicate what part of the file contains the answer to the assignment. For answers in natural language, you can use Swedish or English; write your answers also in Haskell comments. Remove irrelevant things from the file.

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:

When you are done, please submit it using the Fire system.

Good luck!