<?xml version="1.0" encoding="ISO-8859-1" standalone="yes"?>
<page name="tutorial_patterns">

<title>Patterns</title>
<banner>Patterns</banner>

<left>
<boxes-toc/>
<p>
You can cut and paste the code on this page and 
test it on the <a href="http://reglisse.ens.fr/cgi-bin/cduce">online interpreter</a>.
</p>
</left>

<box title="Key concepts" link="key">

<b style="color:#FF0080">TO BE DONE</b>

</box>

<box title="Pair and Record Patterns" link="record">

<b style="color:#FF0080">TO BE DONE</b>

</box>

<box title="Sequence patterns" link="seq">

<b style="color:#FF0080">TO BE DONE</b>

</box>

<box title="XML elements and attributes" link="xml">
<p>
Up to now we used for XML elements (and their types) an abbreviated notation
as for <code>&lt;table align="center" valign="top">[</code><i>some_content</i><code>]</code>. Actually, the precise syntax of XML elements is
</p>
<sample><![CDATA[
<(%%expr1%%) (%%expr2%%)>%%expr3%%
]]></sample>
<p>
where <code>%%expr1%%</code>, <code>%%expr2%%</code>, and<code>%%expr3%%</code> are generic
expressions. The same holds true for record patterns, but where
the generic expressions are replaced by generic patterns (that is, <code>&lt;(%%p1%%) (%%p2%%)>%%p3%%</code>). It is important
to notice that the parentheses (in red) <code>&lt;{{(}}%%expr1%%{{)}}
{{(}}%%expr2%%{{)}}>%%expr3%%</code> are part of the syntax.<br/>
 
