**Assigned:** 9 Feb 2005

**Due:** 16 Feb 2005

In this week's lab we concentrate on a particular style of function
definition, namely recursion and pattern-matching. This style emphasizes
the internal (*inductive*) structure of lists (built from nil and cons)
more so than the style of connecting together Prelude functions that we have
used in the previous labs. Both styles are useful, and thus we have some
exercises for each.

**Note, therefore, that you should do these exercises, as requested, using
pattern-matching and recursion** (except for #3), even though there might be other
(simpler)
ways to write them built on Prelude functions. (Of course, you are welcome to
explore and submit the other style of definition as a way of developing a feel
for the differences between styles.)

- The Prelude defines functions
`minimum`and`maximum`with types as follows:

Here`maximum, minimum :: Ord a => [a] -> a``Ord a`means that the items in the list must have an ordering defined on them (rather like the`Comparable`interface in Java); these functions "inherit" the ordering from two binary functions`min`and`max`.Define your own versions of these functions (call them

and`minimum'`to avoid clashes with the Prelude definitions), but define your versions directly, using pattern-matching and recursion (the Prelude defines them indirectly using folds).`maximum'` - Define a function
which returns the even-numbered elements of a list (i.e., those elements with even indices or, to put it another way:`evens`*every other element, starting with the first*). Since 0 is an even number, that means every other element, starting with the first. Use pattern-matching and recursion in your definition (here the obvious solution in the other style si to use Prelude's`filter`). - Define a function
which returns the first half of a list and the second half of a list as a pair of results (you may favor either half when the list has an odd length). For example, you should have:`split``split [1,2,3,4,5,6] = ([1,2,3], [4,5,6])`*(Hint: this function is probably***not**best defined using direct recursion and pattern-matching, although you might like to try in order to see why. But for the assignment, see if you can find appropriate helper functions in the Prelude.) - Define a function
which will take two lists (as successive arguments) and return a third which has all the items of the arguments, but in alternating order. In other words,**riffle**`riffle [1,2,3,4] [11,12,13,14] == [1,11, 2,12, 3,13, 4,14]`*(spaces added only for emphasis)*. The name "riffle" is inspired by the last step in shuffling cards, where two stacks are "riffled" together. (Note: unlike with zip, it makes sense here to include all the "leftover" items from a longer list, in order.) - Continuing the theme of card shuffling, define a function
which repeatedly splits a list in half, then riffles the two resulting lists together. Allow an integer argument to control the number of split/riffle steps which will be taken, so that shuffle has type:`shuffle`

(Your function may use Integer or Num b in place of Int.)`shuffle :: Int -> [a] -> [a]` - Experiment with different numbers of shuffles on
lists with different numbers of elements (even numbers, odd numbers, powers of two, primes ...)
See how long it takes to return to the original list order (if ever).
Write functions (and/or use functions from the Prelude) to help you in your
testing and exploration.
You needn't come up with specific, concrete results here, but report on your experiences and findings, and show the helper functions you wrote or used.

- We have also seen the Prelude function
, which takes two (successive) argument lists and joins them into a list of pairs, as follows:`zip`

Define a zip of your own (call it`zip [1,2,3,4] [11,12,13,14] == [(1,11), (2,12), (3,13), (4,14)]`) using recursion and pattern-matching. Note that zip "trims off" to the length of the shorter of the two lists (your function should also).`zip'` - Recall the definitions of natural numbers (Peano style), addition
and multiplication given in class (see the following file
Recursion.hs for some
relevant definitions).
Define an exponentiation function

of type`power``Nat -> Nat -> Nat`which will raise its first argument to the power of its second argument. Use explicit recursion, i.e., don't just use the conversion functions and the pre-defined exponentiation functions to get the same effect. You may wish, however, to use these techniques to check your results; in particular, you should have:`num (power a b) == num a ^ num b`

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