Here is a list of exercises related to project management, testing, and laziness.

The file `Game.hs`

implements a small guessing game, all in one file. You can run it using `runghc Game.hs`

on the terminal prompt. The goal of this first exercise is to turn this file into a proper Cabal project:

- Initialize a project with one executable stanza.
- Separate the pure part of the game (data type declarations and functions
`next`

and`step`

) into a separate module, which should be imported by the`Main`

module. - If you use Stack, initialize also the
`stack.yaml`

file. - Run the game using Cabal or Stack.

In this assignment we want to build a library to generate smooth permutations. Given a list of integers `xs`

and an integer `d`

, a *smooth permutation of xs with maximum distance d* is a permutation in which the difference of any two consecutive elements is at most

`d`

. A naïve implementation just generates all the permutations of a list,```
split [] = []
split (x:xs) = (x, xs) : [(y, x:ys) | (y, ys) <- split xs]
perms [] = [[]]
perms xs = [(v:p) | (v, vs) <- split xs, p <- perms vs]
```

and then filters out those which are smooth,

```
smooth n (x:y:ys) = abs (y - x) < n && smooth n (y:ys)
smooth _ _ = True
smoothPerms :: Int -> [Int] -> [[Int]]
smoothPerms n xs = filter (smooth n) (perms xs)
```

**Exercise 1:** *Packaging and documentation*

- Create a library
`smoothies`

which exports`perms`

and`smoothPerms`

from a module`SmoothPermsSlow`

. You should be able to build the package by just running`cabal build`

in the top level directory. - Document the exported functions using Haddock.

**Exercise 2:** *Testsuite*

- Write a
`SmothPermsTest`

module with a comprehensive set of properties to check that`smoothPerms`

works correctly. - Integrate your testsuite with Cabal using
`tasty`

(here is how you do so).

**Exercise 3:** *Implementation with trees*

The initial implementation of `smoothPerms`

is very expensive. A better approach is to build a tree, for which it holds that each path from the root to a leaf corresponds to one of the possible permutations, next prune this tree such that only smooth paths are represented, and finally use this tree to generate all the smooth permutations from. Expose this new implementation in a new `SmoothPermsTree`

module.

- Define a data type
`PermTree`

to represented a permutation tree. - Define a function
`listToPermTree`

which maps a list onto this tree. -
Define a function

`permTreeToPerms`

which generates all permutations represented by a tree.At this point the

`perms`

functions given above should be the composition of`listToPermTree`

and`permTreeToPerms`

. - Define a function
`pruneSmooth`

, which leaves only smooth permutations in the tree. - Redefine the function
`smoothPerms`

.

Integrate this module in the testsuite you developed in the previous exercise.

**Exercise 4:** *Unfolds*

Recall the definition of `unfoldr`

for lists,

```
unfoldr :: (s -> Maybe (a, s)) -> s -> [a]
unfoldr next x = case next x of
Nothing -> []
Just (y, r) -> y : unfoldr next r
```

We can define an unfold function for binary trees as well:

```
data Tree a = Leaf a | Node (Tree a) (Tree a)
deriving Show
unfoldTree :: (s -> Either a (s, s)) -> s -> Tree a
unfoldTree next x = case next x of
Left y -> Leaf y
Right (l, r) -> Node (unfoldTree next l) (unfoldTree next r)
```

Define the following functions in a new module `UnfoldUtils`

, which should *not* be exposed by your package. Define the functions using `unfoldr`

or `unfoldTree`

, as required.

`iterate :: (a -> a) -> a -> [a]`

. The call`iterate f x`

generates the infinite list`[x, f x, f (f x), ...]`

.`map :: (a -> b) -> [a] -> [b]`

.`balanced :: Int -> Tree ()`

, which generates a balanced binary tree of the given height.`sized :: Int -> Tree Int`

, which generates any tree with the given number of nodes. Each leaf in the returned tree should have a unique label.

Define a new module `SmoothPermsUnfold`

with an `unfoldPermTree`

function which generates a `PermTree`

as defined in the previous exercise. Then use that `unfoldPermTree`

to implement a new version of `listToPermTree`

and `smoothPerms`

.

**(Optional)** Write the following proofs as comments in the `UnfoldUtils`

module.

- Prove using induction and equational reasoning that the version of
`map`

you defined using`unfoldr`

coincides with the definition of`map`

by recursion. -
We define the

`size`

of a binary tree as the number of internal nodes.`size (Leaf _) = 0 size (Node l r) = 1 + size l + size r`

What is the

`size`

of a balanced tree as generated by`balanced`

? Prove your result using induction and equational reasoning.

**Exercise 5:** *Performance*

- Use the
`criterion`

package to make and run benchmarks for the given naïve solution and the implementations using trees and unfolds, in order to find out whether your solution really gives higher performance. - Use heap profiles to analyse and draw conclusions about the differences.