Exercises for week 7

1. Lab 1 revisited.

Recall the function buildHistogram from Lab 1. You probably defined it by explicit recursion over the list of observations. Can you redefine it by folding over this list?

2. Folding with bracketing to the left.

As discussed in chapter 9, we can understand the action of foldr as

foldr ¤  e [x1, x2, ... xn] = x1 ¤ (x2 ¤ ... ¤ (xn ¤ e)...)

(Here I used the (illegal) operator symbol ¤ to indicate an "arbitrary" operator). Define a function foldl that is similar but brackets to the left and, accordingly, puts the unit element e in the beginning of the expression. So we want

foldl ¤  e [x1, x2, ... xn] = (...((e ¤ x1) ¤ x2)... ) ¤ xn

Note: Also foldl is in the Prelude, so you have to come up with another name to test your definition.

After having done this, we could define e.g. sum using foldl instead of foldr. Would there be any advantage in doing so?

3. Minimal spanning trees.

This is a harder programming problem.

We consider the following problem: We are given n points in the plane and want to connect some of them pairwise by straight line segments ("roads") in such a way that

We can travel between any two of the given points using the roads.
The total road length is as small as possible.

For example, if the points are those given to the left below, the solution is shown to the right.

Hopefully, it is intuitively clear that the solution to this problem will never include cycles, i.e. closed paths leading away from a point along one road and coming back along another. Connected graphs without cycles are called trees. A spanning tree is one which connects all the points. Finally, a minimal spanning tree is a spanning tree of minimal total length. The problem of finding a minimal spanning tree for a given set of points occurs frequently in applications.

The problem can be solved by the following famous algorithm (Kruskal's algorithm):

form the list of all edges, i.e. two-element sets {P,Q} of distinct points.
sort the edge list so that the shortest edges (where the length of an edge is the ordinary distance between its two points) come first.
Start with the empty graph, i.e. only the points, and add edges as follows.
Go through the sorted edge list from beginning to end and add the road (a line segment) described by this edge to the graph if this does not give a cycle. For example, at one stage of the construction of the above solution we will have the following situation:

The shortest edge that has not yet been considered is now {P,Q} but this gives a cycle and is discarded. The next two are {S,T} and {S,Q}, which are also discarded. Thereafter comes is {Q,R}, which will be added.
When all edges have been connected, the algorithm terminates.

It is far from obvious that this actually gives a minimal spanning tree, but for now we take this fact for granted.

Your task is to program this algorithm. Your function should take a list of points as input and produce a list of edges, those that form a minimal spanning tree. The hard part is the test of whether a proposed edge gives a cycle. You will have to design an auxiliary data structure to record which edges are connected at each stage and update this as you add new edges.

4. Giving Change

This and the next question are exam questions from last year.

This question concerns finding change. Suppose you have a collection of coins in your pocket, which we represent by a list of numbers such as [1,1,5,5,5,10,10]. Then you can pay 16kr by paying three 5kr coins and a 1kr, but you cannot pay 18kr at all. Suppose the person you are paying also has some coins, say [1,1,1,5]. Then you can pay 18kr by paying 20kr, and receiving 2kr in change. We will design functions to decide whether one person can pay another a specific amount, with or without giving change.

Define a function
```
subsets :: [a] -> [[a]]
```
which given a list, returns a list of all the ways of choosing some of the list elements. For example,
```
subsets [1,2,3] ==
  [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
```
(the order of this list doesn't matter here).
Define a function
```
amounts :: [Int] -> [Int]
```
which given a list of the coins in your pocket, returns a list of all the amounts you can pay using those coins.
Define a function
```
withChange :: [Int] -> [Int] -> [Int]
```
which, given a list of the coins in the first person's pocket, and a list of the coins in the second person's pocket, returns a list of all the amounts the first person can pay the second assuming that the second person is willing to provide change. The result should not contain negative numbers.
The subsets function you wrote above is inefficient for this problem, because it ignores the fact that we may have many coins with the same value in our pockets. For example,
```
subsets [1,1] ==
  [[],[1],[1],[1,1]]
```
where the two subsets [1] represent choosing different coins, but with the same value. Since we do not care which coin we actually pay with, we do not need to consider these subsets separately. We can improve the efficiency of our program by working with bags instead, which we represent by lists of pairs of a coin value, and the number of coins of that value in the bag. For example, [1,1,5,5,5,10,10] corresponds to the bag [(1,2),(5,3),(10,2)].
- Define a function
```
bag :: Eq a => [a] -> [(a,Int)]
```
  which converts a set to a bag.
- Define a function
```
set :: [(a,Int)] -> [a]
```
  which converts a bag back into a set.
- Define a function
```
subbags :: [(a,Int)] -> [[(a,Int)]]
```
  which returns a list of every bag we can make by choosing some of the elements of the given bag. For example,
```
subbags [(1,2)] ==
  [[],[(1,1)],[(1,2)]]
```
How would you use these functions to improve your function withChange?

5. Generating Web Pages

Your task in this question is to write a program that converts a list of names and email addresses in a file, such as

John Hughes rjmh@cs.chalmers.se
Mary Sheeran ms@cs.chalmers.se

into a web page which when viewed in a browser looks like this,

John Hughes, rjmh@cs.chalmers.se
Mary Sheeran, ms@cs.chalmers.se

Clicking on the underlined links should send mail to the given address.

The web page is to be generated as HTML; for example, the web page in the example can be represented by the following HTML source:

<ul>
<li>John Hughes, 
    <a href="mailto:rjmh@cs.chalmers.se">
      rjmh@cs.chalmers.se
    </a></li>
<li>Mary Sheeran, 
    <a href="mailto:ms@cs.chalmers.se">
      ms@cs.chalmers.se
    </a></li>
</ul>

Here the <ul> tag introduces a bulleted list, the <li> tag introduces a list element, and the <a href=...> introduces a link. The layout of HTML source is not important: only the HTML tags affect what one sees in a browser. You need not reproduce the layout used above, only the tags.

You can identify email addresses because they contain the character '@'. Write a function
```
isEmail :: String -> Bool
```
which returns True when it is passed an email address.
Write a function
```
nameList :: String -> [(String,String)]
```
which converts the contents of the first file into a list of pairs of names and email addresses. In the example above, the result should be
```
[("John Hughes","rjmh@cs.chalmers.se"),
 ("Mary Sheeran","ms@cs.chalmers.se")]
```
Hint: The functions lines, words, and unwords are useful in this part.
Define a function
```
formatNames :: [(String,String)] -> String
```
which converts the list of names and email addresses produced in the last part to HTML source, following the structure of the example HTML file above. You may wish to define one or two `help functions' to simplify your task.
Define a function
```
generateHtml :: IO ()
```
which reads names and email addresses from a file "names", and writes the generated web page to a file "names.html".