[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.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:

Ease of extension and variation. If a scripting language doesn't have some needed functionality, or forces it to be achieved in some horrible way, the script-writer is stuck. Extending the language is likely to be a Big Deal. A combinator library, however, can be enlarged comparatively straightforwardly to extend the model of XML processing. All the combinator definitions are accessible, and most of them are short and simple.
Computational power. When it comes to any general computation that may be needed to process XML, scripting languages tend to offer either a few weak ingredients such as a limited expression language, or a hook into a programming system at a completely different level of abstraction. But if XML scripts are programs in a language such as Haskell, the full power of the native language is immediately available.
Abstraction, generality and reuse. Almost any pattern occurring in a combinator program can be isolated and defined as a separate re-usable idea [4]. This applies not only at the combinator level, but at the application level too, where the common ideas in a family of similar applications might easily be defined in a higher-level library. This form of re-use makes the development of each application that much quicker and less error-prone.
Laws for reasoning about scripts. How are the semantics of a scripting language defined? Probably by an informal operational explanation, with illustrative examples. This makes it difficult to reason with confidence about the meanings of scripts. Is expression A just a stylistic variation of expression B or are there XML documents for which the two could give different results? In a functional-language, the semantics of scripts can be defined in terms of the equations that define the combinators. From these equations, properties such as associativity and distribution can often be demonstrated quite simply (see Section 2.5), and exploited in more advanced implementations.
Implementation tools `for free'. A scripting language is no use without tools for processing it. Is there an interactive interpreter as well as a compiler? A type-checker? A time and space profiler? All these things are available for Haskell and therefore immediately applicable to XML scripts directly expressed as Haskell programs.

Of course, there are disadvantages too.

Distance from target language. A domain-specific language like XSL [2] has the property that a script is in fact an expression in the target language (XML): it uses exactly the XML syntax for building new tagged elements. By contrast, our combinator-based scripts must use a different syntax due to the underlying language, and although they can be much more readable than XSL scripts, the linguistic gap is perhaps large enough to cause confusion, and increase learning costs.
Living in an unfamiliar world. A related problem is this: the style in which a combinator program is written is very like a small domain-specific language. People writing scripts may be beguiled by this apparent simplicity, but when they make an small error, they could potentially drop into some weird corner of the Haskell language and either get error messages that are totally incomprehensible to them, or worse, the script might actually compile to code which does something utterly strange.
Potentially large tools. The major Haskell compilers sometimes suffer by requiring a lot of space, both for code and for runtime usage. This fault is not universal, for instance nhc13 and Hugs have comparatively small footprints, but in return, these tools trade-off speed for space.

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.

Basic predicate and selection filters. The filter elem is a predicate, returning just this item if it is an element, or nothing otherwise. Conversely, text returns this item only if is plain text,² and nothing otherwise. The filter children returns the immediate children of an element if it has any, or nothing if this content-item is not an element. The filter tag t returns this item only if it is an element whose tag name is the string t. The filter attr a returns this item only if it is an element containing the attribute name a. The filter attrval (a,v) returns this item only if is an element containing the attribute a with the value v.
Basic construction filters. The function literal s makes a text content containing just the string s. The function mkElem t fs builds a content element with the tag t; the argument fs is a list of filters, each of which is applied to the current item, and all their results are collected to become the children of the new element. The function mkElemAttrs t avs fs is just like mkElem except that its extra parameter avs is a list of attribute values ³ to be attached to the tag.

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,⁴ 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.

Recursion.

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:

A predicate p has the property that p c always gives as result either [c] or [].
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:

For every element, there is a specification of allowed inner elements (ELEMENT declaration), and possibly also a specification of allowed attribute values (ATTLIST declaration).
For inner content, the grammar allows sequence (commas), choice (vertical bar), optionality (question mark), and repetition (star or plus).
Where the inner content declaration allows free text (PCDATA), choice between text and other elements is permitted, but sequencing of those elements is not permitted.
In attribute lists, some values are mandatory (REQUIRED) and some are optional (IMPLIED); attribute values can either be unconstrained strings (CDATA) or a member of some pre-defined set of string values.

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:

XSL [2] (eXtensible Style Language) is a W3C-proposed declarative language for expressing a limited form of transformations on XML documents, originally intended for rendering to a layout-based format, e.g. HTML, PostScript, etc., but now widely used for XML�XML transformations.
DSSSL [9] (Document Style Semantics and Specification Language) is a mature ISO standard with no complete implementations. It is similar in essence to XSL, but deals with full SGML input, and is based on Scheme.
DOM [10] (Document Object Model) is a developing W3C-standard applications programming interface, heavily imperative and slightly object-oriented in flavour.
XQL [8] (eXtensible Query Language) is a non-W3C proposal for a selection language over XML documents. Many of its ideas have now been incorporated into XSL.

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.

General scripting. When using the generic combinator library, one can treat each individual XML�XML transformation as a typeless version of a typed transition (the document subtree is changed from one DTD to another). Just as scripts are composed using combinators, their DTDs can also be composed into new DTDs. Taking this approach, a DTD can be re-constructed for the whole script. Finally, this DTD can be compared with the input and output DTDs. Scripts can be generic over many DTDs, just as types can be polymorphic, so the final comparison is one of DTD-inclusion rather than equality.
Selection combinators. An extension to our current library of selection combinators is to extract not only the required subtrees, but also the sub-DTD within which the selection is a valid document rather than just a fragment. Hence, any sub-document can be made valid simply by attaching a new DTD to it. This would perhaps fit naturally into the labelling scheme of Section 2.3.
Bringing together combinators and types. It has been pointed out that if the CFilter type were parameterised as: type CFilter m a b = a -> m b then many more algebraic laws might reveal themselves. In particular, the monadic nature of composition immediately comes to mind. This approach might also allow the type-translation of XML DTDs to be fitted inside the combinator framework, providing validity checks (through type inference) in addition to generic transformation.
Merging. As part of the problem of writing scripts which merge document contents, one has to consider merging their DTDs, to preserve the validity of the merged output.

Acknowledgements

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.

References

[1]: 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.
[2]: 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.
[3]: Jon Fairbairn. Making form follow function: An exercise in functional programming style. Software -- Practice and Experience, 17(6):379--386, June 1987.
[4]: John Hughes. Why functional programming matters. Computer Journal, 32(2), April 1989.
[5]: 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.
[6]: 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.
[7]: Andreas Neumann. fxp: the functional XML parser. Technical Report http://www.informatik.uni-trier.de/~neumann/Fxp/, University of Trier, February 1999.
[8]: 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.
[9]: Unknown. Document Style Semantics and Specification Language (DSSSL) (Final Draft). Technical Report http://occam.sjf.novell.com/dsssl/dsssl96/, Novell Publications, 1996.
[10]: 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.
[11]: Philip Wadler. A formal model of pattern matching in XSL. Technical Report http://www.cs.bell-labs.com/~wadler/xsl/, Bell Labs, January 1999.
[12]: 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">
<album>
  <title>Time Out</title>
  <artist>Dave Brubeck Quartet</artist>
  <coverart style='abstract'>
    <location thumbnail='pix/small/timeout.jpg'
              fullsize='pix/covers/timeout.jpg'/>
  </coverart>

  <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'/>

  <personnel>
    <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'/>
  </personnel>

  <tracks>
    <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' />
  </tracks>

  <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>.
  </notes>
</album>

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 =
  html
    [ 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 title #PCDATA>
<!ELEMENT artist #PCDATA>
<!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)* >
<!ELEMENT track EMPTY>
    <!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 decl₀ ... decl_k>]] = data m_Attrs = m_Attrs {F[[decl₀]], ..., F[[ decl_k]] }

A[[decl₀]]

...

A[[ decl_k]]

where m = M[[n]]

RHS of type declarations

D[[ ( x₀, x₁, ..., x_k ) ]] m = C[[ m x₀ ... x_k ]] D'[[ x₀ ]] D'[[ x₁ ]] ... D'[[ x_k ]]

D[[ ( x₀ | x₁ | ... | x_k ) ]] m = C[[ m x₀ ]] D'[[ x₀ ]]

| C[[ m x₁ ]] D'[[ x₁ ]]

| ...

| C[[ m x_k ]] D'[[ x_k ]]

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'[[ ( x₀, x₁, ..., x_k ) ]] = ( D'[[ x₀ ]] , D'[[ x₁ ]] , ... D'[[ x_k ]] )

D'[[ ( x₀ | x₁ | ... | x_k ) ]] = (OneOf_n D'[[ x₀ ]] D'[[ x₁ ]] ... D'[[ x_k ]] )

D'[[ (x)? ]] = (Maybe D'[[ x ]] )

D'[[ (x)+ ]] = (List1 D'[[ x ]] )

D'[[ (x)* ]] = [ D'[[ x ]] ]

D'[[ x ]] = C[[ x ]]

Name mangling

C[[ m x₀ x₁ ... x_k ]] = ... 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 (s₀|s₁|...|s_k) #REQUIRED ]] = M'[[ n ]] :: M[[ n ]]

F[[ n (s₀|s₁|...|s_k) #IMPLIED ]] = M'[[ n ]] :: Maybe M[[ n ]]

Constrained attributes

A[[ n CDATA ... ]] = f

A[[ n (s₀|s₁|...|s_k) ... ]] = data M[[ n ]] = M[[ s₀ ]] | M[[ s₁ ]] | ... | M[[ s_k ]]

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.

1: The XML toolkit from this paper is available on the WWW at http://www.cs.york.ac.uk/fp/XmlLib/
2: For those familiar with the detail of XML, entity references within the document are treated as plain text.
3: 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.
4: 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 L^AT_EX by H^EV^EA.

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

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

Type declarations
T[[`<ELEMENT n` `spec>`]]	=	`newtype` `m` `=` `m` `(m_Attrs,` `m_)`
		`newtype` `m_ =` `D[[spec]]` `m`
		where `m` `=` `M[[n]]`
T[[`<ATTLIST n` `decl₀` `...` `decl_k>`]]	=	`data` `m_Attrs =` `m_Attrs {F[[decl₀]], ...,` `F[[` `decl_k]]` `}`
		A[[decl₀]]
		...
		A[[ decl_k]]
		where `m` `=` `M[[n]]`

RHS of type declarations
D[[ ( x₀, x₁, ..., x_k ) ]] m	=	C[[ m x₀ ... x_k ]] D'[[ x₀ ]] D'[[ x₁ ]] ... D'[[ x_k ]]
D[[ ( x₀ \| x₁ \| ... \| x_k ) ]] m	=	C[[ m x₀ ]] D'[[ x₀ ]]
		`\|` C[[ m x₁ ]] D'[[ x₁ ]]
		`\|` ...
		`\|` C[[ m x_k ]] D'[[ x_k ]]
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'[[ ( x₀, x₁, ..., x_k ) ]]	=	`(` D'[[ x₀ ]] `,` D'[[ x₁ ]] `,` ... D'[[ x_k ]] `)`
D'[[ ( x₀ \| x₁ \| ... \| x_k ) ]]	=	`(OneOf_n` D'[[ x₀ ]] D'[[ x₁ ]] ... D'[[ x_k ]] `)`
D'[[ (x)? ]]	=	`(Maybe` D'[[ x ]] `)`
D'[[ (x)+ ]]	=	`(List1` D'[[ x ]] `)`
D'[[ (x)* ]]	=	`[` D'[[ x ]] `]`
D'[[ x ]]	=	C[[ x ]]

Name mangling
C[[ m x₀ x₁ ... x_k ]]	=	... 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 (s₀\|s₁\|...\|s_k) #REQUIRED` ]]	=	M'[[ n ]] `::` M[[ n ]]
F[[ `n (s₀\|s₁\|...\|s_k) #IMPLIED` ]]	=	M'[[ n ]] `:: Maybe` M[[ n ]]

Constrained attributes
A[[ `n CDATA ...` ]]	=	f
A[[ `n (s₀\|s₁\|...\|s_k) ...` ]]	=	`data` M[[ n ]] `=` M[[ s₀ ]] `\|` M[[ s₁ ]] `\|` ... `\|` M[[ s_k ]]