CS 254 Lab 4: Recursion, combinatorics, etc.

Here are some more little exercises involving recursion: you're also welcome to use lambda notation or list comprehensions for these exercises ... except for the first one (combinations): it would be too easy to do with list comprehensions!

  1. 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"
[(1,'a'),(1,'b'),(1,'c'),(1,'d'),(2,'a'),(2,'b'),(2,'c'),(2,'d'),(3,'a'),(3,'b'),(3,'c'),(3,'d')]
  2. Using the function combos, you should be able to easily write a similar function, called tabulate, which applies a binary function to all possible arguments from two lists, returning a list of list of results. This function can be used, for example, to write out a "table of operations" for operators like (+) and (*) 
    tabulate :: (a -> b -> c) -> [a] -> [b] -> [[c]]

Hugs> tabulate (*) [1..3] [10..12]
[[10,11,12],[20,22,24],[30,33,36]]

    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: 

    Hugs> tabulate (*) [1..3] [1..4]
[[1, 2, 3, 4], [2, 4, 6, 8], [3, 6, 9, 12]]

Hugs> prTable $$

	1       2       3       4
	2       4       6       8
	3       6       9       12
  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"
["abc","bac","bca","acb","cab","cba"]

Hugs> perms "aba"
["aba","baa","baa","aab","aab","aba"]   -- note treatment of duplicates
  4. 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?)

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

    6.