CS 154 Lab 3: Recursion, combinatorics, etc.

Here are some more exercises: the simpler ones are pretty straightforward, but the later ones will involve some recursion. You are encouraged to use the “template style” or even folds to get things going, especially for the recursive ones. Also be sure to check out the page with the example-based approach to code development for ideas about how to proceed.

  1. Here’s a simple little warm-up, based on text ideas, but requiring a type definition. Let’s define a two-valued type, similar to Booleans, but with the meaning of distinguishing between vowels, consonants and other characters:

    data Cat = Vow | Con | Other  deriving (Show, Eq)
    (Include this definition near the top of your file.)

    The interpretation of Cat is “character category” and it allows us to distinguish between the vowel and consonant categories (or “other” characters) in a typical Haskell-y abbreviated fashion. (Let’s agree to consider 'y' a vowel by default, just because.)

    You should define a classifying or “categorizing” function on values of type Char which takes a character argument and tells whether it is a vowel, consonant or neither; i.e., you should write a function cat :: Char -> Cat. (This shoudn’t be too hard, but will require working with the new datatype.)

    OK, now for the actual working part of the exercise: define a function which will take a piece of text (i.e., a String) and, based on a Cat argument value, replace every character of the type in the string with an asterisk ('*'); the non-selected categories of characters should remain unchanged.

    So you’ll write a function replace that behaves as follows:

    replace :: Cat -> String -> String
    Hugs> replace Vow "kitty cat"
    "k*tt* c*t"
    Hugs> replace Con "hot diggity dog"
    "*o* *i**i*y *o*"

    (This part shouldn’t be too hard either, but this is just a warm-up exercise, after all.)

    Note that Other is a possible argument to the function, so that vowels and consonants might survive unchanged, but spaces, punctuation, tabs, etc., would be converted to asterisks.

  2. Let’s do some math with non-integer numbers. Specifically, we’ll work with circles in a geometric plane, conceived in terms of cartesian co-ordinates (you know, the old “(x,y)” routine). You can write these values into Haskell by just using decimal points in your numbers.

    More specifically, let’s work with circles represented in terms of three numbers, an x-coordinate, a y-coordinate (these two represent the center of the circle), and a radius (the distance from the center of the circle to it’s “edge”, i.e., the circle itself). We can define a circle datatype as follows, where the constructor Circle will build a circle representation from three floating-point numbers:

    data Circle = Circle Float Float Float  deriving Show
    (Again, just add this line to your lab file.)

    Now for the fun part: write a function overlap which will take two Circles as argument and tell (as a Bool result) whether they overlap or not. Recall that two circles overlap if the distance between them is less than the sum of their radii. (The distance between two points, as you’ll recall, is the square root of the sum of the squares of the differences between their respective coordinates.) Note that Haskell has a sqrt function to do the square roots for you (I pronounce it “squirt”, but maybe that’s just me ...).

    overlap :: Circle -> Circle -> Bool
    Hugs> overlap (Circle 0.0 0.0 3.0) (Circle 2.0 2.0 1.0)
    Hugs> overlap (Circle 1.0 1.0 1.0) (Circle 5.0 5.0 1.0)

    Clarification: You should count only one overlap for each pair of distinct circles that overlap. In other words, don’t count circles overlapping with themselves, but also don’t count two distinct circles overlapping with each other twice, just count them once.

  3. Write a function called perms: given a list xs, it should produce the list of all permutations of the xs, i.e., a list of all lists which are a re-ordering of the elements in xs. If there are duplicate elements, they should be considered effectively different: in other words, what matters is that you permute in some sense the positions in the list, not the specific elements (although of course your answer lists will contain the original elements).
    perms :: [a] -> [[a]]
    Hugs> perms "abc"
    Hugs> perms "aba"
    ["aba","baa","baa","aab","aab","aba"]   -- note treatment of duplicates
  4. Write a function called combos: when given two lists xs and ys, it should produce a list of all combinations (as pairs) of the form (x,y), such that x comes from the list xs and y from the list ys. (In particular, make sure that duplicate elements in the lists yield duplicate elements in the results.)
    combos :: [a] -> [b] -> [(a,b)]
    Hugs> combos [1..3] "abcd"
  5. Given your definition of the overlap and combos functions, you should be able to write a function that takes a list of circles and returns the number of distinct pairwise overlaps between circles in the list. (Just to be sure, we won’t consider a circle to overlap with itself, so be sure to exclude that possibility somehow in the count.)

    overlaps :: [Circle] -> Int

    (I’ll supply some sample test data in a separate file over the weekend.)

    NEW!! OK, here is some test data, not as a separate file, but just as a paste-able block:

    circs1 = [ Circle 2.0 5.0 1.0, Circle 13.0 7.0 1.0, Circle 7.0 4.0 3.0, 
               Circle 4.0 7.0 2.0, Circle 10.0 7.0 2.0 ]
    {- 4 overlaps -}
    circs2 = [ Circle 5.0 5.0 1.0, Circle 5.0 5.0 2.0, Circle 5.0 5.0 3.0 ]
    {- 3 overlaps -}
    circs3 = [ Circle 6.5 8.0 2.0, Circle 3.0 7.0 1.0, Circle 3.0 3.0 2.0,
               Circle 6.5 5.5 1.0, Circle 3.0 5.5 1.0, Circle 6.5 3.0 2.0 ]
    {- 5 overlaps -}

  6. We can represent a matrix as a list of lists, like this:
    	[ [ 1, 2, 3 ], 
    	  [ 4, 5, 6 ],
    	  [ 7, 8, 9 ]  ]
    The transpose of a matrix is a new matrix where the roles of the columns and rows are exchanged; for a list of lists, this means in some sense that we turn the list of lists "inside out. So the transpose of the example above is:
    	[ [ 1, 4, 7 ], 
    	  [ 2, 5, 8 ],
    	  [ 3, 6, 9 ]  ]

    Write a function called trans that will transpose a lists of lists as above. Note: if there are "short" lists within the outer list, you could just trim all the lists in the result to match. (Can you think of other reasonable behaviors?)

  7. A simple "encryption" mechanism used in Usenet newsgroups, back in the 1900's, was called ROT13. It didn't actually encrypt text (it's too easily inverted), but rather was used to hide text from being immediately read. This feature was useful for delaying punch lines to jokes, or movie spoilers, for example, or as a simple way to block potentially objectionable material (one had to overtly "decrypt" the text, thus implicitly agreeing not to be offended).

    (See Wikipedia's entry on ROT13 for more information, history and trivia. Furrfu! Fnir zr sebz gur abbof!) 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. (NB: all non-alphabetic symbols are preserved unchanged.) Note that upper-and lower-case letters must be treated a bit differently, since they lie in different alphabetic ranges. (In Haskell, you can achieve the rotation by first converting characters to numbers in the ASCII code via the ord function in the Char module; then you will need some arithmetic, and probably the mod function, to hep the rotation. But there are other approaches ... .)

    Define a rot function that takes a number n (usually 13) and a string, and returns a new string to which the technique has been applied. By way of example:

    Hugs> rot 13 "This is a message; it is a test, just a test."
    "Guvf vf n zrffntr; vg vf n grfg, whfg n grfg." 

    (Of course, 13 was used in the ROT13 technique since it allowed one to "toggle" between obscured and plain text by simply applying the function again; in other words, it was self-inverse with n=13.)