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

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

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

(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],[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`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”.)`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.`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.)

`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)]

`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

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

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]`

`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]`

`(++)`

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`

)`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]`

`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]`

`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]`

`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`

).