CS 465 Lab 2: More Haskell function definitions

This lab is intended as further practice using the Haskell programming language. We will not by this point have covered every Haskell feature we will need for the class, but the few things we will need later will be introduced as we go.

We focus here on function definitions which are most naturally defined by direct or indirect recursion, usually based on the recursive structure of lists. By “indirect” recursion we just mean that they might be defined using various higher-order functions from the Haskell Prelude that are themselves recursively defined, thus “wrapping up” a recursion up in a form which is easier to use.

I‘ve included descriptions in the last section below of a number of such functions from the Prelude that I think might be handy when you’re completing these exercises ... but everyone approaches these things differently, so you are not required to use these specific Prelude functions in your definitions. Nevertheless, it is worth trying them out to see how they work if you get stuck: perhaps they will provide some inspiration!

The main thing to try when you are starting out is to see if you can use the “template style” of definition for list arguments. (It’s not always the right way to get the function, but it almost always helps you get ideas.) Recall that the template style means that, for a function defined on a list argument, you start out with something like this:

f [] = ...

f (x:xs) = ... x ... (f xs) ...

In other words, think of what the function will do on an empty list and of what it will do on a not-so-empty list (composed of a head x and a tail xs), if given a recursive result based on xs. In the second case, it’s often easiest if you don’t worry about how the recursive result itself gets computed. Just pretend that it all works out and comes back the way you’d like: focus instead on what you will do with that recursive result to get the “whole result” you want to build from it and the x value.

It also helps to work from a specific, concrete example, building the more abstract, variable-based code you are working toward as you go along. See this page from the Intro. Functional class for advice about how you can structure this approach systematically.

The exercises

Try to define the following functions, with the given types:

1. power :: [a] -> [[a]]
   

   This function should return the “powerlist” of its list argument, akin to the powerset of a set. I.e., it should return a list of lists such that every list that is a sublist of the original argument will be an element of the result list. “But what about duplication and order, which are relevant for lists, but not for sets?” you might ask. If there are distinct-but-equal occurrences of elements in the argument list, it's easiest to treat them as distinct in the result as well. In other words, you should work in some sense with positions in the original list rather than with the items as values. With regard to order, you should try to preserve the order of items in the sub-lists as they appear in the original list.

   Example:

   Hugs> power "abc"
   
    [ "",  "c",  "b",  "bc",
     "a", "ac", "ab", "abc"]            -- Hint!
   
   Hugs> power [2,2,2]
   
   [[],[2],[2],[2,2],[2],[2,2],[2,2],[2,2,2]]   -- note treatment of duplicates
   

   (Note the ordering of the results and the behavior of repetitions in the second example. The odd formatting of the first example is actually intended as a big hint!)

2. perms :: [a] -> [[a]]
   

   Given a list xs, the function perms should produce the list of all permutations of the elements in 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 (just as in the power function): in other words, what matters is that you permute the positions in the list, not the specific elements.

   Example:

   Hugs> perms "abc"
   ["abc","bac","bca","acb","cab","cba"]
   
   Hugs> perms "aba"
   ["aba","baa","baa","aab","aab","aba"]   -- note treatment of duplicates
   

   (Hint: think about the results of a recursive call on the tail; how can you combine the head value into those results? Use a “helper function”.)

3. combos :: Int -> [a] -> [[a]]
   

   This function should take an integer and produce a list of all lists of that length, each of whose elements are drawn from the original list, in the order they appear there. Treat duplicates as in the previous two functions, i.e., as if the position matters but the value does not.

   Example:

   Hugs> combos 3 "abcde"
   ["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
   
   Hugs> combos 2 [1..6]
   [[1,2],[1,3],[1,4],[1,5],[1,6],[2,3],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6],[4,5],[4,6],[5,6]]
   
   Hugs> combos 4 [1..3]
   []
   

   Note that there are no “combos” of a given length if that length is longer than the argument list, so the result will just be empty (as in the third example). This can be a hint as to how the recursion should go: in particular, you may want to recurse on both the integer and list arguments.

4. transpose :: [[a]] -> [[a]]
   

   For the purposes of this function, we will think of a list of lists as if it were a matrix or 2-dimensional array, i.e., as a list of rows of elements (the rows should all be of the same length, but if they are not, they will likely be trimmed off as we go). The point of the function then is to exchange rows for columns and vice versa, i.e., to flip the “matrix” along its diagonal.

   Example:

   Hugs> transpose ["abc", "def", "ghi", "xyz"]
   ["adgx","behy","cfiz"]
   
   Hugs> trans [[1,2,3,4,5], [6,7,8,9,10]]
   [[1,6],[2,7],[3,8],[4,9],[5,10]]
   
   Hugs> trans ["abc", "pq", "xyz"]
   ["apx","bqy"]
   

   (Note how the last example shows that non-uniform row lengths will result in “trimming” to the shortest row length, although then the rows are swapped for columns.)



