CS 254 Lab 3: More Exercises, Some Recursion

For this lab we will continue with some fairly simple function definitions, but now possibly including definition by recursion, typically using patterns over lists. Of course, the functions described below can be written many ways: I would encourage you to think about each one as being written either in terms of "prior" functions (e.g., in the Prelude or some library) or in terms of explicit recursion. (It wouldn't be a bad idea to write both when you can!)

Special note: it is, however, part of point of the assignment (as it is with all our labs) that you write the functions yourself, at least at some level (i.e., allowing for some use of Prelude, etc.). In other words, you are supposed to be getting practice at writing, not practice at finding things someone else already defined somewhere on the web ☺ .

So, try to write each of these functions (let's do them all this time, even though a few are a bit more difficult):

1. Write a function count :: (a -> Bool) -> [a] -> Int that will count how many elements of a list meet a certain predicate. (You might end up returning a Num a or Integer result, depending on how you do this one.)

   Example:

   Hugs> count even [1..20]
   10
   

2. In lecture we saw the until function from the Prelude that applied a function to some initial "seed" value repeatedly, until it produced a result that met some predicate; write a while function of the same type, but which returns the first value that "breaks" the rule.

   Example:

   Hugs> while (<100) (*2) 1
   128
   

3. Hmmm, what were those intermediate values generated by while, anyway? Write a function during :: (a -> Bool) -> (a -> a) -> a -> [a] that will return a list of all the values "generated" during a run of while. For this one, rather than return the value that "broke" the rule, let's only include the ones that meet it.

   Example:

   Hugs> during (<100) (*2) 1
   [1,2,4,8,16,32,64]
   

4. We saw the elem function from the Prelude that allowed us to treat lists roughly like sets; write a function subset :: Eq a => [a] -> [a] -> Bool which will tell if its first list argument is a subset of the second, i.e., if all the members of the first list are also members of the second.

5. In a related vein, we might want to generate the "powerset" of a list (maybe the "powerlist"?). Write a function power :: [a] -> [[a]] which will return a list of lists such that (roughly) every list that is a sublist of the original argument will be an element of the powerlist. What about duplication and order, which are relevant for lists, but not for sets? Well, let's not worry too much about order, but if there are distinct-but-equal occurrences of elements in the argument list, it's easiest to treat them as distinct for the result.

   Example:

   Hugs> power "abc"
   ["","c","b","bc","a","ac","ab","abc"]
   
   Hugs> power [2,2,2]
   [[],[2],[2],[2,2],[2],[2,2],[2,2],[2,2,2]]
   

   (Remember, the order of elements in your results might differ from these examples!)

6. Write a function that will return a list of all the even-numbered elements of a list; in other words, every other element, starting with the "0th" one. Your function should be of this type: evens :: [a] -> [a].

   Example:

   Hugs> evens "abcdefg"
   "aceg"
   

   (This might make good use of patterns we haven't seen as of Friday's lecture: if you have trouble with it, just try again after Monday's lecture.)

7. Write a function that will take a "relation" r and break a list of values into "segments", where each of the successive pairs of list elements bear the relation to each other. In other words, the segments "break" the list between elements where the relation fails. This will allow us, for example, to break up a list into increasing segments (or non-decreasing ones). Your function should be realized as segment :: (a -> a -> Bool) -> [a] -> [[a]] and should work as shown below. (This one is pretty hard!)

   Example:

   Hugs> segment (<)  [1,2,3,0,1,2,2,4,6,8]
   [[1,2,3],[0,1,2],[2,4,6,8]]
   
   Hugs> segment (<=) [1,2,3,0,1,2,2,4,6,8]
   [[1,2,3],[0,1,2,2,4,6,8]]
   

   (What to return for an empty list as argument? Hmm, perhaps an empty list, but maybe a list containing the empty list ... which makes more sense? How would you argue for one or the other?)

8. Now write a function that will split a list in halves, i.e., into a front half and a back half: split :: [a] -> ([a],[a]). If there are excess elements, you should put the extra one in the second list, but do preserve the original order of elements.

   Example:

   Hugs> split "abcdefg"
   ("abc","defg")
   

9. Finally, write a function which "merges" a pair of lists together so that their elements occur in the result in alternating order (this is a basic step in shuffling cards, for example): riffle :: ([a],[a]) -> [a]. If either argument list is too long, just leave its elements at the end of the result.

   Example:

   Hugs> riffle ("abc","wxyzpqr")
   "awbxcyzpqr"
   

The last couple of functions can be combined to give a "card shuffler": just repeatedly split and riffle the "cards" (really, any list will do, e.g., numbers). It can be fun to experiment and see, for example, how many such "perfect shuffle" are required to retrun a list to its original order.