Lab #2: More Fun with Lists and Recursion

Assigned: Wednesday 2 February 2005
Due: Wednesday 9 February 2005

This week we'll try out a few more simple functions on lists (look for other data structures such as binary trees next time) and a couple of exercises on recursion. See last week's lab for tips on strategy, etc.

Write a function title which will take a string as argument and return a new string with all initial letters uppercase and all non-initial letters lowercase:
> title "now is THE time, For aLL good men." "Now Is The Time, For All Good Men."
You should leave punctuation unchanged, but you can eliminate redundant word spacing (Hint: recall the words, head and tail functions; try working in two stages).
It can be useful during testing programs to apply a single function of two arguments to all combinations from two lists of possible arguments; this can be used to show a table of results, rather like a grade school multiplication table.
Write a function tabulate which will take a single function and two successive lists of arguments and return a list of lists of results, representing all possible combinations of the function with arguments from the two lists (note: the first argument should always come from the first list and the second argument from the second list).
> tabulate (*) [1..3] [10..12] [[10, 11, 12], [20, 22, 24], [30, 33, 36]]

Hint: you can use the following function to print out tables in a tab/return style:
prTable xss = putStr (concatMap (('\n':) . concatMap (('\t':) . show)) xss)

It can be called as follows:
> tabulate (*) [1..3] [1..4] [[1, 2, 3, 4], [2, 4, 6, 8], [3, 6, 9, 12]] > prTable $$ 1 2 3 4 2 4 6 8 3 6 9 12
We saw the standard Prelude zip and zipWith functions in lecture yesterday: zip takes two lists and returns a list of pairs, whereas zipWith applies a function between the elements of two lists (so to speak).
There is also a standard unzip function which takes a list of pairs and returns a pair of lists as a result:
unzip :: [(a,b)] -> ([a],[b])
Unfortunately, the definition of this function in the Prelude is a little obscure: see if you can write your own definition of unzip using functions you already know (you may also want the two functions fst and snd which "project" the first and second halves of a pair).
Your function should behave (for example) as follows:
Prelude> unzip [('a',1),('b',2),('c',3),('d',4),('e',5)] ("abcde",[1,2,3,4,5])
You might be tempted to think that the two functions zip and unzip are inverses, and in some sense they are, but in fact the following "theorem" is not really universally true: why?
```
For all lists xs and ys,

	unzip (zip xs ys) == (xs,ys)
				
```

A medium-sized exercise

A simple "encryption" mechanism used in Usenet newsgroups is called "rot13". It doesn't actually encrypt text (it's too easily inverted), but rather is used to hide text from being immediately viewed. This can be used either for delaying punch lines to a joke or as a simple way to block potentially objectionable material (one must overtly "decrypt" the text, thus implicitly agreeing not to be offended).

The idea behind the "rot13" technique is simple: every alphabetic character in the message is "rotated" 13 letters forward through the alphabet, wrapping back around from the end to the beginning when necessary. All non-alphabetic symbols are preserved. Note that upper- and lower-case letters must be treated a bit differently, since they lie in different alphabetic ranges.

Define a "rot" function that takes a number n (usually 13) and a string and returns a modified string to which the technique has been applied. By way of example:
> rot 13 "This is a message; it is a test, just a test." "Guvf vf n zrffntr; vg vf n grfg, whfg n grfg."

You may want to make use of the following functions:
- ord yields the ASCII ordinal corresponding to a character
  (so, e.g., ord 'a' is 97);
- chr yields the character corresponding to an ASCII ordinal
  (so, e.g., chr 97 is 'a');
- mod returns its first argument "modulo" its second argument
  (so, e.g., mod 10 3 is 1;
- isUpper is True for upper-case letters;
- isLower is True for lower-case letters;
- map applies a function to all elements of a list, returning a list of corresponding results
  (so, e.g., map toUpper "foobar" is "FOOBAR");

Non-coding exercise: more fun with rabbits

We saw in lecture yesterday a couple of definitions of the Fibonacci function; the code in the file linked below includes the missing version using "accumulating parameters" (it basically "shifts" values from p and q to q and (p+q) as it is called successively). The standard recursive definition is also there, as well as two slight variations on the zipped list version.

Fibs.hs

Turn on timing statistics in Hugs (using the :s +s command) and try running each of the different functions for values such as 10, 20, 30, 100 and 1000 (well, don't try the standard recursive version for larger values, as it is too slow). Recall that when you evaluate an expression for the second and subsequent times, you will see some benefit from reduction on the first evaluation.

Keep track of the timings in a table and see if you can develop an equation in terms of n, which precisely describes the number of reductions which you will see (i.e., a polynomial in n, as in O notation, but with specific constants included).

You may think that the list versions are still a little slow, but try the following experiment on the ys and y values defined in the files (as well as the j and k values defined in terms of fibl'): compare the time to generate and print the list ys and the time to compute and print y, paying special attention to the difference betweem timings for the first and susequent evaluations. What can you conjecture about the apparent slow speed of the list-based versions of Fibonacci?

(Note that there are slight differences between the fibl and fibl' functions in terms of timing: why do you think that the use of a global versus local definition of the list matters?)

Please have answers to the above exercises ready for the lab session on Wednesday 9 February 2005

Your answers should include:

definitions for the title, tabulate and unzip functions;
your answer to the question about zip and unzip being inverses;
a (set of) definitions for the rot function;
tabulated timing results for fibr, fiba, fibl and fibl' functions (for several values of n);
your polynomials in n which describe the running time of all these functions (except fibr, which may be quite hard);
your conjectures about the timings for list-based versions fibl and fibl'.