Introduction

In this coursework assignment, you will implement the well-known power function in two different ways.  The power function takes two integer arguments, n and k, and computes nk.  Your implementations only have to work for non-negative k.

Downloading the skeleton code

1.  Download the skeleton code zip file by going to this link.

2.  Extract the contents of the zip to wherever you want to save it

•  How to extract zip files on Windows

•  How to extract zip files on Ubuntu

•  How to extract zip files on Mac

Compiling and running tests

If your code passes all the tests, you get all the marks! It’s therefore essential that you can compile and run the tests. To do this:

1.  In VSCode (in WSL mode if you’re on Windows), open the folder containing the skeleton code

2.  Open an integrated terminal in the VSCode window,  either  by  using the  menu  bar (”Terminal ->  New Terminal”) or by using the shortcut (Ctrl + Shift + ‘).

3.  Run cabal update (this will update your package list for Haskell libraries)

4.  Run cabal build (this will build your project and the tests, which may take a little while the first time) 5.  Run cabal test (this will run the tests)

When you run this on the skeleton code all the tests should fail, because nothing has been implemented yet.

Every time you make a change, run cabal test to test it! You can also load Power.hs in GHCi/interactive mode using cabal repl

Write all your code in Power.hs, but don’t change the name of the functions and don’t change any other files. You are free to write any helper functions you like, as long as you write them in Power.hs.

Calculating your mark

Your mark will be based on the percentage of tasks you implement correctly.   This is not the same as the percentage of passing tests.  Instead, to get the marks for a task, you must pass every test for that task.  This means all tasks are worth an equal number of marks, even if they have a different number of tests.

Submitting your coursework

Submit your work via Blackboard.  You should submit only Power.hs.  Do not rename Power.hs.  Do not submit any other files.  Do not submit a zip file.

You are responsible for early submission, therefore you should submit at least an hour before the deadline to make sure there are no upload problems. The university systems will automatically apply harsh penalties if the coursework is late by even a second.

Task 1

Look at the power implementation provided for you in Power.hs.  In order to calculate power n k, for a given n and k, how many computational “steps” are required?

Write your answer in the form of a function definition:

stepsPower n k = ...

Your function should not be recursive.

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.

...

Task 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 the function product to multiply them alltogether.

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.  You could use the standard Haskell function replicate to do this.  If you do, you might want to use the function fromInteger too! Use Hoogle to find out more about standard functions.

Task 3

A different approach to calculating the power function uses fewer computational steps.

We use the fact that, ifk is even, we can calculate nk  as follows:

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)

In summary, to calculate power n k:

•  Ifk is even, we use (n · n)k/2

•  Ifk is odd, we use n · (nk − 1 )

Implement this idea as a Haskell function power2.

Hints:

•  Don’t forget to add a base case (what should you do when k = 0?).