---

The last two functions both depend on the idea of a run-length encoding. This is a simple but common approach to data compression in situations where a given element of a sequence is likely to be repeated many times in a row: we recognize the repetitions by producing a list of pairs where the first half of each pair is an element from the list, and the second is a positive integer representing how many times it was repeated in the original list. Note that we treat each “run” of repetitions separately: if one run is interrupted by even just one other element, we produce separated pairs for each run (see the second example). The inverse function of run-length decoding takes such a list of pairs and restores the original list with repetitions.

(Note, by the way, that it is probably much easier to write the reldecode function than it is to write the relencode function! So you might want to do them in the opposite order than they are described here.

5. rlencode :: Eq a => [a] -> [(a,Int)]

   Example:

   Hugs> rlencode "aaaaabbbbccdddddddddee"
   [('a',5),('b',4),('c',2),('d',9),('e',2)]
   
   Hugs> rlencode "abcabc"
   [('a',1),('b',1),('c',1),('a',1),('b',1),('c',1)]
   

6. rldecode :: Eq a => [(a,Int)] -> [a]

   Example:

   Main> rld [(5,'a'),(4,'b'),(2,'c'),(9,'d'),(2,'e')]
   "aaaaabbbbccdddddddddee"
   
   Hugs> rldecode [('a',1),('b',1),('c',1),('a',1),('b',1),('c',1)]
   "abcabc"
   

   (If this seems like a hard function to write, it is: the best technique to use may be one called “accumulating parameters”: this involves carrying information into the function as an input, but then modifying that input parameter on the next recursive call. For example, we can use this technique to implement a reverse function for lists as follows: first we define a “helper function” that uses an extra list parameter (called st for “stack”) to push on each list element encountered in the main argument (i.e., the one on which we are recursing). This stack argument gets returned as the result from the helper function when we reach the final, empty list in the main argument (the list being reversed). Finally, the overall reversal function calls the helper with an initially empty stack in order to get the reversed result. The stack argument is the “accumulating parameter” because it changes or “accumulates” during the successive calls to the helper function.)

   rhelp st [] = st
   rhelp st (x:xs) = rhelp (x:st) xs
   
   rev xs = rhelp [] xs
   

Some handy functions you might want to know ☺

Here are a few handy functions that are defined in the Prelude that you might want to learn about and experiment with:

• map :: (a->b) -> [a] -> [b]
  You should already know map: it takes a function and a list of values and returns a list of results of applying the functions to the elements in the list, in the original order.
• zipWith :: (a->b->c) -> [a] -> [b] -> [c]
  zipWith is similar to map, but it takes a function of two arguments and two lists of arguments, and returns a list of results which come from applying the function to corresponding arguments from the two lists, in the original order. (If one of the lists is “short”, i.e., shorter than the other one, then the list of results is trimmed down to the length of the shorter list.)
• (++) :: [a] -> [a] -> [a]
  The (++) operator (written in infix format) just puts two lists together, one after the other, into a result list. It’s pronounced “append”.

• concat :: [[a]] -> [a]
  concat is an extended version of append which appends together all the lists in a list of lists, in order. The name comes from the word “concatenate”, but it doesn’t have anything to do with what the kitty was allowed to eat.
• (x:) :: [a] -> [a] (assuming x::a)
  If you have a value x, you can make a function which “sticks x on the front of a list” by writing (x:), with parentheses; this fixes the left argument of cons to be your x value, but leaves a function “waiting” for the list to be added to.
• repeat :: a -> [a]
  This function takes a value and returns an infinite list of items equal to that value; it is often useful in combinations with take below (to get some fixed number of items) or when used with zip or zipWith, since those functions will trim off an infinite-list argument to fit with some shorter list.
• replicate :: Int -> a -> [a]
  This function is like a finite version of repeat: it takes an integer (well, just a small Int) and a value and returns a list of that length made solely of items which are that value. (It is defined in terms of repeat and take.)
• take :: Int -> [a] -> [a]
drop :: Int -> [a] -> [a]
  These two functions each take an integer argument and a list argument and return some portion of the original list as a result. The take function “takes” the given number of elements off the front of the list and returns them, leaving off the remaining ones, whereas the drop function does the opposite, “dropping off” the given number of elements and returning this that remain. In each case, if the number to be taken or dropped is longer than the input list, the result is either just the whole list (for take) or just an empty list (for drop).