% -*- mode: LaTeX; compile-command: "mk" -*-
\documentclass{tufte-handout}
%include polycode.fmt
\arrayhs
\usepackage{../../hshw}
\title{\thecourse\ problem set 3}
\date{\small Revision 1: compiled \today\ at \currenttime}
\author{Due Tuesday 9 February, 2016}
\begin{document}
\maketitle
\exercise Implement a function
\begin{code}
xor :: [Bool] -> Bool
\end{code}
which returns |True| if and only if there are an odd number of |True|
values contained in the input list. It does not matter how many
|False| values the input list contains. For example,
\begin{spec}
xor [False, True, False] == True
xor [False, True, False, False, True] == False
\end{spec}
Your solution must be implemented using a fold.
\exercise Implement |map| as a fold. That is, complete the definition
\begin{code}
map' :: (a -> b) -> [a] -> [b]
map' f = foldr ...
\end{code}
in such a way that |map'| behaves identically to the standard |map|
function.
% \exercise Implement |foldl| using |foldr|. That is, complete the definition
% \begin{code}
% myFoldl :: (b -> a -> b) -> b -> [a] -> b
% myFoldl f base xs = foldr ...
% \end{code}
% in such a way that |myFoldl| behaves identically to the standard |foldl|
% function.
% \emph{Hint}: Study how the application of |foldr| and |foldl| work out:
% \begin{code}
% foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
% foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
% \end{code}
% \emph{Hint 2}: Ask me if you want another hint.
\exercise Recall the definition of a \term{binary tree} data
structure\marginnote{\url{http://en.wikipedia.org/wiki/Binary\_tree}}. The
\term{height} of a binary tree is the length of a path from the root
to the deepest node. For example, the height of a tree with a single
node is $0$; the height of a tree with three nodes, whose root has two
children, is $1$; and so on. A binary tree is \term{balanced} if the
height of its left and right subtrees differ by no more than $1$, and
its left and right subtrees are also balanced.
You should use the following data structure to represent binary trees.
Note that each node stores an extra |Integer| representing the size
(total number of nodes) of the binary tree at that node.
\begin{code}
data Tree a = Leaf
| Node Integer (Tree a) a (Tree a)
deriving (Show, Eq)
\end{code}
For this exercise, write a function, implemented using |foldr|,
\begin{spec}
mkBalancedTree :: [a] -> Tree a
mkBalancedTree = foldr ...
\end{spec}
which generates a balanced binary tree from a list of values.
For example, one sample output might be the following, also visualized
at right in \pref{fig:balanced}:
\begin{marginfigure}[1in]
\begin{diagram}[width=150]
import Data.Tree
import Diagrams.TwoD.Layout.Tree
data HTree a = Leaf
|| HNode Integer (HTree a) a (HTree a)
deriving (Show, Eq)
t :: HTree Char
t = HNode 10
(HNode 4
(HNode 1 Leaf 'F' Leaf)
'I'
(HNode 2 (HNode 1 Leaf 'B' Leaf) 'C' Leaf))
'J'
(HNode 5
(HNode 2 (HNode 1 Leaf 'A' Leaf) 'G' Leaf)
'H'
(HNode 2 (HNode 1 Leaf 'D' Leaf) 'E' Leaf))
htree2tree :: HTree a -> Tree (Maybe (Integer,a))
htree2tree Leaf = Node Nothing []
htree2tree (HNode h l a r) = Node (Just (h,a)) (map htree2tree [l,r])
drawHTree
= renderTree' drawNode drawEdge
. symmLayout' (with & slHSep .~ 4 & slVSep .~ 4)
. htree2tree
drawNode Nothing = mempty
drawNode (Just (h,a)) = text [a] <> circle 1 # fc white
drawEdge _ (Nothing,_) = mempty
drawEdge (_,p1) (_,p2) = p1 ~~ p2
dia = drawHTree t # centerXY # pad 1.1
\end{diagram}
\caption{A balanced tree} \label{fig:balanced}
\end{marginfigure}
\begin{code}
foldTree "ABCDEFGHIJ" ==
Node 10
(Node 4
(Node 1 Leaf 'F' Leaf)
'I'
(Node 2 (Node 1 Leaf 'B' Leaf) 'C' Leaf))
'J'
(Node 5
(Node 2 (Node 1 Leaf 'A' Leaf) 'G' Leaf)
'H'
(Node 2 (Node 1 Leaf 'D' Leaf) 'E' Leaf))
\end{code}
Your solution might not place the nodes in the same exact order, but
it should result in a balanced tree, with each subtree having a
correct computed size.
\exercise Implement a fold for the type |Nat|, defined by
\begin{spec}
data Nat where
Z :: Nat
S :: Nat -> Nat
\end{spec}
\exercise Describe the set of all possible functions of type |forall
a. (a -> a) -> a -> a|.
\exercise \marginnote{You will need to enable the |Rank2Types|
extension, by putting |{-# LANGUAGE Rank2Types #-}| at the top of
your |.hs| file.} Implement (sensible) functions with types \[ |Nat
-> (forall a. (a -> a) -> a -> a)| \] and \[ |(forall a. (a -> a) -> a
-> a) -> Nat|. \] Note carefully where the parentheses are in the
above types. We haven't specifically discussed types like this, but
see if you can figure out what they mean; ask me if you need a hint.
\bigskip \hrule \bigskip
The following exercises concern the type of \emph{rose trees}, where
each node contains a value of some type and \emph{any number}
of children (including the possibility of \emph{zero} children):
\begin{spec}
data Rose a where
Node :: a -> [Rose a] -> Rose a
\end{spec}
\exercise Implement a function \[ |mapRose :: (a -> b) -> Rose a -> Rose
b|. \]
\exercise Implement a fold for |Rose a|. \marginnote{I'm not telling
you the type; that's part of the fun.}
%% TODO: next time, make some pictures to illustrate height and width.
\begin{marginfigure}
\begin{diagram}[width=100]
import EdgeColorTree
dia = drawEdgyTree exampleTreeHeight # frame 0.2
\end{diagram}
\caption{A tree with height $4$} \label{fig:height}
\end{marginfigure}
\exercise Using your fold, implement a function \[ |height :: Rose a
-> Integer|. \] Again, the height of a tree is defined as the length
of the deepest path from the root to any leaf. The height of a leaf
(a node with no children) is therefore zero. An example is shown in
\pref{fig:height}.
\begin{marginfigure}
\begin{diagram}[width=100]
import EdgeColorTree
dia = drawEdgyTree exampleTreeWidth # frame 0.2
\end{diagram}
\caption{A tree with width $6$} \label{fig:width}
\end{marginfigure}
\exercise The \emph{width} of a tree is defined as the length of the
longest path between two leaves. (That is, a path between two leaves
starts at a leaf, goes up the tree for a while, and then goes back
down to another leaf.) Be careful to note that, as illustrated in
\pref{fig:width}, the maximum-width path may not pass through the root
of the tree!
Use your fold to implement a function \[ |width :: Rose a ->
Integer|. \] \textbf{Note}: this is much trickier than it may first
appear. You will probably need a helper function. Please ask for
hints if you are stuck.
\bigskip \hrule \bigskip
Read sections 1--5 of John Backus's 1977 Turing Award lecture,
\marginnote{The rest of this lecture has lots of cool stuff in it too;
you're welcome to read more if you find it interesting, although
beware that it starts getting extremely hairy about halfway
through.} \emph{Can Programming Be Liberated from the von Neumann
Style? A Functional Style and Its Algebra of Programs}, available
from \url{http://worrydream.com/refs/Backus-CanProgrammingBeLiberated.pdf}.
\exercise Backus delivered this lecture almost 40 years ago. In what
ways do his remarks still apply today, and in what ways are they
outdated? Give two specific examples of each.
\exercise Translate the Innerproduct function, defined in section 5.2,
into Haskell. (You may use the standard |transpose| function, defined
in the |Data.List| module.)
\end{document}