%
% Este ficheiro contem um texto em Literate Haskell
%    Partes do ficheiro são texto em LaTeX e outras em Haskell
%    
%  Métodos de Programação III
%  Universidade do Minho
%  2001/2002
%


\documentclass[12pt]{article}
\usepackage{a4wide}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage{color}
\usepackage{alltt}
\usepackage[portuges]{babel}


\usepackage[latin1]{inputenc}
\usepackage{latexsym}


\usepackage[dvips]{epsfig}
\usepackage{epic}
\usepackage{eepic}


\def\Ipe#1{\def\IPEfile{#1}\input{#1}}

\newenvironment{code}
{\textbf{Haskell Code} \hspace{1cm} \hrulefill \\ 
\smallskip 
\begin{center}
\begin{minipage}{.80\textwidth} 
\begin{alltt}\small}
{\end{alltt}
\end{minipage}
\end{center}
\hrule\medskip\noindent
}


\newtheorem{exercicio}{Exercise}[section]

\title{\sf\huge Advanced Functional Programming \\
\begin{tabular}{c}
{\small LMCC \& LESI}, {\small Universidade do Minho} \\
Strafunski: Exercises \\ 
\end{tabular}
}

\author{}
\date{}


%-------------------- Inicio do Documento -------------------------------

\begin{document}

\maketitle


\section{Refactoring of Haskell Programs}


One of the examples included in the Strafunski distribution is a
program \verb@HsTransform@ that transforms haskell source code. It
performs two simple transformations: the elimination of the do
constructor and the introduction of a new type definition. You can run
the program (in hugs) as follows:

\begin{alltt} \footnotesize
runhugs  +o -98 +N
 -P<StrategyLib>/examples/haskell:<StrategyLib>/library:<StrategyLib>/models/drift-default: 
 HsTransform <inputfile> <outputfile>
\end{alltt}

\noindent
where \verb+StrategyLib+ is the location where you installed
Strafunski's StrategyLib (version 4.0-beta), and \verb+inputfile+ and
\verb+outputfile+ are the names of the Haskell program to be
transformed, and the file where you want the transformed program to be
written to.


\begin{exercicio} 

Write a little test program that makes use of various \verb+do+
constructions. Run the transformation program on your test program and
inspect the resulting program. Run your test program as well as the
transformed program to see if they behave the same.

Note: Be sure to test nested do-expression and monadic let-expressions
inside do's.

\end{exercicio}

\noindent
For instance, consider the following example Haskell program:

\begin{code}
Put your input test module here
\end{code}

Running the \verb+HsTransform+ program on it produces the following output:

\begin{code}
Put the transformed module here
\end{code}

\noindent
The elimination of \verb+do+ expressions is defined in the Haskell
Report, in section 3.14. This transformation is expressed in
Strafunski as follows:


\begin{code}
doElim 	   :: (Term a, MonadPlus m) => a -> m a
doElim h   =  applyTP (innermost (monoTP doElim1)) h

doElim1    :: MonadPlus m => HsExp -> m HsExp
doElim1 (HsDo [HsQualifier e]) 	
  = return e
doElim1 (HsDo (HsQualifier e:stmts))	
  = return (HsInfixApp e (HsVar (hsSymbol ">>")) (HsDo stmts))
doElim1 (HsDo (HsGenerator p e:stmts))
  = do ok <- new_name
       return (letPattern ok p e stmts)
doElim1 (HsDo (HsLetStmt decls:stmts))
  = return (HsLet decls (HsDo stmts))
doElim1 _                      
  = mzero
\end{code}


The function \verb+doElim1+ implements a single \verb+do+-elimination
rewrite step. It follows the definition in the Haskell Report quite
closely, except that instead of Haskell's concrete surface syntax,
it's abstract syntax is used.

The function \verb+doElim+ completes the rewrite step \verb+doElim1+
into a complete transformation. The \verb+monoTP+ combinator lifts the
rewrite step to a \emph{generic} rewrite step, and the
\verb+innermost+ combinator applies this generic rewrite step
repeatedly according to the innermost traversal strategy, until a
fixpoint is reached (no more redexes remain).




\begin{exercicio} 

In section 3.6 of the Haskell report a translation of the
\verb@if_then_else@ construct is presented. Implement this translation
in a strategic function named \verb@ifElim@. Inorder to incorporate
this transformation in the distributed package, just modify the Main
module to import module \verb+IfElim+, and modify one line in the main
function into:

\begin{verbatim}
      iowrap (mpipe [doElim,data2newtypeConv,ifElim])
\end{verbatim}

\end{exercicio}

\noindent

\noindent
For instance, consider the following example Haskell program:

\begin{code}
module TestIfElim where
f a = if (a > 1)
      then a
      else -a
\end{code}

Running the \verb+HsTransform+ program on it produces the following output:

\begin{code}
module TestIfElim where
f a
  = case (a > 1) of
	True -> a
	False -> - a
\end{code}


This transformation is expressed in Strafunski as follows:

\begin{code}
module IfElim where

import Datatypes
import DatatypesTermInstances
import StrategyLib
import Monad

ifElim 	   :: (Term a, MonadPlus m) => a -> m a
ifElim h   =  ...

ifElim1    :: MonadPlus m => HsExp -> m HsExp

\end{code}


\begin{exercicio} 

Implement the list comprehension elimination according to the rules
defined in section 3.11 of the haskell report. (if you solve this
exercise please email Joost the solution to be included in the next
Strafunski distribution).

\end{exercicio}


%\section{Querying and Extracting XML Documents}








\end{document}