[This local archive copy is from the official and canonical URL, http://www.cs.york.ac.uk/fp/HaXml/paper.html; please refer to the canonical source document if possible.]

Haskell and XML: Generic Document Processing Combinators vs. Type-Based Translation

Malcolm Wallace Colin Runciman
University of York

10 March 1999

Abstract: We present two complementary approaches to writing XML document-processing applications in a functional language.

In the first approach, the generic tree structure of XML documents is used as the basis for the design of a library of combinators for generic processing: selection, generation, and transformation of XML trees. Careful design of the combinators leads to a set of algebraic laws, which in turn suggests the possibility of a more sophisticated implementation capable of optimised traversals of the data.

The second approach is to use a type-translation framework for treating XML document type definitions (DTDs) as declarations of algebraic data types, and a derivation of the corresponding functions for reading and writing documents as typed values in Haskell.

1  Introduction

1.1  Document markup languages

XML (Extensible Markup Language) [1] is a recent simplification of the older SGML (Standardised Generalised Markup Language) standard that is widely used in the publishing industry. It is a markup language, meaning that it adds structural information around the text of a document. It is extensible, meaning that the vocabulary of the markup is not fixed -- each document can contain a meta-document, called a DTD (Document Type Definition), which describes the particular markup capabilities used.

The use of XML is not however restricted to the traditional idea of a document. Many companies are proposing to use XML as an interchange format for pure data produced by applications like graph-plotters, spreadsheets, and relational databases.

HTML (Hyper-Text Markup Language) is one well-known example of an instance of SGML -- every HTML document is an SGML document conforming to a particular DTD. Where XML improves over SGML is in removing shorthand forms that require an application to have knowledge of a document's DTD. XML has strict well-formedness constraints which allow the possibility of generic applications -- applications which can process a document without knowing the DTD.

For instance, in HTML some markup (such as a numbered list) requires an end marker; other forms (such as paragraphs) have implicit end markers understood when the next similar form starts; and yet other markup (such as in-line images) is self-contained and needs no end marker. An HTML application needs to be aware of the specific kind of markup in order to do the right thing. By contrast, XML requires that all markup has an explicit end marker without exception: every document is well-formed; its nesting structure is syntactically clear. In this way, an XML application needs no knowledge of the meaning of any particular markup expression -- parts of the document can be selected, re-arranged, transformed, by structure alone rather than by meaning.

On the other hand, when the DTD is in fact available for a document, the meaning it defines can be used to ensure that a document is valid, that is, it conforms to the markup rules given in the DTD. The notion of validity can be extended to applications which process documents, as well.

In this paper we present two complementary approaches to using a lazy functional language (Haskell) in the style of a ``domain-specific language'' for XML processing.

First, combinator style programming, already commonly used for writing parsers and pretty-printers, is applied to XML-document processing. Secondly, the natural correspondence between DTDs and statically-checked algebraic types is explored, allowing documents to be manipulated as fully type-secure Haskell values. The former approach lends itself to generic processing tasks; the latter to specialised tasks where document validity is important.

Both approaches rely on a toolkit of more basic components for processing XML documents in Haskell: for instance, a parser and pretty-printer, both themselves implemented using standard combinator libraries.1

1.2  XML document structure

An XML document is essentially a tree structure. To simplify somewhat, there are two basic `types' of content in a document: tagged elements, and plain text. A tagged element consists of a start tag and an end tag, which may enclose any sequence of other content (elements or text fragments). Tagged elements can be nested to any depth, and the document is well-formed if it consists of a single top-level element containing other properly nested elements.

Start tags have the syntax <tag>, and end tags </tag>, where tag is an arbitrary name. There is special syntax for an empty element: <tag/> is exactly equivalent to <tag></tag>.

The start and end tags for each element contain a tag name, which identifies semantic information about the structure, indicating how the enclosed content should be interpreted. The start tag may also contain attributes, which are simple name/value bindings, providing further information about the element.

Figure 1 shows an example XML document, illustrating all these components.

1.3  The combinator approach

Combinators have been an important part of functional programming since the beginning (Church?, Landin?, Schonfinkel?, Curry?). A combinator-style program is written entirely in terms of a small, perhaps even minimal, set of higher order functions; each function does a small amount of work that does not overlap with other functions; their types are very uniform, allowing any function to compose with any other. The combinators are the glue; they provide a variety of ways of composing functions together into more powerful functions.

Defining a set of combinators is rather like defining some new syntax for the language, specially tailored to your problem domain [3]. For instance, in Haskell we can define new infix operators like ! or ?> to mean whatever we want. In this sense, functional languages are extensible, just as XML itself is extensible.

Examples of successful combinator libraries abound: parsing and pretty-printing are two very common application areas. The first part of this paper sets out the design of a new set of combinators for document transformation, specifically in the setting of XML. This design attempts to be principled and uniform, in order to maximise the applicability of algebraic manipulation, and hence to maximise opportunities for an implementation which uses these properties to optimise data traversals.

In contrast to the ``mainstream'' solution for document processing, namely new domain-specific languages for expressing and scripting transformations, the combinator approach has several advantages:

Of course, there are disadvantages too.

2  Combinators for generic document transformation

In this section, we describe the document and transformation models, introduce some combinators for transformation, and illustrate some algebraic laws about these combinators. A complete table of filters and combinators is given in Figure 2. An example program is shown in Figure 3. A table of algebraic laws is given in Figure 4.

2.1  Documents and transformations

Data modelling.
    data Element = Elem Name [Attribute] [Content]
    data Content = CElem Element
                 | CText String
Because functional languages are good at processing tree-structured data, there is a natural fit between the XML document domain and Haskell tree datatypes. In simplified form, the main datatypes which model an XML document are Element and Content, whose definitions are mutually recursive, together forming a multi-branch tree structure.

The filter type.
    type CFilter = Content -> [Content]
The basic type of all document processing functions is the content filter, which takes a fragment of the content of an XML document (whether that be some text, or a complete tagged element), and returns some sequence of content. The result list might be empty, it might contain a single item, or it could contain a large collection of items.

Some filters are used to select parts of the input document, and others are used to construct parts of the output document. They all share the same basic type, because when building a new document, the intention is to re-use or extract information from parts of the old document. Where the result of a filter is either empty or a singleton, the filter can sometimes be thought of as a predicate, deciding whether or not to keep its input.

Program wrapper.
    processXMLwith :: CFilter -> IO ()
We assume a top-level wrapper function, which gets command-line arguments, parses an XML file into the Content type, applies a filter, and pretty-prints the output document. The given filter is applied to the top-level enclosing element of the document.

Basic filters.
The simplest possible filters are predefined: none takes any content and returns nothing; keep takes any content and returns just that item. These are zero and identity in the underlying algebra.

A useful filter which involves both selection and construction is showAttr a, which extracts the value of the attribute a from the current element and returns just that string as a piece of content.

When constructing a new document (e.g. the script in Figure 3 which generates HTML), the mkElem function occurs repeatedly. We define and use a small library of functions such as htable, hrow, and hcol which are just synonyms for particular applications of mkElem and mkElemAttrs to different tagnames, reducing verbosity and making the syntax rather more readable.

Also for convenience, we define the new operators ? and ! as synonyms for showAttr and literal respectively: they are used in a bracketed postfix notation,4 which some people may find stylistically attractive.

2.2  Combinators

In what ways can these very basic filters be combined into more interesting and complex filters?

The most important and useful filter combinator is `o`. We call this operator ``Irish composition'', for reasons which should be obvious. It plugs two filters together: the left filter is applied to the results of the right filter. So, for instance, the expression
    text `o` children `o` tag "player"
means ``only the plain-text children of the current element, provided the current element has the player tag name''.

Some other combinators are as follows. cat fs concatenates the results of each of the filters from the fs list. f `with` g acts as a guard on the results of f, pruning to include only those which are productive under g. The dual, f `without` g, excludes those results of f which are productive under g. The expression p ?> f :> g is a functional choice operator; if the (predicate) filter p is productive, then the filter f is applied, otherwise g is applied. From this is derived an ``exclusive or'' operator, giving a directed choice: f |>| g gives either the results of f, or those of g only if f is unproductive.

Generalised Path Selectors.
Selection of subtrees by path patterns is familiar to users of the Unix file-system, where such patterns are used to access directory structure. Similar patterns are used in XSL, an XML transformation language [2]. In this connection, we define two path selection combinators /> (pronounced ``slash'') and </ (pronounced ``outside''). The symbols are chosen for mnemonic value -- the slash indicates the ``containing'' relation, and the arrowhead indicates which side is of interest, contained or container respectively.

Our first recursive combinator is deep, which potentially pushes the action of a filter deep inside a document sub-tree. It first tries the given filter on the current item: if it is productive then it stops here, but if no results are returned, then it moves to the children and tries again recursively. When used with a predicate, this strategy searches for the topmost matching elements in the tree. There are variations: deepest searches for the bottommost matching elements; multi returns all matches, even those which are sub-trees of other matches.

Another recursion combinator is foldXml: the expression foldXml f applies the filter f to every level of the tree, from the leaves upwards to the root (at least conceptually -- of course lazy evaluation makes this more efficient). That is to say, f is applied to the children of an element, the element is rebuilt with the results as new children, then f is applied again to the element itself.

2.3  Labellings

One feature that is occasionally useful is the ability to attach labels to items in a sequence, for instance, to number a list of items, or to treat the first/last item of a list differently from the other items. For this purpose, the library provides special labelling combinators. We choose to introduce a new type:
    type LabelFilter a = Content -> [ (a,Content) ]
A LabelFilter is like a CFilter except it attaches a label to each of its results. Note that we could have chosen to fold label values inside the Content type, to yield a uniform CFilter type. However, keeping the labels separate allows them to be of completely polymorphic type: a label could even be another filter for example.

There are several common labelling functions:
    numbered     :: CFilter -> LabelFilter Int
    interspersed :: a -> CFilter -> a -> LabelFilter a
    tagged       :: CFilter -> LabelFilter String
    attributed   :: CFilter -> LabelFilter [(String,String)]
These labelling functions lift a CFilter to the LabelFilter type: numbered f transforms the ordinary filter f into one which attaches integers (from 1 upwards) to the results of f; interspersed a f z attaches the label a to all of the results of f except the last, which gets the label z; tagged f labels every tagged element with its tag name (and non-elements with the empty string); attributed f labels every tagged element with its attribute/value pairs (and non-elements with the empty list).

The combinator `oo` is a new form of composition which drops a LabelFilter back to the CFilter type by application of another filter that consumes the label.

    `oo` :: (a -> CFilter) -> LabelFilter a -> CFilter
For example, the definition of the `et` combinator is:
    et :: (String->CFilter) -> CFilter -> CFilter
    f `et` g = (f `oo` tagged elem) |>| (g `o` text)
`et` combines a filter f on elements with a filter g on text. The element filter f pattern-matches against tagnames -- the tagnames are extracted from the elements by the labelling function tagged.

Furthermore, it is possible to combine labellings. The `x` combinator glues two labelling functions together, pairing the labels they produce.
    `x` :: (CFilter->LabelFilter a) -> (CFilter->LabelFilter b)
               -> (CFilter->LabelFilter (a,b))
So for instance, the following example formats a heterogeneous collection of items as an enumerated list:
    myfilter = enumerate `oo` (numbered `x` tagged) children

    enumerate :: (Int,String) -> CFilter
    enumerate (n,str) = cat [ ((show n++".")!)
                            , mkElem "bold" [ (str!) ]
                            , children ]

2.4  Example

The use of these filters and combinators is illustrated in an example script in Figure 3. This program transforms an ``album'' structure within an XML document, into an HTML document that provides a formatted summary of some of the information from the original. Such a task might be fairly common, for instance in e-commerce applications.

We now describe some of the salient features of the example.

The script first searches recursively for an element tagged as an ``album''. Thus, it works equally well with any XML source document that contains an ``album'' structure anywhere within it, and (correctly) produces no output for documents which do not contain album data.

If the script is used on the document shown in Figure 1, the output is a re-ordering of the internal components of the input. For instance, in the ``body'' part of the output, the ``notes'' section is selected and transformed before the ``catalogno'' elements.

Some assumptions are made about the structure of data within the ``album'' structure. For instance, the expression keep /> tag "title" /> text encodes the assumption that a ``title'' element is an immediate child of the ``album'' element, and that its immediate children include text.

The definition of the notes function is interesting because it makes fewer assumptions about the content of a ``notes'' structure. There is a chained if-then-else choice within the recursive foldXml combinator: the result is that all internal structure of the ``notes'' element is retained except for the replacement of ``trackref''s by emphasised text, and ``albumref''s by HTML links.

The treatment of ``catalogno''s illustrates the use of labelling to extract information that is useful for formatting. It also illustrates the use of ? as a way of querying an attribute's value to change it into textual content, and ! to construct new text.

One of the most striking features of the example as a whole is how selection and testing of old content and construction of new content are uniform, and can be combined almost interchangeably.

2.5  Algebraic laws of combinators

We briefly show how combinators are defined in such a way that various algebraic laws hold. The complete set of laws is given in Figure 4.

Giving all content filters the same type maximises the usefulness of combinators for plugging together functions of this type. However, it is still helpful to identify subclasses of content filters that offer extra guarantees. Two examples of such classes are:
  1. A predicate p has the property that p c always gives as result either [c] or [].
  2. A selector s has the property that s c always gives as result a sequence of contents taken from c. Resulting items do not overlap, and the result sequence respects the order in which the contents were found in c.
So a predicate is a selector, but a selector is not necessarily a predicate.

The `o` form of filter composition could be defined using a Haskell list comprehension
    (f `o` g) c = [c'' | c' <- g c, c'' <- f c']
However, we prefer the equivalent higher-order definition f `o` g = concat . map f . g because it is more convenient in algebraic calculation. (Irish composition is in fact just the flipped-argument version of the Kleisi composition operator in the list monad.) Composition is associative, with none as zero, and keep as identity.

The `with` form of guarded composition is not associative, but we do have some laws, particularly idempotence. We also have a promotion law about combined uses of `with` and `o`. The dual operator, `without` has parallel laws.

The /> path selector is associative but </ is not, and there are some idempotence laws for both. Most important however, are the various promotion laws for changing the order of application of />, </, and with.

The directed choice operator |>| viewed by itself appears to be algebraically sensible, but it does not seem to have useful algebraic properties in connection with other combinators because of its bias towards the left operand. The simpler result-appending combinator ||| could be an alternative to the directed choice operator, and would probably lead to more laws, but it has less `application bite'. A potentially serious problem is that the |||-combination of two selectors is not necessarily a selector.

The recursion operator deep has some minor laws, one of which, the depth law, is more profound. We have not yet fully investigated the properties of deepest, multi, and foldXml.

Laws such as these, in particular the promotion and simplification laws, might be used to write an optimising implementation of the combinators. We would like to define normal forms, that is, a canonical form that is, in some sense, most ``direct'' in expressing a selection or other operation. All non-canonical combinations could then be transformed into the normal forms by automatic means, leading to programs that remain readable to the author, but traverse the document tree efficiently (in either space, time, or both). As a trivial example, the expression deep none visits every node of the tree, whereas the equivalent expression none visits none at all.

3  Translation of DTDs to Types

3.1  DTDs

So far we have considered document-processing as generic tree transformations, where markup is matched textually at runtime, and no account is taken of any deeper meaning of tags.

However, when the DTD for a document is available, the meaning it defines for markup tags can be used to powerful effect. The most basic use is to confirm semantic validity: a stronger notion than mere syntactic well-formedness. A DTD defines a grammar for document content: it specifies a vocabulary of markup tags, and the allowed content and attributes for each tag. Document validation is therefore a straightforward check that the document's structure conforms to the vocabulary and grammar given in the DTD.

XML document validators are readily available. However, we go further and define the idea of valid document processing. A valid processing script is one which produces a valid document as output, given a valid document as input. We achieve this by demonstrating a correspondence between the DTD of a document and the definition of a set of algebraic types in Haskell, and the consequent correspondence between the document's content and a structured Haskell value. Hence, by writing document processing scripts to manipulate the typed Haskell value, the script validation problem is just an instance of normal Haskell type inference.

At the moment, manipulation of typed values is outside the scope of application of the generic combinator library described in Section 2. However, we hold out the hope that these two approaches can be combined to provide valid polymorphic and higher-order scripting. That is to say, we envisage writing generic (yet fully type-checked) document-processing applications, parameterised on scripts for processing sub-documents.

3.2  DTD translations.

An example DTD for the document shown earlier is given in Figure 5. The immediate features to note are: There are some obvious correspondences between this very restricted form of type language and the richer type language of Haskell. Each element declaration is roughly speaking a new datatype declaration. Sequence is like product types (i.e. single-constructor values). Choice is like sum types (i.e. multi-constructor values). Optionality is just the familiar ``Maybe'' type. Repetition is lists.

Attribute lists also have a translation: because they are unordered and accessed by name, Haskell named-fields are a good representation. Optionality can again be expressed as ``Maybe'' types. Attribute values that are constrained to a particular value-set can be modelled by defining a new enumeration type encompassing the permitted strings.

These rules are formalised in Figure 6. An implementation of these rules (with some additional rules to eliminate redundancy) translated the DTD in Figure 5 into the Haskell type declarations shown in Figure 7.

Along with the type declarations, we also need functions which read and write values of these types to and from actual XML documents. It is relatively straightforward to generate these automatically from the type declarations alone by defining appropriate type classes, then deriving an instance for each generated type using a tool like DrIFT [12].

Note that the type translation uses only datatypes and newtypes, never type synonyms. This is a result of needing to write values out as XML -- a type synonym is indistiguishable from the type it abbreviates, but the generated types must be distinct in order to be able to re-introduce enclosing start and end tags with the correct markup.

4  Related Work

There are several infant processing languages surrounding XML: Other researchers have written toolkits for XML-processing in functional languages: for instance, Christian Lindig's XML parser in O'Caml [6], and Andreas Neumann's validating XML parser in SML [7]. To our knowledge, none of these have attempted to provide transformation capabilities in either a combinator style or a type-translation style.

Philip Wadler has written a short formal semantics of XSL selection patterns [11].

The combinator approach to applications programming is of course not new: parser combinators (Hutton/Meijer, Duponcheel/Swierstra, etc.), pretty-printing combinators (Hughes/PeytonJones, Wadler etc.), SKI combinators? (Turner? etc.). This section is incomplete.

5  Conclusions and Future Work

Our conclusions are that Haskell is a very suitable language for scripting generic XML document processing. A good set of combinators, designed with algebraic properties in mind, can be powerful enough and flexible enough to describe a full range of selection, testing, and construction operations in a uniform framework. We have also separately demonstrated the possibility of reading and writing XML documents as fully-typed Haskell values, which gives an opening to using the type system to ensure scripts are valid.

Some work remains in making these tools and components complete, polished, and secure. There is much scope for designing useful extensions to the current model, for instance to unify the LabelFilter and CFilter types, allowing an even more uniform interface.

Space-efficient Combinators.
The space-behaviour of XML processors is an important issue. Many lazy functional programs that process trees in pre-order left-to-right fashion can be formulated to run in log(N) space. (Roughly, the part of the tree that is held in memory corresponds to a path from the root to some node that is currently the focus of computation: to the left are `garbage' subtrees already processed, to the right are subtrees not yet evaluated.) However, our current combinators are by no means guaranteed to give this sort of space behaviour when composed in arbitrary ways.

Algebra of Deletion and Editing Combinators.
So far our algebraic investigations have concentrated on combinators for selecting sections of an XML document. The result of any selection corresponds to a sequence of sub-trees from the full document tree. We propose to move on next to a more general class of deletion operations in which the sub-trees can be thinned and pruned in various ways.

Normal form optimisation.
In an extended exposition of the combinator-library approach, Hughes [5] has shown how the algebraic properties of combinators can be used as a driving specification. First, laws are used to show that every combination is equivalent to a restricted class of normal forms. An advanced implementation then concentrates on making the evaluation of normal-form combinations as efficient as possible, and also arranges that all other combinations are `self-optimising' into normal forms. (Similar techniques have been used to excellent effect in programming languages based on calculi such as Hoare's CSP.)

We aim to define normal forms for XML processing combinations, and hence to develop a more advanced implementation of this kind.

Multiple documents.
An interesting extension of single-document scripting is the handling of multiple documents. Whilst producing more than one output document presents no great problem, the issues involved in merging several input documents are of greater interest, with new challenges in designing appropriate combinators for scripting. It seems sensible to work on both problems together, since in some sense they are inverses. Their two families of combinators should enjoy useful relationships.

``Secure'' XML processing.
There are several other potential approaches to checking script-validity.


Canon Research Centre (Europe) Ltd. suggested this line of work and funded it. Philip Wadler, Christian Lindig, and Joe English gave very helpful comments on an earlier draft of this paper and software.


Tim Bray, Jean Paoli, and C.M. Sperberg-Macqueen. Extensible Markup Language (XML) 1.0 (W3C Recommendation). Technical Report http://www.w3.org/TR/1998/REC-xml-19980210, WWW Consortium, February 1998.

James Clark and Stephen Deach. Extensible Stylesheet Language (XSL) Version 1.0 (Working Draft). Technical Report http://www.w3.org/TR/1998/WD-xsl-19981216, WWW Consortium, December 1998.

Jon Fairbairn. Making form follow function: An exercise in functional programming style. Software -- Practice and Experience, 17(6):379--386, June 1987.

John Hughes. Why functional programming matters. Computer Journal, 32(2), April 1989.

John Hughes. The design of a pretty-printing library. In 1st Intl. School on Advanced Functional Programming, pages 53--96. Springer LNCS Vol. 925, 1995.

Christian Lindig. Tony: an XML parser and pretty-printer written in Objective Caml. Technical Report http://www.cs.tu-bs.de/softech/people/lindig/tony.html, Technical University of Braunschweig, January 1999.

Andreas Neumann. fxp: the functional XML parser. Technical Report http://www.informatik.uni-trier.de/~neumann/Fxp/, University of Trier, February 1999.

Jonathan Robie, Joe Lapp, and David Schach. XML Query Language (XQL) (Proposal). Technical Report http://www.w3.org/TandS/QL/QL98/pp/xql.html, WWW Consortium, November 1998.

Unknown. Document Style Semantics and Specification Language (DSSSL) (Final Draft). Technical Report http://occam.sjf.novell.com/dsssl/dsssl96/, Novell Publications, 1996.

W3C. Document Object Model (DOM) Level 1 Specification, Version 1.0 (W3C Recommendation). Technical Report http://www.w3.org/TR/1998/REC-DOM-Level-1-19981001, WWW Consortium, October 1998.

Philip Wadler. A formal model of pattern matching in XSL. Technical Report http://www.cs.bell-labs.com/~wadler/xsl/, Bell Labs, January 1999.

Noel Winstanley. Reflections on instance derivation. In 1997 Glasgow Functional Programming Workshop. BCS Workshops in Computer Science, September 1997.

<?xml version='1.0'?>
<!DOCTYPE album SYSTEM "album.dtd">
  <title>Time Out</title>
  <artist>Dave Brubeck Quartet</artist>
  <coverart style='abstract'>
    <location thumbnail='pix/small/timeout.jpg'

  <catalogno label='Columbia' number='CL 1397' format='LP'/>
  <catalogno label='Columbia' number='CS 8192' format='LP'/>
  <catalogno label='Columbia' number='CPK 1181' format='LP' country='Korea'/>
  <catalogno label='Sony/CBS' number='Legacy CK 40585' format='CD'/>

    <player name='Dave Brubeck' instrument='piano'/>
    <player name='Paul Desmond' instrument='alto sax'/>
    <player name='Eugene Wright' instrument='bass'/>
    <player name='Joe Morello' instrument='drums'/>

    <track title='Blue Rondo &agrave; la Turk' credit='Brubeck' timing='6m42s'/>
    <track title='Strange Meadow Lark' credit='Brubeck'  timing='7m20s' />
    <track title='Take Five' credit='Desmond'  timing='5m24s' />
    <track title='Three To Get Ready' credit='Brubeck'  timing='5m21s' />
    <track title="Kathy's Waltz" credit='Brubeck'  timing='4m48s' />
    <track title="Everybody's Jumpin'" credit='Brubeck'  timing='4m22s' />
    <track title='Pick Up Sticks' credit='Brubeck'  timing='4m16s' />

  <notes author="unknown">
    Possibly the DBQ's most famous album, this contains
    <trackref link='#3'>Take Five</trackref>,
    the most famous jazz track of that period.  These experiments in
    different time signatures are what Dave Brubeck is most remembered for.
    Recorded Jun-Aug 1959 in NYC.  See also the sequel,
      <albumref link='cbs-timefurthout'>Time Further Out</albumref>.
Figure 1: An example XML document.

Predicates none :: CFilter zero/failure
  keep :: CFilter identity/success
  elem :: CFilter tagged element?
  text :: CFilter plain text?
  tag :: String -> CFilter named element?
  attr :: String -> CFilter element has attribute?
  attrval :: String -> CFilter element has attribute/value?
Selection children :: CFilter children of element
  (?) :: String -> CFilter value of attribute
Construction literal :: String -> CFilter build plain text
  (!) :: String -> CFilter synonym for literal
  mkElem :: String -> [CFilter] -> CFilter build element
  mkElemAttrs :: String -> [(String,CFilter)]  
  -> [CFilter] -> CFilter build element with attributes
  replaceTag :: String -> CFilter replace element's tag
  replaceAttrs :: [(String,CFilter)] -> CFilter replace element's attributes
Combinators o :: CFilter -> CFilter -> CFilter Irish composition
  (|||) :: CFilter -> CFilter -> CFilter append results
  cat :: [CFilter] -> CFilter concatenate results
  with :: CFilter -> CFilter -> CFilter guard
  without :: CFilter -> CFilter -> CFilter negative guard
  (/>) :: CFilter -> CFilter -> CFilter interior search
  (</) :: CFilter -> CFilter -> CFilter exterior search
  et :: (String->CFilter) -> CFilter -> CFilter disjoint union
  (?>) :: CFilter -> ThenElse CFilter -> CFilter if-then-else choice
  data ThenElse a = a :> a rhs of choice
  (|>|) :: CFilter -> CFilter -> CFilter directed choice
  deep :: CFilter -> CFilter recursive search (topmost)
  deepest :: CFilter -> CFilter recursive search (deepest)
  multi :: CFilter -> CFilter recursive search (all)
  chip :: CFilter -> CFilter ``in-place'' application to children
  foldXml :: CFilter -> CFilter recursive application
Definitions f `o` g = concat. map f . g Irish composition
  f ||| g = \c-> f c ++ g c append results
  cat fs = \c-> concatMap (\f->f c) fs concatenate results
  f `with` g = filter (not.null.g) . f guard
  f `without` g = filter (null.g) . f negative guard
  f /> g = g `o` children `o` f interior search
  f </ g = f `with` (g `o` children) exterior search
  f `et` g = (f `oo` tagged elem) |>| (g `o` text) disjoint union
  p ?> f :> g = \c-> if (not.null.p) c then f c else g c choice
  f |>| g = f ?> f :> g directed choice
  deep f = f |>| (deep f `o` children) recursive search (topmost)
  deepest f = (deepest f `o` children) |>| f recursive search (deepest)
  multi f = f ||| (multi f `o` children) recursive search (all)
  foldXml f = f `o` (chip (foldXml f)) recursive application

Figure 2: Content filters and filter combinators.

module Main where
import Xml
main = processXMLwith (album `o` deep (tag "album"))

album =
    [ hhead
      [ htitle
        [ text `o` children `o` tag "artist" `o` children `o` tag "album"
        , literal ": "
        , keep /> tag "title" /> text
    , hbody [("bgcolor",("white"!))]
        [ hcenter [ h1 [ keep /> tag "title" /> text ] ]
        , h2 [ ("Notes"!) ]
        , hpara [ notes `o` (keep /> tag "notes") ]
        , summary

notes = foldXml (text           ?> keep            :>
                 tag "trackref" ?> replaceTag "EM" :>
                 tag "albumref" ?> mkLink          :> children)

summary =
  htable [("BORDER",("1"!))]
      [ hrow [ hcol [ ("Album title"!) ]
             , hcol [ keep /> tag "title" /> text ] ]
      , hrow [ hcol [ ("Artist"!) ]
             , hcol [ keep /> tag "artist" /> text ] ]
      , hrow [ hcol [ ("Recording date"!) ]
             , hcol [ keep /> tag "recordingdate" /> text ] ]
      , hrow [ hcola [("VALIGN",("top"!))] [ ("Catalog numbers"!) ]
             , hcol  [ hlist [ catno `oo` numbered (deep (tag "catalogno")) ] ] ]

catno n = mkElem "LI" [ ((show n++". ")!), ("label"?), ("number"?)
                      , ("("!), ("format"?), (")"!) ]

mkLink = mkElemAttr "A" [ ("HREF",("link"?)) ] [ children ]
Figure 3: An example document-processing script using filter combinators. An ``album'' structure is found somewhere inside a document, and transformed into an HTML document giving the product details. Note how the semantic elements of the original document are selected, re-ordered, and transformed.

Irish composition f `o` (g `o` h) = (f `o` g) `o` h associativity
  none `o` f = f `o` none = none zero
  keep `o` f = f `o` keep = f identity
Guards f `with` keep = f identity
  f `with` none = none `with` f = none zero
  (f `with` g) `with` g = f `with` g idempotence
  (f `with` g) `with` h = (f `with` h) `with` g promotion
  (f `o` g) `with` h = (f `with` h) `o` g promotion
  f `without` keep = none `without` f = none zero
  f `without` none = keep identity
  (f `without` g) `without` g = f `without` g idempotence
  (f `without` g) `without` h
  = (f `without` h) `without` g promotion
  (f `o` g) `without` h = (f `without` h) `o` g promotion
Path selectors f /> (g /> h) = (f /> g) /> h associativity
  none /> f = f /> none = none zero
  keep /> f = f `o` children  
  f /> keep = children `o` f  
  keep /> keep = children  
  none </ f = f </ none = none zero
  f </ keep = f `with` children  
  (f </ g) </ g = f </ g idempotence
  (f </ g) /> g = f /> g idempotence
  (f /> g) </ h = f /> (g </ h) promotion
  (f </ g) </ h = (f </ h) </ g promotion
  f `o` (g /> h) = g /> (f `o` h) promotion
  (f /> g) `o` h = (f `o` h) /> g promotion
  (f /> g) `with` h = f /> (g `with` h) promotion
  (f </ g) `with` h = (f `with` h) </ g promotion
Directed choice (f |>| g) |>| h = f |>| (g |>| h) associativity
  keep |>| f = keep  
  none |>| f = f |>| none = f identity
  f |>| f = f idempotence
Recursion deep keep = keep simplification
  deep none = none simplification
  deep children = children simplification
  deep (deep f) = deep f depth law
Misc elem |>| text = text |>| elem = keep completeness
  elem `o` text = text `o` elem = none excluded middle
  children `o` elem = children  
  children `o` text = none  

Figure 4: Algebraic laws of combinators.

<?xml version='1.0'?>
<!DOCTYPE album SYSTEM "album.dtd" [
<!ELEMENT album (title, artist, recordingdate?, coverart, (catalogno)+,
                 personnel, tracks, notes) >
<!ELEMENT recordingdate EMPTY>
    <!ATTLIST recordingdate date CDATA #IMPLIED
                            place CDATA #IMPLIED>
<!ELEMENT coverart (location)? >
    <!ATTLIST coverart style CDATA #REQUIRED>
<!ELEMENT location EMPTY >
    <!ATTLIST location thumbnail CDATA #IMPLIED
                       fullsize CDATA #IMPLIED>
<!ELEMENT catalogno EMPTY >
    <!ATTLIST catalogno label CDATA #REQUIRED
                        number CDATA #REQUIRED
                        format (CD | LP | MiniDisc) #IMPLIED
                        releasedate CDATA #IMPLIED
                        country CDATA #IMPLIED>
<!ELEMENT personnel (player)+ >
<!ELEMENT player EMPTY >
    <!ATTLIST player name CDATA #REQUIRED
                      instrument CDATA #REQUIRED>
<!ELEMENT tracks (track)* >
    <!ATTLIST track title CDATA #REQUIRED
                    credit CDATA #IMPLIED
                    timing CDATA #IMPLIED>
<!ELEMENT notes (#PCDATA | albumref | trackref)* >
    <!ATTLIST notes author CDATA #IMPLIED>
<!ELEMENT albumref #PCDATA>
    <!ATTLIST albumref link CDATA #REQUIRED>
<!ELEMENT trackref #PCDATA>
    <!ATTLIST trackref link CDATA #IMPLIED>
Figure 5: An example DTD.

Type declarations    
T[[<ELEMENT n spec>]] = newtype m = m (m_Attrs, m_)
    newtype m_ = D[[spec]] m
    where m = M[[n]]
T[[<ATTLIST n decl0 ... declk>]] = data m_Attrs = m_Attrs {F[[decl0]], ..., F[[ declk]] }
    A[[ declk]]
    where m = M[[n]]
RHS of type declarations    
D[[ ( x0, x1, ..., xk ) ]] m = C[[ m x0 ... xk ]] D'[[ x0 ]] D'[[ x1 ]] ... D'[[ xk ]]
D[[ ( x0 | x1 | ... | xk ) ]] m = C[[ m x0 ]] D'[[ x0 ]]
    | C[[ m x1 ]] D'[[ x1 ]]
    | ...
    | C[[ m xk ]] D'[[ xk ]]
D[[ (x)? ]] m = Maybe D'[[ x ]]
D[[ (x)+ ]] m = List1 D'[[ x ]]
D[[ (x)* ]] m = [ D'[[ x ]] ]
D[[ x ]] m = C[[ m x ]]
Inner type expressions    
D'[[ ( x0, x1, ..., xk ) ]] = ( D'[[ x0 ]] , D'[[ x1 ]] , ... D'[[ xk ]] )
D'[[ ( x0 | x1 | ... | xk ) ]] = (OneOfn D'[[ x0 ]] D'[[ x1 ]] ... D'[[ xk ]] )
D'[[ (x)? ]] = (Maybe D'[[ x ]] )
D'[[ (x)+ ]] = (List1 D'[[ x ]] )
D'[[ (x)* ]] = [ D'[[ x ]] ]
D'[[ x ]] = C[[ x ]]
Name mangling    
C[[ m x0 x1 ... xk ]] = ... unique constructor name based on m
M[[ n ]] = ... ensure initial upper-case
M'[[ n ]] = ... ensure initial lower-case
Named fields    
F[[ n CDATA #REQUIRED ]] = M'[[ n ]] :: String
F[[ n CDATA #IMPLIED ]] = M'[[ n ]] :: Maybe String
F[[ n (s0|s1|...|sk) #REQUIRED ]] = M'[[ n ]] :: M[[ n ]]
F[[ n (s0|s1|...|sk) #IMPLIED ]] = M'[[ n ]] :: Maybe M[[ n ]]
Constrained attributes    
A[[ n CDATA ... ]] = f
A[[ n (s0|s1|...|sk) ... ]] = data M[[ n ]] = M[[ s0 ]] | M[[ s1 ]] | ... | M[[ sk ]]

Figure 6: DTD translation rules.

module AlbumDTD where

data Album = 
    Album Title Artist (Maybe Recordingdate) Coverart [Catalogno]
          Personnel Tracks Notes
newtype Title = Title String
newtype Artist = Artist String
newtype Recordingdate = Recordingdate Recordingdate_Attrs
data Recordingdate_Attrs = Recordingdate_Attrs {
    date :: Maybe String,
    place :: Maybe String }
newtype Coverart = Coverart (String, Maybe Location)
newtype Location = Location Location_Attrs
data Location_Attrs = Location_Attrs {
    thumbnail :: Maybe String,
    fullsize  :: Maybe String }
newtype Catalogno = Catalogno Catalogno_Attrs
data Catalogno_Attrs = Catalogno_Attrs {
    label :: String,
    number :: String,
    format :: Maybe Format,
    releasedate :: Maybe String,
    country :: Maybe String }
data Format = CD | LP | MiniDisc
newtype Personnel = Personnel [Player]
newtype Player = Player Player_Attrs
data Player_Attrs = Player_Attrs {
    name :: String,
    instrument :: String }
newtype Tracks = Tracks [Track]
newtype Track = Track Track_Attrs
data Track_Attrs = Track_Attrs {
    title :: String,
    credit :: Maybe String,
    timing :: Maybe String }
newtype Notes = Notes (Maybe String, [Notes_])
data Notes_ = 
    Notes_Str String
  | Notes_Albumref Albumref
  | Notes_Trackref Trackref
newtype Albumref = Albumref (String,String)
newtype Trackref = Trackref (Maybe String,String)
Figure 7: DTD translated to Haskell types.

The XML toolkit from this paper is available on the WWW at http://www.cs.york.ac.uk/fp/XmlLib/
For those familiar with the detail of XML, entity references within the document are treated as plain text.
Actually, a list of attribute/filter pairs. Each filter is applied to the current element and the resultant content is flattened to a string value which is assigned to the named attribute.
Actually a left-section of the infix operator. Because filters are higher-order, their use is eta-reduced and the rightmost argument disappears from view.

This document was translated from LATEX by HEVEA.