Even if <code>%%expr1%%</code>, <code>%%expr2%%</code>, and
<code>%%expr3%%</code> may be any expression, in practice they mostly occur in a very
precise form. In particular, <code>%%expr1%%</code> is an <a
href="manual_types_patterns.html#basictag">atom</a>, <code>%%expr2%%</code> is a
<a href="manual_types_patterns.html#record">record value</a>, while
<code>%%expr3%%</code> 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 <code>{{(` )}}</code>
when <code>%%expr1%%</code> is an atom, and to omit the surrounding <code>{{{ }
}}</code> and the infix semicolons <code>{{;}}</code>  when
<code>%%expr2%%</code> is a record value. This is why we can write
<code>&lt;table align="center" valign="top">[ </code>...<code> ]</code>, rather than
<code>&lt;$$(`$$table$$)$$ $$({$$align="center"$$;$$ valign="top"$$})$$
>[ </code>...<code> ]</code>
</p>

<p> 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:
</p>
<sample><![CDATA[
<(%%p1%%) (%%p2%%)>%%p3%%
]]></sample>
<p>
and the same abbreviations as for expressions apply. In particular, this means
that, say, the pattern <code>&lt;t (a)>_</code> stands for <code>&lt;(`t)
(a)>_</code>. Therefore while <code>&lt;t (a)>_</code> matches all the elements
of tag <code>t</code> (and captures in the variable <code>a</code> the
attributes), the pattern <code>&lt;(t) (a)>_</code> matches all XML elements
(whatever their tag is) and captures their tag in the variable <code>t</code>
(and their attributes in <code>a</code>). Another point to notice is that
<code>&lt;t>_</code> stands for <code>&lt;t ({})>_</code> (more precisely, for
<code>&lt;(`t) ({})>_</code>). Since <code>{}</code> is the <i>closed</i> empty
record type, then it matches only the empty record. Therefore <code>&lt;t>_</code>
matches all elements of tag <code>t</code> that have no attibute. We have seen at the beginning of this tutorial that in order to match all element of tag <code>t</code> independently from whether they have attributes or not, we have to use the pattern <code>&lt;t ..>_</code> (which stands for <code>&lt;(`t) ({..})>_</code>).
</p>
<p>
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:
</p>
<sample><![CDATA[
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 ]
]]></sample>
<p>
Let <code>bib</code> be of type <code>Biblio</code> then
</p>
<sample><![CDATA[
transform bib with
     <book (a)> [ (x::(Any\Url)|_)* ] -> [ <book (a)> x ]
]]></sample>
<p>
returns the list of all books without their Url element (if any).
</p>
<sample><![CDATA[
transform bib with
     <(book) (a)> [ (x::(Any\Url)|_)* ] -> [ <(book) (a)> x ]
]]></sample>
<p>
returns the bibliography in which all entries (either books or papers) no longer
have their Url elements (<code>book</code> is now a capture variable). Equivalently we could have
pushed the difference on tags:
</p>
<sample><![CDATA[
transform bib with
     <(book) (a)> [ (x::<(Any\`url)>_|_)* ] -> [ <(book) (a)> x ]
]]></sample>
<p>
We can perform many kinds of manipulations on the attributes by
using the <a href="manual_expressions.html#record">operators for records</a>,
namely <code>%%r%%\%%l%%</code> which deletes the field <code>%%l%%</code>
in the record <code>%%r%%</code> whenever it is present, and <code>%%r1%% +
%%r2%%</code> which merges the records <code>%%r1%%</code> and
<code>%%r2%%</code> by giving the priority to the fields in the latter. For
instance
</p>
<sample><![CDATA[
transform bib with
     <(t) (a)> x  -> [ <(x) (a\isbn)> x ]
]]></sample>
<p>
strips all the ISBN attributes.
</p>
<sample><![CDATA[
transform bib with
     <_ (a)> [(x::(Author|Title|Url)|_)*]  -> [ <book ({isbn="fake"}+a\year)> x ]
]]></sample>
<p>
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
<code>a</code> already contains an isbn attribute, this is preserved.
</p>

<p>
As an example to summarize what we said above, consider the the elements
<code>table</code>, <code>td</code> and <code>tr</code> in XHTML. In
transitional XHTML these elements can have an attribute <code>bgcolor</code>
which is deprecated since in strict XHTML the background color must be specified
by the <code>style</code> attribute. So for instance <code>&lt;table
bgcolor="#ffff00" style="font-family:Arial"></code>...
must be rewritten as <code>&lt;table style="bgcolor:#ffff00;
font-family:Arial"></code>... to be XHTML strict compliant. Here is a function
that does this transformation on a very simplified version of possibly nested
tables containing strings.
</p>
<sample><![CDATA[
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  
]]></sample> 
<p>
As an exercise the reader can try to rewrite the function <code>strict</code> so that the first three branches of the map are condensed into a unique branch. 
</p>
</box>


<box title="Handling optional attributes" link="optatrr">
<p>
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.
</p>
<p>
Consider the following fragment of code from site.cd from the CDuce
distribution that we have changed a bit so that it stands alone:
</p>
<sample><![CDATA[
type Sample = <sample highlight=?"true"|"false">String

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

]]></sample> 
<p>
The idea here is to use the highlight attribute to specify that
certain pieces of <code>&lt;sample></code> should be emphasized. When the higlight
attribute is missing, the default value of "true" is presumed.
</p>
<p>
But what if we have two optional attributes? The naive solution would be
to write the
<i>four</i> possible cases:
</p>
<sample><![CDATA[
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,"

]]></sample> 
<p>
The intended use for the <code>lineno</code> attribute is to tell us whether line
numbers should be displayed alongside the sample code.
<br/>
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:
</p>
<sample><![CDATA[
let content (Sample -> String)
  | <sample ( ({ highlight = h ..} | (h {{:=}} "true"))
             {{&}}({ lineno = l ..} | (l {{:=}} "true")) )>_
         -> ['lineno=' !l ', highlight=' !h]

]]></sample> 
<p>
The intersection pattern <code>&amp;</code> 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 <code>..</code>), 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.
</p>
<p>
The use of patterns of the form <code>
({ label1= x } | (x := %%v%%)) &amp; { label2 = y }</code> is so common in handling 
optional fields (hence, XML attributes) that  CDuce has a special syntax for this 
kind of patterns:  <code>
{ label1 = x else (x := %%v%%) ; label2 = y }</code>
</p>
</box>



<box title="Recursive patterns" link="recpat">
<p>
Recursive patterns use the same syntax as recursive types:
<code>%%P%% where %%P1%%=%%p1%% and ... and %%Pn%%=%%pn%%</code> with <i>P, P1,..., Pn</i>
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
<code>P where P = (x &amp; Int, _) | (_, P)</code>; it extracts from a sequence the first
element of type <code>Int</code> (recall that sequences are
encoded with pairs). The order
is important, because
the pattern <code>P where P =  (_, P) | (x &amp; Int, _)</code>
extracts the <i>last</i> element of type <code>Int</code>. 
</p>
<p>
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, <code>P where P = (x &amp; Int, P) | (_, P) | (x := `nil)</code>
extracts all the elements of type <code>Int</code> from a sequence (<code>x</code>
is bound to the sequence containing them)
and the pattern <code>P where P = (x &amp; Int, (x &amp; Int, _)) | (_, P)</code>
extracts the first pair of consecutive integers.
</p>
</box>

<box title="Compiling regular expression patterns" link="pre">

<b style="color:#FF0080">CONNECT WITH SECTION ON SEQUENCE PATTERNS WHEN WRITTEN</b>

<p>
CDuce provides syntactic sugar for defining patterns working on
sequences with regular expressions built from patterns, usual regular
expression operators, and <i>sequence capture variables</i> of the form <code>x::%%R%%</code> 
(where <i>R</i> is a pattern regular expression).
</p>
<p>
Regular expression operators <code>*</code>, <code>+</code>, <code>?</code> are 
<i>greedy</i> in the sense that they try to match as many times as possible.
Ungreedy versions <code>*?</code>, <code>+?</code> and <code>??</code>
are also provided; the difference in the compilation scheme
is just a matter of order in alternative patterns.
For instance, <code>[_* (x &amp; Int) _*]</code> is compiled
to <code>P where P = (_,P) | (x &amp; Int, _)</code>
while <code>[_*? (x &amp; Int) _*]</code> is compiled
to <code>P where P = (x &amp; Int, _) | (_,P)</code>.
</p>
<p>
Let us detail the compilation of an example with a sequence capture variable:
</p>
<sample><![CDATA[
[ _*?  d::(Echar+ '.' Echar+) ]
]]></sample> 
<p>
The first step is
to propagate the variable down to simple patterns:
</p>
<sample><![CDATA[
[ _*?  (d::Echar)+ (d::'.') (d::Echar)+ ]
]]></sample> 
<p> 
which is then
compiled to the recursive pattern:
</p>
<sample><![CDATA[
P where P = (d & Echar, Q) | (_,P)
    and Q = (d & Echar, Q) | (d & '.', (d & Echar, R))
    and R = (d & Echar, R) | (d & `nil)
]]></sample>
<p>
The <code>(d &amp; `nil)</code>
pattern above has a double purpose: it checks that the end
of the matched sequence has been reached, and it binds <code>d</code> to
<code>`nil</code>, to create the end of the new sequence.
</p>
<p>
Note the difference between <code>[ x&amp;Int ]</code>
and <code>[ x::Int ]</code>. Both patterns accept sequences
formed of a single integer <code>{{i}}</code>, but the first one binds  <code>{{i}}</code> to <code>x</code>,
whereas the second one binds to <code>x</code> the sequence <code>[{{i}}]</code>.
</p>
<p>
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 <code>"no contact"</code>:
</p>
<sample><![CDATA[
let preferred_contact(Person -> String)
   <_>[  _  _  ( _*? <tel kind="work">x)  |  (_* <email>x) |  <tel ..>x ] -> x
  |  _ -> "no contact"
]]></sample>
<p>
(note that <code>&lt;tel ..>x</code> does not need to be preceded by any wildcard pattern as it is
the only possible remaining case).
</p>
</box>

</page>