q3.tex

%%% Question 3 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\question This question is about user-defined types and type classes.
\begin{parts}
	
	\part Consider a variant of rose trees where elements are stored in nodes rather than leaves such that, for example, the following is a valid definition:
	\begin{small}
		\begin{verbatim}
		tree :: Tree String 
		tree = Node "Sakura" [Node "Rubber" []]
		\end{verbatim}
	\end{small}
	
	\begin{subparts}
		
		\subpart[3] Give a suitable definition for the \haskellIn{Tree} type. \droppoints 
		
		\begin{solution}
			\emph{Application.}
			\begin{small}
				\begin{verbatim}
				data Tree a = Node a [Tree a]
				\end{verbatim}
			\end{small}
		\end{solution}
	
		\subpart[1] A collection of trees is referred to as a \emph{forest}. Define a suitable \emph{type alias} for \haskellIn{Forest a} which represents zero or more trees of  elements of type \haskellIn{a}. \droppoints 
		
		\begin{solution}
			\emph{Application.}
			\begin{small}
				\begin{verbatim}
				type Forest a = [Tree a]
				\end{verbatim}
			\end{small}
		\end{solution}
	
		\subpart[4] The \haskellIn{Tree} type is a functor. Define a suitable instance of Haskell's \haskellIn{Functor} type class for it. Your solution should obey the functor laws, although you do not need to prove this. \droppoints 
		
		\begin{solution}
			\emph{Application.} 
			\begin{small}
				\begin{verbatim}
				instance Functor Tree where 
				     fmap f (Node x ts) = Node (f x) (fmap (fmap f) ts)
				\end{verbatim}
			\end{small}
		\end{solution}
	
		\subpart[4] Define a suitable instance of Haskell's \haskellIn{Foldable} type class for the \haskellIn{Tree} type.  \droppoints 
		
		\begin{solution}
			\emph{Application.}
			\begin{small}
				\begin{verbatim}
				instance Foldable Tree where 
				  foldr f z (Node x ts) = 
				    f x (foldr (\t r -> foldr f r t) z ts)
				\end{verbatim}
			\end{small}
		\end{solution} 
		
	\end{subparts}

	\part A zipper is a purely functional data structure which can be used to efficiently traverse another data structure if the same element needs to be accessed repeatedly or element access is relative to the last-accessed element by allowing a particular element of the data structure to be ``focused''. Suppose that we have an implementation of binary trees as follows:
	\begin{small}
		\begin{verbatim}
		data BinTree a = BinLeaf a | BinNode (BinTree a) (BinTree a)
		\end{verbatim}
	\end{small}
	
	\begin{subparts}
		
		\subpart[2] Define an algebraic data type named \haskellIn{Direction} so that it has two constructors with the following types:\\
		\haskellIn{L :: BinTree a -> Direction a} \\
		\haskellIn{R :: BinTree a -> Direction a} \droppoints 
		
		\begin{solution}
			\emph{Application.}
			\begin{small}
				\begin{verbatim}
				data Direction a = L (BinTree a) | R (BinTree a)
				\end{verbatim}
			\end{small}
		\end{solution}
	
		\subpart[1] A zipper data structure for \haskellIn{BinTree} values can then be defined as:
		 
		\begin{small}
			\begin{verbatim}
			data BinZipper a = Pos [Direction a] (BinTree a)
			\end{verbatim}
		\end{small}
	
		What is the type of \haskellIn{Pos}? \droppoints
		
		\begin{solution}
			\emph{Comprehension.}\\
			\haskellIn{Pos :: [Direction a] -> BinTree a -> BinZipper a}
		\end{solution}
	
		\subpart[1] The definition of the \haskellIn{BinZipper} type above can be used to represent a position within a binary tree, where \haskellIn{[Direction a]} represents a list of directions that were taken from the root and \haskellIn{BinTree a} is the node or leaf that is currently in ``focus''. Define a function
		\begin{center}
			\haskellIn{fromTree :: BinTree a -> BinZipper a}
		\end{center} 
		which can be used to create a zipper for a given binary tree. \droppoints 
		
		\begin{solution}
			\emph{Application.}
			\begin{small}
				\begin{verbatim}
				fromTree :: BinTree a -> BinZipper a 
				fromTree t = Pos [] t
				\end{verbatim}
			\end{small}
		\end{solution}
		
		\subpart[2] Define a function 
		\begin{center}
			\haskellIn{view :: BinZipper a -> Maybe a}
		\end{center}
		which gets the element that is currently in the view, if there is one. For example, \haskellIn{view (Pos p (BinLeaf x))} should evaluate to \haskellIn{Just x}. \droppoints 
		
		\begin{solution}
			\emph{Application.}
			\begin{small}
				\begin{verbatim}
				view :: BinZipper a -> Maybe a 
				view (Pos ds (BinLeaf x)) = Just x 
				view (Pos ds _) = Nothing
				\end{verbatim}
			\end{small}
		\end{solution}
		
		\subpart[4] Define two functions 
		\begin{center}
			\haskellIn{turnRight :: BinZipper a -> Maybe (BinZipper a)}\\
			\haskellIn{turnLeft  :: BinZipper a -> Maybe (BinZipper a)} 
		\end{center}
		which, given a current position in a tree, go down the right or left subtree, respectively. For example, \haskellIn{turnRight (Pos [] (BinNode l r))} should evaluate to \haskellIn{Just (Pos [R l] r)}. \droppoints 
		
		\begin{solution}
			\emph{Application.}
			\begin{small}
				\begin{verbatim}
				turnRight :: BinZipper a -> Maybe (BinZipper a)
				turnRight (Pos ds (BinNode l r)) = Just (Pos (R l:ds) r)
				turnRight (Pos ds (BinLeaf _))   = Nothing
				
				turnLeft :: BinZipper a -> Maybe (BinZipper a)
				turnLeft (Pos ds (BinNode l r)) = Just (Pos (L r:ds) l)
				turnLeft (Pos ds (BinLeaf _))   = Nothing
				\end{verbatim}
			\end{small}
		\end{solution}
	
		\ifprintanswers \else \pagebreak \fi
		
		\subpart[3] Define a function 
		\begin{center}
			\haskellIn{back :: BinZipper a -> Maybe (BinZipper a)}
		\end{center}
		which shifts the focus of the zipper up the tree to the parent of the node that is initially in focus. \droppoints 
		
		\begin{solution}
			\emph{Application.} 
			\begin{small}
				\begin{verbatim}
				back :: BinZipper a -> Maybe (BinZipper a)
				back (Pos [] _) = Nothing 
				back (Pos (L r:ds) t) = Just (Pos ds (BinNode t r))
				back (Pos (R l:ds) t) = Just (Pos ds (BinNode l t))
				\end{verbatim}
			\end{small}
		\end{solution}
		
	\end{subparts}
\end{parts}