Here is a list of exercises related to project management, testing, and laziness.
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:
step) into a separate module, which should be imported by the
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
smoothPermsfrom a module
SmoothPermsSlow. You should be able to install the package by just running
cabal installin it.
Exercise 2: Testsuite
SmothPermsTestmodule with a comprehensive set of properties to check that
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
PermTreeto represented a permutation tree.
listToPermTreewhich 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
pruneSmooth, which leaves only smooth permutations in the tree.
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
unfoldTree, as required.
iterate :: (a -> a) -> a -> [a]. The call
iterate f xgenerates 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
(Optional) Write the following proofs as comments in the
mapyou defined using
unfoldrcoincides with the definition of
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
criterionpackage 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.