%include Haskell.fmt

\begin{question}{Higher-order Functions}{15}

\begin{minipage}{12.2cm}
\setlength{\parskip}{0.25cm}
Take a look at the data type |Tree|, and consider the example tree.

\begin{code}
data Tree a = Bin (Tree a) a (Tree a) | Leaf deriving Show

tree :: Tree Int
tree = Bin (Bin (Bin Leaf 1 Leaf) 2 (Bin Leaf 3 Leaf)) 4 (Bin Leaf 5 Leaf)
\end{code}
\end{minipage}
\begin{minipage}{4cm}
\image{tree.pdf}
\end{minipage}

\subquestion
Write a higher-order function |foldTree|, which can be used to compute a value for a tree.
Also write down the type of |foldTree|.
All functions in the remainder of this question have to be written with this higher-order function. 

\answer{
\begin{code}
foldTree :: (result -> a -> result -> result, result) -> Tree a -> result
foldTree alg@(bin, leaf) tree =
   case tree of
      Bin l a r  -> bin (foldTree alg l) a (foldTree alg r)
      Leaf       -> leaf
\end{code}}

\subquestion
Use |foldTree| to define the following two functions:
\begin{code}
height   :: Tree a -> Int
mapTree  :: (a -> b) -> Tree a -> Tree b
\end{code}
The function |height| yields the height of a tree, whereas |mapTree| applies a given
function to all the elements of a tree. 
For example, |height tree| gives |3|, and |mapTree even tree| returns
|Bin (Bin (Bin Leaf False Leaf) True (Bin Leaf False Leaf)) True (Bin Leaf False Leaf)|.

\answer{
\begin{code}
height     = foldTree (\l _ r -> 1 + max l r, 0)
mapTree f  = foldTree (\l a r -> Bin l (f a) r, Leaf)
\end{code}}

\subquestion
Use |foldTree| to write a function for collecting the elements of a tree in a depth-first order.
\begin{code}
depthfirst :: Tree a -> [a]
\end{code}
For instance, |depthfirst tree| gives |[1,3,2,5,4]|.
Take into account that concatenation of two lists (|++|) requires a traversal over the left 
operand: prevent quadratic behavior for |depthfirst|.

\answer{
\begin{code}
depthfirst tree =
   foldTree (\f a g -> f . g . (a:), id) tree []
\end{code}}

\subquestion
Use |foldTree| to write a function for collecting the elements of a tree in a breadth-first order.
\begin{code}
breadthfirst :: Tree a -> [a]
\end{code}
For instance, |breadthfirst tree| gives |[4,2,5,1,3]|. For this part, you don't have to worry about the efficiency of (|++|).

\answer{
Idea: use a list of lists. Elements in the same list appear at the same
depth in the tree.
\begin{code}
breadthfirst  =  concat 
              .  takeWhile (not . null)
              .  foldTree (\t1 a t2 -> [a] : zipWith (++) t1 t2, repeat [])
\end{code}}

\end{question}