Lab #3: Recursion and Pattern-matching

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.)

1. The Prelude defines functions minimum and maximum with types as follows:

   maximum, minimum :: Ord a => [a] -> a

   Here 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 minimum' and maximum' to avoid clashes with the Prelude definitions), but define your versions directly, using pattern-matching and recursion (the Prelude defines them indirectly using folds).

2. Define a function evens which returns the even-numbered elements of a list (i.e., those elements with even indices or, to put it another way: 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).

3. Define a function split 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 [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.)

4. Define a function riffle 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 [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.)

5. Continuing the theme of card shuffling, define a function shuffle 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 :: Int -> [a] -> [a]

   (Your function may use Integer or Num b in place of Int.)

6. 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.

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

   zip [1,2,3,4] [11,12,13,14] == [(1,11), (2,12), (3,13), (4,14)]

   Define a zip of your own (call it zip') using recursion and pattern-matching. Note that zip "trims off" to the length of the shorter of the two lists (your function should also).

8. 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 power of type 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