\documentclass{llncs}
\usepackage{times}
\usepackage[T1]{fontenc}

% MAC users: first line, otherwise second line
%\usepackage[applemac]{inputenc}
\usepackage[utf8]{inputenc}
\usepackage{ucs}

\usepackage{a4}
\usepackage{epstopdf}
\usepackage{graphicx}
\usepackage{fancyvrb}
\usepackage{amsmath}
\usepackage{hyperref}
\usepackage{listings}
\usepackage{color}
%\renewcommand{\baselinestretch}{1.5}


\lstset{
  language=Haskell,
  basicstyle=\footnotesize,
  numbers=left,
  numberstyle=\tiny,
  numbersep=5pt,
  frame=single,
  rulecolor=\color{black},
  tabsize=4,
  captionpos=b,
  breaklines=true,
  breakatwhitespace=true,
  title=\lstname
}


\title{Generic Pandoc}
\titlerunning{Generic Pandoc}

\author{João Alpuim, Liewe van Binsbergen, João Paulo Pizani Flor}

\institute{
    Utrecht University \\
    e-mail: \{j.p.pizaniflor,l.t.vanbinsbergen,j.m.queirozataideagorretaalpuim\}@students.uu.nl
}

\date{\today}


\begin{document}
    \mainmatter

    %\bibliographystyle{splncs}

    \maketitle

    \section{Introduction}

        \subsection{Motivation}
            There is a big variety of markup languages available. All of them serve the same essential purpose,
            but still use different syntactic constructs. Often, different organizations and publishers require
            documents to be written in different markup languages, and this leads to a need for transformation
            between content in all of these languages.

            This task, of taking as input several structurally similar languages, and operating over them, seemed
            to us a perfect fit to apply generic programming techniques.


        \subsection{Choice of library}
            Our original goal was to work with several markup languages in a unified way, trying to apply generic
            programming to enhance parsing and processing for all of them. Therefore, we searched for a Haskell
            library which could handle as much markup languages as possible.

            This led us to choose the \href{http://hackage.haskell.org/package/pandoc}{Pandoc} library. Pandoc is
            able to convert (currently) from 7 input languages into 16 output languages (besides plain text),
            while also being reasonably recent and frequently updated.


    \section{Analysis}
        \label{sec:analysis}
        Pandoc interprets all of its supported input languages with only one parser (even though there are
        different modules for each language). It parses all languages to a common \texttt{Pandoc} datatype.
        This datatype has to be general enough to be able to represent features from all input languages.

        Due to this generality, we expected some valid constructs from one language to be allowed as part of
        the input in a language where these constructs are invalid. Pandoc would be therefore unable to detect
        these inconsistencies and provide sensible error messages.

        To confirm this expectations we ran some tests:
        \begin{description}
            \item[Incorrect nesting in HTML] The test HTML file (given as input to Pandoc) had a \emph{head}
            tag inside a numbered list environment, which is not allowed by the specification. Pandoc
            gave no error messages and in the resulting PDF, the text inside the \emph{head} tag was
            ignored.

            \item[Invalid tag names] We tried to give Pandoc an HTML test input file in which non-existent tag
            names were used (i.e, ''bbl'' and ''pandoc''). Again, no error messages were present during the
            processing, and the output PDF file contained the text between the invalid tags, as if the tags
            were not present in the input.

            \item[Embed Markdown in HTML] We embedded a little markdown-formatted text at the beginning of an
            HTML file. The goal of this test was to determine whether Pandoc tried to ''guess'' in any way the
            format of the file by looking at its contents. In the resulting output, the whole
            Markdown-formatted preamble (before the opening \textless html\textgreater) was ignored, which
            led us to conclude that Pandoc uses \emph{only the file extension} in an \emph{rough attempt} at
            guessing the input format.

            \item[Wrong extension] We fed Pandoc some TeX input, but gave the file a \emph{.html} extension.
            Pandoc then consumed the whole input and produced \emph{no error messages whatsoever}, even though
            no HTML tags were present in the input. The resulting PDF file just contained the whole TeX code,
            as if it was plain text.
        \end{description}

        Summarizing the problems faced during the tests:  Pandoc has to parse features of all input languages
        into a single intermediate representation (modeled by the \emph{Pandoc} datatype). This need for a
        general representation of all possible inputs leads to ambiguity in the parsing, and - consequently -
        to incorrect behaviour and lack of error messages when parsing some kinds of invalid inputs.


    \section{Proposed solution}
        \subsubsection{Specific datatypes}
            As the problems mentioned in section \ref{sec:analysis} are caused by a too general target
            datatype for the parser, a big part of the solution is to introduce specific datatypes modeling
            the structure of each of the input languages. We did not introduce an specific datatype for each
            input language. However the goal of this project is to make the necessary functionalities
            available in order to create a library that can be extended with any user-specific input
            language.

        \subsubsection{Generic solution}
            By looking at the \emph{Pandoc} input languages we clearly see that all of them provide constructs
            modeling a certain set of \emph{markup concepts}. In fact, these concepts are precisely
            represented in the \texttt{Pandoc} datatype, that captures the markup concepts common to all of
            the input languages. These include document meta-information, namely the title, authors and date; 
            and the content itself such as paragraphs, lists, etc.

            Therefore we thought of using generic programming to define generic functions that traverse the
            datatype and apply a specific function (defined by the user) that converts a specific node of the
            AST from the user's datatype into a node of the \texttt{Pandoc} datatype.

            We opted to use Haskell's type-classes to make these functions for each specific datatype available, 
            since one can always declare a new instance for a new datatype. 
            This would provide the end-user an API where he may only declare these instances, explaining how the 
            program can extract the information from the specific datatype.

            We chose to use \texttt{Scrap Your Boilerplate} mainly due its extensibility but also because of its
            easiness-of-use and the built-in functionalities to query and transform data.

        \subsubsection{Pandoc Datatype}
            Before going any further, we should introduce a brief overview of the \emph{Pandoc} datatype, that
            will be useful throughout the report

            \begin{lstlisting}
data Pandoc = Pandoc Meta [Block] 

-- Bibliographic information for the document.
data Meta = Meta { docTitle   :: [Inline]
                 , docAuthors :: [[Inline]]
                 , docDate    :: [Inline] }

data Block = Plain [Inline]
           | Para [Inline]
           | BulletList [[Block]]
           | DefinitionList [([Inline],[[Block]])]
           | Header Int [Inline]
           (...)

data Inline = Str String
            | Emph [Inline]
            | Strong [Inline]
            (...)
            \end{lstlisting}

            There are several other contructors and datatypes which are not relevant for the purpose of this
            project. It is important to note that this datatype is not mutually recursive between
            \texttt{Block} and \texttt{Inline}, which is not the case in some target languages, as we will
            see for HTML. This leaves some freedom of choice to the user when defining his own transformation
            to this \texttt{Pandoc} datatype.

        \subsubsection{Example source language: HTML}
            Since we need specific datatypes for each of the input languages, we opted for writting our own
            \emph{HTML} datatype and parser. We could then mirror \emph{in the datatype itself} restrictions
            such as element names (tag names in HTML, command names in \LaTeX) and the possible sub-elements
            of a given element. For example, an excerpt of a datatype definition modeling an HTML document
            could look like:

            \begin{lstlisting}
data HTMLDoc = HTMLDoc HTMLOTag HTMLHead HTMLBody HTMLCTag
data HTMLOTag  = HTMLOTag
data HTMLCTag = HTMLCTag

data HTMLHead = HTMLHead HTMLHeadOTag HTMLHeadContents HTMLHeadCTag

data HTMLHeadContents = HTMLHeadContents [HTMLHeadContents_] HTMLTitle [HTMLHeadContents_]

data HTMLHeadContents_ = Meta ... | Style ... | HTMLTitle ... | Link ... | ...

data HTMLTitle = HTMLTitle ...
            \end{lstlisting}

            Looking at the definition of \emph{HTMLHeadContents}, for example, it's immediately obvious that
            the \emph{head} section of an HTML file \emph{must} contain at least one \emph{title} element.
            Also, the HTMLHeadContents\_ type gives an extensive listing of all the allowed children of
            HTMLHead.

            It is important to note that \emph{Meta} refers to information such as document enconding; and 
            consequently it is not the same Meta information required by the \texttt{Pandoc} datatype. 

            By mirroring the grammar of the input language in a set of mutually-recursive datatype
            definitions in this way, we can be sure that \emph{any} value with type HTMLDoc is the result of
            parsing a valid document, according to the standard.

\clearpage
\section{Approaches to the Generic Transformation}
    \subsection{Introduction}
        By creating specific datatypes for every input language we are able to enforce the well-formedness of
        the input documents. For obtaining actual values of these AST's separate parsers have to be created.
        These parsers can provide us with error messages about the structure of the input document, which
        solves one of the observed problems with the current version of Pandoc.

        However, we would also be required to define specific writers for \emph{each transformation}. When we
        have $n$ input languages and $m$ output languages we would require $(m-1) \times n$ writers, assuming
        every input language is also an output language and that we will not transform from any language to
        itself (hence the $-1$). This is obviously a lot of work and therefore not desired.

        Pandoc already provides us with writers for all the possible output languages and all these writers
        work on the general Pandoc representation of a document. If we are able to transform our specific
        AST's to this general representation we can reuse the writers. This is where generic programming
        might come in handy. 

        Our goal for the rest of the project will be to provide an `interface' of functions that help the
        users in defining a transformation from his specific AST to the general representation.

        \subsection{Characteristics of the Approaches}
        The `quality' of transformation interface can be measured by the following characteristics:
        \begin{enumerate}
            \item \emph{The genericity of the transformation interface}. Ideally the interface should be as generic as possible, so it can work for any language and their corresponding ASTs.\\
            \item \emph{The level of overhead}. The transformation interface should be designed in such a way that it allows the user to write his transformation with minimum boilerplate code.
        \end{enumerate}

        \paragraph{\textbf{Approaches}}
            We have explored two approaches:
        \begin{enumerate}
            \item Type Class instances, using a a class for obtaining `Blocks' and a a class for obtaining inline elements called `Inlines'.
            \item Node transformation %TODO
        \end{enumerate}
        Before we will examine these approaches we will first look at a test case.

    \subsection{Test Case: Obtaining Meta Information from HTML}
        \label{testcasemeta}
            We started off by defining the following class and generic function:

            \begin{lstlisting}
type Title = [Inline]

class (Data a, Typeable a) => GTitle a where
    gtitle :: a -> Title

gTitle :: GenericQ Title
    gTitle = everything (++) (mkQ [] gtitle)

-- Below is what the user could define
instance GTitle Head where
    gtitle (Head ...) = ...            

htmlTitle :: HTML -> Title
htmlTitle = gTitle (title :: Head -> Title)
            \end{lstlisting}

            Where \texttt{[Inline]} is the type of the title in the \texttt{Pandoc} datatype.

            The idea behind this code was to query the datatype with the function defined by the user, in the
            GTitle class. This would allow one to define the function \texttt{gtitle} on a subtree of the AST
            for the datatype. However, GHC cannot verify the constraints imposed by \texttt{gtitle} (when used
            inside gTitle) at compile time, which leads to the following error:
            \begin{verbatim}
Ambiguous type variable `b0' in the constraints:
  (Typeable b0)
arising from a use of `mkQ' at (...)
  (GTitle b0)
arising from a use of `gtitle' at (...)
            \end{verbatim}

            We therefore slightly changed the implementation:
            \begin{lstlisting}
gTitle :: (GTitle a) => (a -> Title) -> GenericQ Title 
gTitle g = everything (++) (mkQ [] g)
            \end{lstlisting}
 
            By moving the restriction to the function itself, we lost expressiveness.
            Now it can only be called if \texttt{g} is an instance of \texttt{GTitle} and we can just extend
            it with one function. 
            Despite this disadvantages this approach still suits our needs since it still imposes the constraint
            and we can apply \texttt{gTitle} to any function that satisfies it.

            Given this implementation we moved on to define two other classes, namely \texttt{GPandoc} and
            \texttt{GMeta}.
           
            The former class is for declaring instances for datatypes that can be converted to the 
            \texttt{Pandoc} datatype, by declaring the \texttt{gpandoc} function.
            Ideally it should use the \texttt{gmeta} function defined in the \texttt{Meta} class, which in its
            turn should use the \texttt{gtitle} function.
            
            A possible partial implementation of the conversion between \emph{HTML} and \emph{Pandoc} would
            be the following:

            \begin{lstlisting}
class (Data a, Typeable a) => GMeta a where
    gmeta :: a -> Meta

class (Data a, Typeable a) => GPandoc a where
    gpandoc :: a -> Pandoc

-- An HTML has no authors and no date, therefore empty lists are used.
instance GMeta HTML where
    gmeta h = Meta (gTitle (gtitle :: Head -> Title) h) [] []

instance GPandoc HTML where
    gpandoc h = Pandoc (gmeta h) undefined 
            \end{lstlisting}

            Note that in the \texttt{gpandoc} function the second field is still \texttt{undefined} because
            it's related to the document structure and content and not to meta-information.

\clearpage 
    \section{Approach \#1: Type Class Instances}
        \subsection{Examining Queries}
        We have seen an approach of obtaining information from our datatype in 
        section \ref{testcasemeta} by using SYB queries. Could we then use a similar approach to obtain 
        information about blocks and inlines and construct the whole Pandoc type?

        In order to answer this question we first need a way to obtain pandoc blocks from 
        our AST. Assuming that all the input languages to be used in the future
        will be some kind of markup language, they will all contain some form 
        of block elements. Note that the approach proposed in this section should work 
        for any input language, any datatype even, but assuming that the input language is
        some form of markup language facilitates the discussion.

        It should be the case that any specific datatype of such a input language will contain
        a type with corresponding constructors for such a block element. For example, looking
        again at HTML we could have a type BlockTag with constructors Div, Paragraph, etc.
        We can query our AST for any such constructor and return a value with the corresponding
        constructor from Pandoc. So for the query approach to work, we require at least some
        knowledge of the Pandoc type from the side of the user.
        This leads to another characteristic for our transformation interface.
        \paragraph{\textbf{Characteristic}}
        \begin{enumerate}
            \item[3] \emph{The required level of understanding of Pandoc and/or its datatype}. 
        The more a user has to dive into the code of the target Pandoc datatype, the less appealing
        it is to add a new input language or datatype.
        \end{enumerate}
        A query to dive into our AST to find all values of a type that matches our ASTs
        block elements can be easily defined when we disregard the contents of such a
        block element. At the highest level, the Pandoc datatype consists of Meta information 
        and a list of blocks. When we want to transform our AST into the Pandoc type, all we
        have to do is obtain all the block elements that our part of it by querying for them!

        The problems begin to show when we do take the contents of such a block element
        into account. In the Pandoc datatype there is no mutual recursion. A block either 
        contains inline elements or other blocks. An inline element however only contains 
        other inlines. The Note constructor is an exception, however it is only used for
        end notes of a document, not for the contents itself.

        \subsection{Mutually Recursive Inputs}

        A constraint on our input language is introduced: in order to be able to transform
        into Pandoc directly, our input language  \emph{cannot} be \emph{Mutually Recursive}.

        This does not mean that we can not use mutually recursive languages as our input 
        language, e.g. HTML is mutually recursive and already an input language of Pandoc.

        Instead of introducing impossibilities for our user, anxious to introduce a new language
        with pandoc, the current construction of the Pandoc type introduces a 
        \emph{degree of freedom} for the user. As is, Pandoc might not deal with the mutual
        recursive structure of an input language as the user expects it. The way Pandoc
        currently deals with it is just one of the many alternatives.

        To show an example of the choices a user can make, consider the following case. The user
        has an XHTML document with at the top level a block element. This block element contains
        an inline element which, in its turn, contains a second block element and also a 
        piece of emphasized text (which is an inline element). To transform
        this document into the Pandoc type there are multiple options available. The resulting
        Pandoc type could, for example, contain just one top-level block element and since 
        there are no child-level block elements in the Pandoc type, completely ignoring
        the second block element. A second result could be a Pandoc type where the second
        child-level block element is moved to the top-level, thereby ignoring the recursive
        structure of the input. A third option would be to interpret the child-level 
        block element as an inline element, for example by retrieving all children 
        inline elements.

        Hopefully it is clear that there are many other interpretations possible, which ever
        is used can be made available as a choice to the user. This is what forms the cornerstone
        of the approach explained in this chapter. It has obvious downsides, as we will see
        shortly. First a fourth characteristic for qualifying our approaches is introduced.

        \paragraph{\textbf{Characteristic}}
        \begin{enumerate}
            \item[4] \emph{The level of freedom the user has in defining the transformation}. 
            More freedom for the user means a greater chance of the user to reach his expected
            result.
        \end{enumerate}

        \subsection{The Instances}   
            The first approach for transforming any AST to the Pandoc type that we worked out 
            uses an approach similar to the querying methods we have seen in section
            \ref{testcasemeta} except that it doesn't use `Scrap Your Boilerplate'.

            The core question is defining a function of type $\alpha \rightarrow [P.Block]$
            where $P.Block$ refers to the type Block from Pandoc and $\alpha$ is the users type
            or any child element of it.
            We call this function 
            $gblocks$. Because gblocks will have to operate on more then one type we define
            it as a method within a type class called $GBlocks$. We do the same for the 
            function $ginlines$ within type class $GInlines$. To summarize: the function 
            $gblocks$($ginlines$) obtains from any relevant type within our AST a list of 
            Pandoc blocks(inlines). The $ginlines$ function, and also $gblocks$ function itself,
            will be used within the definitions of $gblocks$ to obtain the contents of block elements.

        \subsection{Test Case: HTML Instances}
            A lot of instances are required, to see why see Appendix \ref{htmltype}, but most 
            of these instances are trivial and only are only required to transfer the function
            call onwards to children. The interesting definitions we worked out are as follows: 
            \begin{lstlisting}
instance GBlocks BlockTags where
gblocks (Paragraph ts) = P.Para (ginlines ts) : (gblocks ts)
gblocks (Div ts) = P.Plain (ginlines ts) : (gblocks ts)
gblocks (Header (H1 blas)) = P.Header 1 (ginlines blas) : (gblocks blas)
gblocks (Header (H2 blas)) = P.Header 2 (ginlines blas) : (gblocks blas)
...
gblocks (Header (H6 blas)) = P.Header 6 (ginlines blas) : (gblocks blas)
gblocks (BlockText raw) = [P.Plain [P.Str raw]]

instance GInlines InlineTags where
ginlines (Span ias) = ginlines ias
ginlines (Em str) = [(P.Emph [P.Str str])]
ginlines (InlineText str) = [P.Str str]
            \end{lstlisting}
            Notice that the instance for BlockTags recurses over child elements and therefore
            the result is not only the block itself, but also all the blocks that could be 
            found from its children. 

            The instance for InlineTags does not behave like this, 
            so when looking for inlines only the top-level is taken into account. 

            This is just \emph{one of the many ways} we could have chosen to implement these
            functions. Another choice available to the user when looking at HTML
            is the choice of what to do for tags that do not correspond to any part of the Pandoc
            type such as form elements and buttons. The current implementation of Pandoc just
            ignores these tags, while we grant the user a choice what to do with these tags.

        \subsection{Conclusions}
            \subsubsection{Looking back at the characteristics} how does this approach `score'?
            \begin{enumerate}
                \item The approach is completely general, it can not only be used for any AST but 
                for any datatype, the user is free to give instances for GBlocks and GInlines 
                for any type.

                \item In the example of HTML there is a lot of boilerplate code required to give
                all the instances since the BlockainerTags, InlainerTags and AllTags types need to be
                traversed. This is caused by the fact that HTML is a mutually recursive
                type while Pandoc is not. For other languages, e.g. Markdown the overhead will be
                a lot less because its structure corresponds more directly with the Pandoc type.

                \item It is required for the user to know what constructors create values of types 
                Block and Inline. The choice a user makes on how to implement his own type influences
                the required knowledge of Pandoc required. 
                The user can go in as deep as he likes, but also
                decide keep the transformation really simple.

                \item As mentioned above, there is complete freedom for the user to implement the
                interface however he pleases. This is the prime advantage of the proposed
                approach.
            \end{enumerate}

            We \textbf{conclude} that some degree of knowledge of the Pandoc type is required and that, 
            depending on the complexity of the users AST, this approach potentially leads to a lot of 
            boilerplate. What the approach lacks in this respects, it makes up in the level of freedom
            that is available to the user. If the user is not prepared to look into the Pandoc datatype
            this level of freedom might be unwanted. Whether we can prevent any requirements on the
            knowledge of Pandoc for the user, while maintaining levels of freedom, is something that is
            explored in the next chapter.


    \clearpage

    \section{Approach \#2: A Parser for Generic ASTs}
        The second approach we explored for implementing a generic transformation into the Pandoc type is by using
        a hierarchy of generic functions organized in a recursive descent fashion. In fact, this set of functions
        form a \emph{generic parser}. This is a peculiar parser, however, as it does \emph{not} parse Strings or
        other sequential data, but it parses an AST of a given document, represented as a Haskell datatype.

        A representative subset of the functions in this recursive descent parser appears below:
        \begin{lstlisting}
gPandoc <-- gMeta, gBlocks
gMeta <-- gTitle, gAuthors, gDate
gBlocks <-- gBlock
gBlock <-- gInline
        \end{lstlisting}

        In this schema, the left-pointing arrow denotes a depency, i.e, the function to the left of the arrow
        has a call to the functions on the right. For example: to construct a value of type Pandoc, we need two
        fields (meta-information and the list of blocks); thus the gPandoc function needs to call gMeta and
        gBlocks.

        The implementation of all these functions is \textbf{very} similar, as they implement basically a
        guided depth-first search. However, the really interesting point in this approach is that, \emph{in any
        level in this hierarchy}, the user can override the generic behaviour and use a type-specific function,
        that works with his document AST datatype.

        There is no better way to understand the behaviour of this ``generic parser'' other than by looking at an
        example. Below is the implementation of the ``gPandoc'' function, the root in the hierarchy of generic
        parser functions. For a more detailed version of the code, see appendix.\ref{approachtwo}  
        \begin{lstlisting}
gPandoc :: (Data a, Typeable a)
    => (a -> Maybe P.Pandoc) -- extension function
    -> (forall b. (Data b, Typeable b) => b -> Maybe P.Meta) -- meta subterm function
    -> (forall c. (Data c, Typeable c) => c -> Maybe [P.Block]) -- blocks subterm function
    -> a
    -> Maybe P.Pandoc

gPandoc e m b = (combine . flattenCollectResults2 . gmapQ collect) `extQ` e
    where
        collect c = (m c, b c)
        combine (mm, mb) = if isJust mm && isJust mb
                               then Just $ P.Pandoc (fromJust mm) (fromJust mb)
                               else Nothing
        \end{lstlisting}

        The type signature of this function (and of all others in the hierarchy) might indeed seem frightening,
        but it has some logic behind it, explained further ahead. Most of this complexity is not conceptual
        anyway, and is imposed by implementation restrictions.

        On the other hand, the behavior of gPandoc is quite easy to understand: the first thing to notice is that
        - even though gPandoc is a generic function - it can be extended with a type-specific case (a function
        which we pass as the ``e'' argument). If the type-specific case is not used, then the generic behaviuor
        comes into action. The \emph{collect} function is applied to all the immediate children of the AST subtree
        being analyzed, and produces a tuple for each of these children.

        The tuple corresponding to each child contains some \emph{attempts} at obtaining information from that
        child. Each attempt may succeed or fail (that is why they reside in the Maybe monad). In the gPandoc case,
        we try to obtain meta-information \textbf{and} blocks for each child (by calling gMeta and gBlocks,
        respectively). This behavior (of trying all possibilities for each child) is necessary because \textbf{we
        do not know in advance} what kind of information a child has (as this is a generic function).

        At last, this list of tuples is flattened and the successes of all searches in all children is combined to
        (possibly) produce the intended result (of type Pandoc). Notice that - because we might not obtain all the
        necessary fields for the Pandoc constructor - the result value also resides in the Maybe monad.

        The user of the ``Generic Pandoc'' library, wanting to add a new input language by making use of the
        approach being described here needs to define a \emph{mapping between AST subtrees in his specific markup
        datatype and subtrees in the Pandoc datatype}. This is done by \emph{partially applying} the generic
        functions from the generic parser hierarchy to his specific functions. Again, nothing better than an
        example to clarify this technique:

        \begin{lstlisting}
hPandoc = gPandoc dummy hMeta hBlocks

hBlocks = ...

hMeta = gMeta dummy hTitle hAuthors hDate

hTitle = gTitle eHTMLTitle
hAuthors = gAuthors eHTMLAuthors
hDate = gDate eHTMLDate
        \end{lstlisting}

        In this example, the hTitle, hAuthors and hDate functions convert HTML AST subtrees into \emph{leaves} of
        the Pandoc AST. Because of this, it is clear that they \emph{need} to use specialized behavior, which they
        do by passing the arguments eHTMLTitle, eHTMLAuthors and eHTMLDate.

        The non-leaf functions hMeta and hPandoc use no specific cases, so their definiton just applies
        respectively gPandoc to hMeta and hBlocks and gMeta to hTitle, hAuthors and hDate, which has the effect of
        ``continuing the generic depth-first search''.

        As a last remark, the ``dummy'' argument passed to gPandoc and gMeta is a very interesting implementation
        issues which - until now - we could not avoid: we want to grant the possiblity of type-specific extension
        on \emph{every} level of the generic parser function hierarchy. Therefore, there \emph{must always be} an
        argument in that position when these functions are (partially) applied. When we want to use just the
        generic behavior, with no specialization at all, we resort to passing the dummy function, which is defined
        as follows:

        \begin{lstlisting}
dummy :: () -> Maybe a
dummy () = Nothing
        \end{lstlisting}

        The dummy function has a value of type Unit as its input, therefore it will never be used when passed as
        type-specific case (as we hope that values of type Unit will never be present in the input markup AST).

        The following analysis can be made of this approach to generic transformation into the Pandoc type,
        according to the criteria defined earlier:

        \begin{enumerate}
            \item This approach is highly generic, as generic as approach \#1 or even more. It can be used for any
            input markup datatype, and the user does not need to redefine all Pandoc ``concepts'' (Meta, Block,
            etc.), but only the minimal subtrees of his input type which match a certain Pandoc subtree.
            \newline \newline

            \item There is a substantial amount of overhead needed to define the mapping between the user type and
            the Pandoc subtrees. We are not yet happy with the amount of boilerplate of the user side, specially
            in declarations such as:
            \begin{verbatim}
hPandoc = gPandoc dummy hMeta hBlocks
            \end{verbatim}
            which we think should be somehow encapsulated - in a newtype declaration perhaps.
            \newline \newline

            \item The user still needs to know the Pandoc types when implementing his specialized conversion
            functions. For example, when getting the title from an HTML head block, the user needs to make his
            conversion function return a list of Inline, which is a Pandoc type. We do not believe, however, that
            this requirement can be lifted somehow. The only step we could take in the direction of separating the
            user from Pandoc internals is to provide a set of type synonyms modeling the ``concepts'' used by
            Pandoc. In this way, if Pandoc decides to rename its types in the future, user code will not break.
        \end{enumerate}

    \clearpage


    \section{Appendix}
        \appendix
        \section{The HTML datatype}
        \label{htmltype}

        \begin{lstlisting}
data HTMLTag    = HTMLTag
data HTMLEndTag = HTMLEndTag
data HeadTag    = HeadTag
data BodyTag    = BodyTag
  deriving (Show, Typeable, Data)
data HeadEndTag = HeadEndTag
data BodyEndTag = BodyEndTag

data HTML = HTML Head Body
  deriving (Show,Typeable,Data)
data Head = Head HeadContents 
  deriving (Show,Typeable,Data)
data Body = Body [BlockTags]
  deriving (Show,Typeable,Data)

data HeadTags     = Title
                  | Base 
                  | Style 
  deriving (Eq,Show,Typeable,Data)
type HeadContents = [(HeadTags,Contents)]
type Contents     = String

data BlockTags = Div [AllTags] 
               | Paragraph [AllTags] 
               | Header Header
               | BlockText String
  deriving (Show, Typeable, Data)
data InlineTags = Span [InlainerTags] 
                | Em String 
                | InlineText String
  deriving (Show, Typeable, Data)
data ContainerTags = Object [BlockainerTags]
                   | Button [BlockainerTags]
  deriving (Show, Typeable, Data)

type AllTags        = Either BlockainerTags InlainerTags
type BlockainerTags = Either BlockTags ContainerTags
type InlainerTags   = Either InlineTags ContainerTags

data Header = H1 [BlockainerTags] 
            | H2 [BlockainerTags]  
            | H3 [BlockainerTags] 
            | H4 [BlockainerTags] 
            | H5 [BlockainerTags] 
            | H6 [BlockainerTags]
  deriving (Show, Typeable, Data)
        \end{lstlisting}

    \section{Generic recursive descent parser to the Pandoc type}
    \label{approachtwo}
        \begin{lstlisting}
-- | A different approach to transforming specific markup datatypes into Pandoc. Using
-- | a form of "generic recursive descent parser"

-- | Performs a fold over a list of Maybes producing a singleton list, with either a Nothing
-- | (if the list had only Nothings), or the first Just in the list
orM :: [Maybe a] -> [Maybe a]
orM xs = [foldr orM2 Nothing xs]
    where
        orM2 (Just x1) _         = Just x1
        orM2 Nothing   (Just x2) = Just x2
        orM2 Nothing   Nothing   = Nothing

uncurriedZip2 :: ([a], [b]) -> [(a, b)]
uncurriedZip2 (l1, l2) = zip l1 l2

uncurriedZip3 :: ([a], [b], [c]) -> [(a, b, c)]
uncurriedZip3 (l1, l2, l3) = zip3 l1 l2 l3

uncurriedZip4 :: ([a], [b], [c], [d]) -> [(a, b, c, d)]
uncurriedZip4 (l1, l2, l3, l4)  = zip4 l1 l2 l3 l4

mapTuple2 :: (a -> c) -> (b -> d) -> (a, b) -> (c, d)
mapTuple2 f1 f2 (x, y) = (f1 x, f2 y)

mapTuple3 :: (a -> d) -> (b -> e) -> (c -> f) -> (a, b, c) -> (d, e, f)
mapTuple3 f1 f2 f3 (x, y, z) = (f1 x, f2 y, f3 z)

mapTuple4 :: (a -> e) -> (b -> f) -> (c -> g) -> (d -> h) -> (a, b, c, d) -> (e, f, g, h)
mapTuple4 f1 f2 f3 f4 (x, y, z, w) = (f1 x, f2 y, f3 z, f4 w)

flattenCollectResults2 :: [(Maybe a, Maybe b)] -> (Maybe a, Maybe b)
flattenCollectResults2 = head . uncurriedZip2 . (mapTuple2 orM orM) . unzip

flattenCollectResults3 :: [(Maybe a, Maybe b, Maybe c)] -> (Maybe a, Maybe b, Maybe c)
flattenCollectResults3 = head . uncurriedZip3 . (mapTuple3 orM orM orM) . unzip3

flattenCollectResults4 :: [(Maybe a, Maybe b, Maybe c, Maybe d)] -> (Maybe a, Maybe b, Maybe c, Maybe d)
flattenCollectResults4 = head . uncurriedZip4 . (mapTuple4 orM orM orM orM) . unzip4


gPandoc :: (Data a, Typeable a)
    => (a -> Maybe P.Pandoc) -- extension function
    -> (forall b. (Data b, Typeable b) => b -> Maybe P.Meta) -- meta subterm function
    -> (forall c. (Data c, Typeable c) => c -> Maybe [P.Block]) -- blocks subterm function
    -> a
    -> Maybe P.Pandoc

gPandoc e m b = (combine . flattenCollectResults2 . gmapQ collect) `extQ` e
    where
        collect c = (m c, b c)
        combine (mm, mb) = if isJust mm && isJust mb
                               then Just $ P.Pandoc (fromJust mm) (fromJust mb)
                               else Nothing


gMeta :: (Data a, Typeable a)
    => (a -> Maybe P.Meta) -- extension function
    -> (forall b. (Data b, Typeable b) => b -> Maybe [P.Inline]) -- title subterm function
    -> (forall c. (Data c, Typeable c) => c -> Maybe [[P.Inline]]) -- authors subterm function
    -> (forall d. (Data d, Typeable d) => d -> Maybe [P.Inline]) -- date subterm function
    -> a
    -> Maybe P.Meta

gMeta e t a d = (combine . flattenCollectResults3 . gmapQ collect) `extQ` e
    where
        collect c = (t c, a c, d c)
        combine (mt, ma, md) = if isJust mt && isJust ma && isJust md
                                   then Just $ P.Meta (fromJust mt) (fromJust ma) (fromJust md)
                                   else Nothing


gTitle :: (Data a, Typeable a)
    => (a -> Maybe [P.Inline]) -- extension function
    -> a
    -> Maybe [P.Inline]

gTitle s = mkQ Nothing s


gAuthors :: (Data a, Typeable a)
    => (a -> Maybe [[P.Inline]]) -- extension function
    -> a
    -> Maybe [[P.Inline]]

gAuthors s = const undefined


gDate :: (Data a, Typeable a)
    => (a -> Maybe [P.Inline]) -- extension function
    -> a
    -> Maybe [P.Inline]

gDate s = const undefined


gBlocks :: (Data a, Typeable a)
    => (a -> Maybe [P.Block]) -- extension function
    -> a
    -> Maybe [P.Block]

gBlocks s = const undefined


gBlock :: (Data a, Typeable a)
    => (a -> Maybe P.Block) -- extension function
    -> a
    -> Maybe P.Block

gBlock s = const undefined


dummy :: () -> Maybe a
dummy = const Nothing


-- | HTML functions
hPandoc = gPandoc dummy hMeta gBlocks

hMeta = gMeta dummy hTitle hAuthors hDate
hTitle = gTitle eHTMLTitle
hAuthors = gAuthors eHTMLAuthors
hDate = gDate eHTMLDate


eHTMLTitle :: Head -> Maybe [P.Inline]
eHTMLTitle (Head c) = lookup Title c >>= return . P.Str

eHTMLAuthors :: Head -> Maybe [[P.Inline]]
eHTMLAuthors x = Just []

eHTMLDate :: Head -> Maybe [P.Inline]
eHTMLDate x = Just []
        \end{lstlisting}

\end{document}
