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
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
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
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.
Try to define the following functions, with the given types:
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.
(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!)
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]] -- note treatment of duplicates
perms :: [a] -> [[a]]
Given a list
xs, the function
perms should produce
the list of all permutations of the elements in
i.e., a list of all lists which are a re-ordering of the elements in
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.
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”.)
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.
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.
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.
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.
rlencode :: Eq a => [a] -> [(a,Int)]
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)]
rldecode :: Eq a => [(a,Int)] -> [a]
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
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
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]
zipWithis 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]
(++)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]
concatis 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
If you have a value
x, you can make a function which “sticks
xon the front of a list” by writing
(x:), with parentheses; this fixes the left argument of cons to be your
xvalue, 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
takebelow (to get some fixed number of items) or when used with
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
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
takefunction “takes” the given number of elements off the front of the list and returns them, leaving off the remaining ones, whereas the
dropfunction 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