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:

You should leave punctuation unchanged, but you can eliminate redundant word spacing (Hint: recall the`> title "now is THE time, For aLL good men."`

"Now Is The Time, For All Good Men."`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:

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`unzip :: [(a,b)] -> ([a],[b])``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 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"`);

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'`.