% -*- 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}