Lab Exercises Week 4

Recursion

Using Email at CSE

You should regularly read the email that is sent to your CSE account. Important announcements regarding this subject will sometimes be made by email to your CSE account. If you do not read such email, you will have to bear the consequences arising from the lack of information.

Moreover, you must write emails that concern this subject and are directed to your tutor or the subject administrators from your CSE account or your UNSW student account, rather than from accounts outside of UNSW. This allows us to establish your identity. Emails from other accounts, especially from anonymous accounts like those provided by Hotmail can easily be faked and we reserve the right to disregard such messages entirely.

To help you getting used to CSE email, this week's lab contains an email component that you have to do to get your mark this week. It contains the following steps:

• Get familiar with the email reader evolution, or any other of your choice. (I strongly recommend to do this either before the lab or only after you have solved the Haskell exercises and showed them to your tutor.)
• Read your CSE email. It should contain an email with the subject "Lab04".
• Read this email. It should contain (possibly among other things), the following text:

  What was the mark awarded to you in Lab04?

• Reply to this email from your CSE account. The reply should at least contain the following text:

  > What was the mark awarded to you in Lab04?
  
  My mark was X.

  where for X you substitute the mark actually awarded to you.

Replies that do not originate from your CSE account will not be counted!

You may send this email in or after your lab. If you are unsure about this exercise, ask your tutor.

For more information about email at CSE and the available mail readers, see the Unix Primer, Email@CSE, and the corresponding FAQ entry. (Please read this before or after the lab.)

Ex 1:

Create a new file called Lab04.hs into which you add your solutions to the this week's Haskell exercises. As last week, before beginning with the exercises, don't forget to add comments at the beginning of this file, which describe the purpose of this Haskell module and who wrote it. Then, for each function that your are implementing, follow the Five Steps.

Generate a list of integers: enumFromToBy

Write a recursive function enumFromToBy that computes a list of integer numbers in a given range using a given step:

enumFromToBy m n k = [ m, m + k , ..., n']

where n' is the largest number below n, such that n' = m + i * k, for some i. You can assume that the step value (i.e., the argument k) is always positive.

Lab04> enumFromToBy 1 10 2
[1,3,5,7,9]
Lab04> enumFromToBy 20 10 2
[]

You will need to use generative recursion for this exercise.

Remove empty strings: removeEmpty

Write function removeEmpty that given a list of strings, removes all empty strings from that list.

Lab04> removeEmpty ["", "Hello", "", "", "World!"]
["Hello","World!"]
Lab04> removeEmpty [""]
[]
Lab04> removeEmpty []
[]

You will need to use structural recursion for this exercise.

When you have completed the above exercises show them to your tutor for this week's core mark.

Ex 2:

Fibonacci Numbers

Leonardo of Pisa, sometimes called Leonardo Fibonacci, was the greatest mathematician of pre-Renaissance Europe. He built upon the work of the great islamic mathematician al-Kowarizmi, after whom algorithms are named. In the year 1202 Leonardo described this sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

It is known as the fibbonacci sequence. Each number is the sum of the two previous numbers in the sequence (except for the first 2 numbers). Leonardo has been dead for over 700 years but his sequence is far from forgotten. It plays an important role in quite a few algorithms you will meet in later courses.

Construct a Haskell function that returns the n-th member of the Fibonacci sequence. For example:

Lab04> :type fibonacci
fibonacci :: Int -> Int
Lab04> fibonacci 1
0
Lab04> fibonacci 2
1
Lab04> fibonacci 3
1
Lab04> fibonacci 4
2
Lab04> fibonacci 5
3
Lab04> fibonacci 20
4181

Hint: You can take a similar approach to that used in the factorial function, except your fibonacci function will need to handle three cases: n == 1, n == 2 and n > 2.

Count occurences of True: countTrue

Write a recursive function countTrue that returns the number of occurrences of the value True in a list:

Lab04> countTrue [False, True, True, False, True]
3
Lab04> countTrue []
0

When you have completed the above exercise show them to your tutor for this week's advanced mark.

Additional Exercises

The following is an additional exercise to help you getting practice in programming. It is not part of the lab mark, but it should help you understand some of the material covered in the lecture.

Make integers positive

Write a recursive function makePositive that given a list of integers changes the sign of all negative integers in the list:

Lab04> makePositive [-1, 0, 5, -10, -20]
[1,0,5,10,20]

Extend the enumeration function

Extend the function enumFromToBy to also work for negative steps -- for example

enumFromToBy 10 1 (-2) = [10, 8, 6, 4, 2]