- Key concepts
- Pair and Record Patterns
- Sequence patterns
- XML elements and attributes
- Handling optional attributes
- Recursive patterns
- Compiling regular expression patterns

You can cut and paste the code on this page and test it on the online interpreter.

# Patterns

CDuce: documentation: Tutorial: Patterns

Overloading Error messages and Warnings

## Key concepts

TO BE DONE

## Pair and Record Patterns

TO BE DONE

## Sequence patterns

TO BE DONE

## XML elements and attributes

Up to now we used for XML elements (and their types) an abbreviated notation as for `<table align="center" valign="top">[`some_content`]`. Actually, the precise syntax of XML elements is

    <(expr1) (expr2)>expr3

where `expr1`, `expr2`, and`expr3` are generic expressions. The same holds true for record patterns, but where the generic expressions are replaced by generic patterns (that is, `<(p1) (p2)>p3`). It is important to notice that the parentheses (in red) `<(expr1) (expr2)>expr3` are part of the syntax.
Even if `expr1`, `expr2`, and `expr3` may be any expression, in practice they mostly occur in a very precise form. In particular, `expr1` is an atom, `expr2` is a record value, while `expr3` is a sequence. Since this corresponds, by far, to the most common use of XML elements we have introduced some handy abbreviations: in particular we allow the programmer to omit the surrounding `(` )` when `expr1` is an atom, and to omit the surrounding `{ }` and the infix semicolons `;` when `expr2` is a record value. This is why we can write `<table align="center" valign="top">[` ...`]`, rather than `<(`table) ({align="center"; valign="top"}) >[` ...`]`

While these abbreviations are quite handy, they demand some care when used in record patterns. As we said, the general form of a record pattern is:

    <(p1) (p2)>p3

and the same abbreviations as for expressions apply. In particular, this means that, say, the pattern `<t (a)>_` stands for `<(`t) (a)>_`. Therefore while `<t (a)>_` matches all the elements of tag `t` (and captures in the variable `a` the attributes), the pattern `<(t) (a)>_` matches all XML elements (whatever their tag is) and captures their tag in the variable `t` (and their attributes in `a`). Another point to notice is that `<t>_` stands for `<t ({})>_` (more precisely, for `<(`t) ({})>_`). Since `{}` is the closed empty record type, then it matches only the empty record. Therefore `<t>_` matches all elements of tag `t` that have no attibute. We have seen at the beginning of this tutorial that in order to match all element of tag `t` independently from whether they have attributes or not, we have to use the pattern `<t ..>_` (which stands for `<(`t) ({..})>_`).

In the following we enumerate some simple examples to show what we just explained. In these examples we use the following definitions for bibliographic data:

    type Biblio  = [(Paper|Book)*]
    type Paper   = <paper isbn=?String year=String>[ Author+ Title Conference Url? ]
    type Book    = <book isbn=String> [ Author+ Title Url? ]
    type Author  = <author>[ PCDATA ]
    type Title   = <title>[ PCDATA ]
    type Conference = <conference>[ PCDATA ]
    type Url     = <url>[ PCDATA ]

Let `bib` be of type `Biblio` then

    transform bib with
         <book (a)> [ (x::(Any\Url)|_)* ] -> [ <book (a)> x ]

returns the list of all books without their Url element (if any).

    transform bib with
         <(book) (a)> [ (x::(Any\Url)|_)* ] -> [ <(book) (a)> x ]

returns the bibliography in which all entries (either books or papers) no longer have their Url elements (`book` is now a capture variable). Equivalently we could have pushed the difference on tags:

    transform bib with
         <(book) (a)> [ (x::<(Any\`url)>_|_)* ] -> [ <(book) (a)> x ]

We can perform many kinds of manipulations on the attributes by using the operators for records, namely `r\l` which deletes the field `l` in the record `r` whenever it is present, and `r1 + r2` which merges the records `r1` and `r2` by giving the priority to the fields in the latter. For instance

    transform bib with
         <(t) (a)> x  -> [ <(x) (a\isbn)> x ]

strips all the ISBN attributes.

    transform bib with
         <_ (a)> [(x::(Author|Title|Url)|_)*]  -> [ <book ({isbn="fake"}+a\year)> x ]

returns the bibliography in which all Paper elements are transformed into books; this is done by forgetting the Conference elements, by removing the year attributes and possibly adding a fake isbn attribute. Note that since record concatenation gives priority to the record on the righ handside, then whenever the record captured by `a` already contains an isbn attribute, this is preserved.

As an example to summarize what we said above, consider the the elements `table`, `td` and `tr` in XHTML. In transitional XHTML these elements can have an attribute `bgcolor` which is deprecated since in strict XHTML the background color must be specified by the `style` attribute. So for instance `<table bgcolor="#ffff00" style="font-family:Arial">`... must be rewritten as `<table style="bgcolor:#ffff00; font-family:Arial">`... to be XHTML strict compliant. Here is a function that does this transformation on a very simplified version of possibly nested tables containing strings.

    type Table = <table { bgcolor=?String; style=?String }>[ Tr+]
    type Tr = <tr { bgcolor=?String; style=?String }>[ Td+]
    type Td = <td { bgcolor=?String; style=?String }>[ Table* | PCDATA ]

    let strict ([Table*]->[Table*]; [Tr+]->[Tr+]; [Td+]->[Td+]; [PCDATA]->[PCDATA])
      x ->
        map x with
           <(t) (a& { bgcolor=c; style=s })> l
                -> <(t) (a\bgcolor+{style=(s@"; bgcolor:"@c)})>(strict l)
        |  <(t) (a& { bgcolor=c })> l
                -> <(t) (a\bgcolor+{style=("bgcolor:"@c)})>(strict l)
        |  <(t) (a)> l -> <(t) (a)>(strict l)
        |   c -> c

As an exercise the reader can try to rewrite the function `strict` so that the first three branches of the map are condensed into a unique branch.

## Handling optional attributes

The blend of type constructors and boolean combinators can be used to reduce verbosity in writing pattern matching. As an example we show how to handle tags with several optional attributes.

Consider the following fragment of code from site.cd from the CDuce distribution that we have changed a bit so that it stands alone:

    type Sample = <sample highlight=?"true"|"false">String

    let content (Sample -> String)
      | <sample highlight="false">_ -> "non-higlighted code"
      | <sample ..>_ -> "highlighted code"

The idea here is to use the highlight attribute to specify that certain pieces of `<sample>` should be emphasized. When the higlight attribute is missing, the default value of "true" is presumed.

But what if we have two optional attributes? The naive solution would be to write the four possible cases:

    type Sample = <sample lineno=?"true"|"false" highlight=?"true"|"false">String

    let content (Sample -> String)
      | <sample highlight="false" lineno="false">_ -> "lineno=false, highlight=false"
      | <sample lineno="false">_ -> "lineno=false, highlight=true"
      | <sample highlight="false">_ -> "lineno=true, highlight=false"
      | <sample ..>_ -> "lineno=true, highlight=true,"

The intended use for the `lineno` attribute is to tell us whether line numbers should be displayed alongside the sample code.
While this situation is still bearable it soon become unfeasible with more than two optional attributes. A much better way of handling this situation is to resort to intersection and default patterns as follows:

    let content (Sample -> String)
      | <sample ( ({ highlight = h ..} | (h := "true"))
                 &({ lineno = l ..} | (l := "true")) )>_
             -> ['lineno=' !l ', highlight=' !h]

The intersection pattern `&` makes both patterns to be matched against the record of attributes: each pattern checks the presence of a specific attribute (the other is ignored by matching it with `..`), if it is present it captures the attribute value in a given variables while if the attribute is absent the default sub-pattern is used to assign the variable a default value.

The use of patterns of the form `({ label1= x } | (x := v)) & { label2 = y }` is so common in handling optional fields (hence, XML attributes) that CDuce has a special syntax for this kind of patterns: `{ label1 = x else (x := v) ; label2 = y }`

## Recursive patterns

Recursive patterns use the same syntax as recursive types: `P where P1=p1 and ... and Pn=pn` with P, P1,..., Pn being variables ranging over pattern identifiers (i.e., identifiers starting by a capital letter). Recursive patterns allow one to express complex extraction of information from the matched value. For instance, consider the pattern `P where P = (x & Int, _) | (_, P)`; it extracts from a sequence the first element of type `Int` (recall that sequences are encoded with pairs). The order is important, because the pattern `P where P = (_, P) | (x & Int, _)` extracts the last element of type `Int`.

A pattern may also extract and reconstruct a subsequence, using the convention described before that when a capture variable appears on both sides of a pair pattern, the two values bound to this variable are paired together. For instance, `P where P = (x & Int, P) | (_, P) | (x := `nil)` extracts all the elements of type `Int` from a sequence (`x` is bound to the sequence containing them) and the pattern `P where P = (x & Int, (x & Int, _)) | (_, P)` extracts the first pair of consecutive integers.

## Compiling regular expression patterns

CONNECT WITH SECTION ON SEQUENCE PATTERNS WHEN WRITTEN

CDuce provides syntactic sugar for defining patterns working on sequences with regular expressions built from patterns, usual regular expression operators, and sequence capture variables of the form `x::R` (where R is a pattern regular expression).

Regular expression operators `*`, `+`, `?` are greedy in the sense that they try to match as many times as possible. Ungreedy versions `*?`, `+?` and `??` are also provided; the difference in the compilation scheme is just a matter of order in alternative patterns. For instance, `[_* (x & Int) _*]` is compiled to `P where P = (_,P) | (x & Int, _)` while `[_*? (x & Int) _*]` is compiled to `P where P = (x & Int, _) | (_,P)`.

Let us detail the compilation of an example with a sequence capture variable:

    [ _*?  d::(Echar+ '.' Echar+) ]

The first step is to propagate the variable down to simple patterns:

    [ _*?  (d::Echar)+ (d::'.') (d::Echar)+ ]

which is then compiled to the recursive pattern:

    P where P = (d & Echar, Q) | (_,P)
        and Q = (d & Echar, Q) | (d & '.', (d & Echar, R))
        and R = (d & Echar, R) | (d & `nil)

The `(d & `nil)` pattern above has a double purpose: it checks that the end of the matched sequence has been reached, and it binds `d` to ``nil`, to create the end of the new sequence.

Note the difference between `[ x&Int ]` and `[ x::Int ]`. Both patterns accept sequences formed of a single integer `i`, but the first one binds `i` to `x`, whereas the second one binds to `x` the sequence `[i]`.

A mix of greedy and ungreedy operators with the first match policy of alternate patterns allows the definition of powerful extractions. For instance, one can define a function that for a given person returns the first work phone number if any, otherwise the last e-mail, if any, otherwise any telephone number, or the string `"no contact"`:

    let preferred_contact(Person -> String)
       <_>[  _  _  ( _*? <tel kind="work">x)  |  (_* <email>x) |  <tel ..>x ] -> x
      |  _ -> "no contact"

(note that `<tel ..>x` does not need to be preceded by any wildcard pattern as it is the only possible remaining case).

Site map

CDuce: documentation: Tutorial: Patterns

Overloading Error messages and Warnings