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


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

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

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