editor, reviewer
33
edits
Changes
Jump to navigation
Jump to search
Created page with "=Function Items= Probably the most important new feature in XQuery 3.0 are ''function items'', i. e. items that act as functions, but can also be passed to and from other functi..."
=Function Items=
Probably the most important new feature in XQuery 3.0 are ''function items'', i. e. items that act as functions, but can also be passed to and from other functions and expressions, making functions ''first-class citizens'' of the language.
The [[XQuery_3.0#Function_Items|XQuery 3.0]] page goes into details on how function items can be obtained.
== Function Types ==
Like every XQuery item, function items have a ''sequence type''. It can be
used to specify the ''arity'' (number of arguments the function takes) and
the argument and result types.
The most general function type is <code>function(*)</code>. It's the type of all
function items. The following query for example goes through a list of XQuery
items and, if it is a function item, prints its arity:
<pre class="brush:xquery">
for $item in (1, 'foo', fn:concat#3, function($a) { 42 * $a })
where $item instance of function(*)
return fn:function-arity($item)
</pre>
''Result:'' <code>3 1</code>
The notation for specifying argument and return types is quite intuitive, as it
closely resembles the function declaration. The XQuery function
<pre class="brush:xquery">
declare function local:char-at(
$str as xs:string,
$pos as xs:integer
) as xs:string {
fn:substring($str, $pos, 1)
};
</pre>
for example has the type <code>function(xs:string, xs:integer) as xs:string</code>. It isn't possible to specify only the argument and not the result
type or the other way round. A good place-holder to use when no restriction
is wanted is <code>item()*</code>, as it matches any XQuery value.
Function types can also be nested. As an example we take <code>local:on-sequences</code>, which takes a function defined on single items and makes it work on sequences as well:
<pre class="brush:xquery">
declare function local:on-sequences(
$f as function(item()) as item()*
) as function(item()*) as item()* {
fn:map($f, ?)
};
</pre>
We'll see later how <code>fn:map(...)</code> works. The type of <code>local:on-sequences(...)</code> on the other hand is easily constructed, if a bit long:
<code>function(function(item()) as item()*) as function(item()*) as item()*</code>.
=Higher-Order Functions=
A ''higher-order function'' is a function that takes other functions as arguments and/or returns them as results. <code>fn:map</code> and <code>local:on-sequences</code> from the last chapter are nice examples.
With the help of higher-order functions, one can extract common patterns of
''behaviour'' and abstract them into a library function.
== Higher-Order Functions on Sequences ==
Some usage patterns on sequences are so common that the higher-order functions
describing them are in the XQuery standard libraries. They are listed here, together
with their possible XQuery implementation and some motivating examples.
===fn:map($f, $seq)===
{|
|-
| valign='top' width='90' | '''Signatures'''
|<code><b>fn:map</b>($f as function(item()) as item()*, $seq as item()*) as item()*</code><br />
|-
| valign='top' | '''Summary'''
|Applies the function item <code>$f</code> to every element of the sequence <code>$seq</code> and returns all of the results as a sequence.
|-
| valign='top' | '''XQuery'''
|<pre class="brush:xquery">
declare function local:map(
$f as function(item()) as item()*,
$seq as item()*
) as item()* {
for $x in $seq
return $f($seq)
};
</pre>
|-
| valign='top' | '''Examples'''
|
<ul><li>Squaring all numbers from 1 to 10:
<pre class="brush:xquery">
fn:map(math:pow(?, 2), 1 to 10)
</pre>
''Result:'' <code>1 4 9 16 25 36 49 64 81 100</code>
</li>
<li>Applying a list of functions to a string:
<pre class="brush:xquery">
let $fs := (
fn:upper-case#1,
fn:substring(?, 4),
fn:string-length#1
)
return fn:map(function($f) { $f('foobar') }, $fs)
</pre>
''Result:'' <code>FOOBAR bar 6</code>
</li></ul>
|}
===fn:filter($pred, $seq)===
{|
|-
| valign='top' width='90' | '''Signatures'''
|<code><b>fn:filter</b>($pred as function(item()) as xs:boolean, $seq as item()*) as item()*</code><br />
|-
| valign='top' | '''Summary'''
|Applies the boolean predicate <code>$pred</code> to all elements of the sequence <code>$seq</code>, returning those for which it returns <code>true()</code>.
|-
| valign='top' | '''XQuery'''
|<pre class="brush:xquery">
declare function local:filter(
$pred as function(item()) as xs:boolean,
$seq as item()*
) as item()* {
$seq[$pred(.)]
};
</pre>
|-
| valign='top' | '''Examples'''
|<ul><li>All even integers until 10:
<pre class="brush:xquery">
fn:filter(function($x) { $x mod 2 eq 0 }, 1 to 10)
</pre>
''Result:'' <code>2 4 6 8 10</code>
</li>
<li>Strings that start with an upper-case letter:
<pre class="brush:xquery">
let $first-upper := function($str) {
let $first := fn:substring($str, 1, 1)
return $first eq fn:upper-case($first)
}
return fn:filter($first-upper, ('FooBar', 'foo', 'BAR'))
</pre>
''Result:'' <code>FooBar BAR</code>
</li>
<li>Inefficient prime number generator:
<pre class="brush:xquery">
let $is-prime := function($x) {
$x gt 1 and
(every $y in 2 to ($x - 1) satisfies $x mod $y ne 0)
}
return filter($is-prime, 1 to 20)
</pre>
''Result:'' <code>2 3 5 7 11 13 17 19</code>
</li></ul>
|-
| valign='top' | '''Note'''
|<code>fn:filter</code> can be easily implemented with <code>fn:map</code>:
<pre class="brush:xquery">
declare function local:filter($pred, $seq) {
map(
function($x) {
if($pred($x)) then $x else ()
},
$seq
)
};
</pre>
|}
===fn:map-pairs($f, $seq1, $seq2)===
{|
|-
| valign='top' width='90' | '''Signatures'''
|<code><b>fn:map-pairs</b>($f as function(item(), item()) as item()*, $seq1 as item()*, $seq2 as item()*) as item()*</code><br />
|-
| valign='top' | '''Summary'''
|''zips'' the elements from the two sequences <code>$seq1</code> and <code>$seq2</code> together with the function <code>$f</code>. It stops after the shorter sequence ends.
|-
| valign='top' | '''XQuery'''
|<pre class="brush:xquery">
declare function local:map-pairs(
$f as function(item(), item()) as item()*,
$seq1 as item()*,
$seq2 as item()*
) as item()* {
for $pos in 1 to min(length($seq1), length($seq2))
return $f($seq1[$pos], $seq2[$pos])
};
</pre>
|-
| valign='top' | '''Examples'''
|<ul><li>Adding one to the numbers at odd positions:
<pre class="brush:xquery">
fn:map-pairs(
function($a, $b) { $a + $b },
fn:map(function($x) { $x mod 2 }, 1 to 10),
(1, 1, 1, 1, 1)
)
</pre>
''Result:'' <code>2 1 2 1 2</code>
</li>
<li>Line numbering:
<pre class="brush:xquery">
let $number-lines := function($str) {
fn:string-join(
fn:map-pairs(
concat(?, ': ', ?),
1 to 1000,
tokenize($str, '\r?\n|\r')
),
'&#xa;'
)
}
return $number-lines(
'hello world,
how are you?'
)
</pre>
''Result:''
<pre>
1: hello world,
2: how are you?
</pre>
</li>
<li>Checking if a sequence is sorted:
<pre class="brush:xquery">
let $is-sorted := function($seq) {
every $b in
fn:map-pairs(
function($a, $b) { $a le $b },
$seq,
fn:tail($seq)
)
satisfies $b
}
return (
$is-sorted(1 to 10),
$is-sorted((1, 2, 42, 4, 5))
)
</pre>
''Result:'' <code>true false</code>
</li></ul>
|}
== Folds ==
A ''fold'', also called ''reduce'' or ''accumulate'' in other languages, is a very
basic higher-order function on sequences. It starts from a seed value and incrementally
builds up a result, consuming one element from the sequence at a time and combining it with
the aggregate with a user-defined function.
Folds are one solution to the problem of not having ''state'' in functional programs.
Solving a problem in ''imperative'' programming languages often means repeatedly updating
the value of variables, which isn't allowed in functional languages.
Calculating the ''product'' of a sequence of integers for example is easy in <code>Java</code>:
<pre class="brush:java">
public int product(int[] seq) {
int result = 1;
for(int i : seq) {
result = result * i;
}
return result;
}
</pre>
Nice and efficient implementations using folds will be given below.
The ''linear'' folds on sequences come in two flavours. They differ in the direction in which they traverse the sequence:
===fn:fold-left($f, $seed, $seq)===
{|
|-
| valign='top' width='90' | '''Signatures'''
|<code><b>fn:fold-left</b>($f as function(item()*, item()) as item()*, $seed as item()*, $seq as item()*) as item()*</code><br />
|-
| valign='top' | '''Summary'''
|The ''left fold'' traverses the sequence from the left.
The query <code>fn:fold-left($f, 0, 1 to 5)</code> for example would be evaluated as:
<pre class="brush:xquery">
$f($f($f($f($f(0, 1), 2), 3), 4), 5)
</pre>
|-
| valign='top' | '''XQuery'''
|As folds are more general that ''FLWOR'' expressions, the implementation isn't as concise as the former ones:
<pre class="brush:xquery">
declare function local:fold-left(
$f as function(item()*, item()) as item()*,
$seed as item()*,
$seq as item()*
) as item()* {
if(empty($seq)) then $seed
else local:fold-left(
$f,
$f($seed, fn:head($seq)),
fn:tail($seq)
)
};
</pre>
|-
| valign='top' | '''Examples'''
|<ul><li>Product of a sequence of integers:
<pre class="brush:xquery">
let $product := fn:fold-left(
function($result, $i) { $result * $i },
1,
?
)
return $product(1 to 5)
</pre>
''Result:'' <code>120</code>
</li>
<li>Illustrating the evaluation order:
<pre class="brush:xquery">
fn:fold-left(
concat('$f(', ?, ', ', ?, ')'),
'$seed',
1 to 5
)
</pre>
''Result:'' <code>$f($f($f($f($f($seed, 1), 2), 3), 4), 5)</code>
</li>
<li>Building a decimal number from digits:
<pre class="brush:xquery">
let $from-digits := fold-left(
function($n, $d) { 10 * $n + $d },
0,
?
)
return (
$from-digits(1 to 5),
$from-digits((4, 2))
)
</pre>
''Result:'' <code>12345 42</code>
</li></ul>
|}
===fn:fold-right($f, $seed, $seq)===
{|
|-
| valign='top' width='90' | '''Signatures'''
|<code><b>fn:fold-right</b>($f as function(item(), item()*) as item()*, $seed as item()*, $seq as item()*) as item()*</code><br />
|-
| valign='top' | '''Summary'''
|The ''right fold'' <code>fn:fold-right($f, $seed, $seq)</code> traverses the from the right.
The query <code>fn:fold-right($f, 0, 1 to 5)</code> for example would be evaluated as:
<pre class="brush:xquery">
$f(1, $f(2, $f(3, $f(4, $f(5, 0)))))
</pre>
|-
| valign='top' | '''XQuery'''
|<pre class="brush:xquery">
declare function local:fold-right(
$f as function(item(), item()*) as item()*,
$seed as item()*,
$seq as item()*
) as item()* {
if(empty($seq)) then $seed
else $f(
fn:head($seq),
local:fold-right($f, $seed, tail($seq))
)
};
</pre>
Note that the order of the arguments of <code>$f</code> are inverted compared to that in <code>fn:fold-left(...)</code>.
|-
| valign='top' | '''Examples'''
|<ul><li>Product of a sequence of integers:
<pre class="brush:xquery">
let $product := fn:fold-right(
function($i, $result) { $result * $i },
1,
?
)
return $product(1 to 5)
</pre>
''Result:'' <code>120</code>
</li>
<li>Illustrating the evaluation order:
<pre class="brush:xquery">
fn:fold-right(
concat('$f(', ?, ', ', ?, ')'),
'$seed',
1 to 5
)
</pre>
''Result:'' <code>$f(1, $f(2, $f(3, $f(4, $f(5, $seed)))))</code>
</li>
<li>Reversing a sequence of items:
<pre class="brush:xquery">
let $reverse := fn:fold-right(
function($item, $rev) {
$rev, $item
},
(),
?
)
return $reverse(1 to 10)
</pre>
''Result:'' <code>10 9 8 7 6 5 4 3 2 1</code>
</li></ul>
|}
Probably the most important new feature in XQuery 3.0 are ''function items'', i. e. items that act as functions, but can also be passed to and from other functions and expressions, making functions ''first-class citizens'' of the language.
The [[XQuery_3.0#Function_Items|XQuery 3.0]] page goes into details on how function items can be obtained.
== Function Types ==
Like every XQuery item, function items have a ''sequence type''. It can be
used to specify the ''arity'' (number of arguments the function takes) and
the argument and result types.
The most general function type is <code>function(*)</code>. It's the type of all
function items. The following query for example goes through a list of XQuery
items and, if it is a function item, prints its arity:
<pre class="brush:xquery">
for $item in (1, 'foo', fn:concat#3, function($a) { 42 * $a })
where $item instance of function(*)
return fn:function-arity($item)
</pre>
''Result:'' <code>3 1</code>
The notation for specifying argument and return types is quite intuitive, as it
closely resembles the function declaration. The XQuery function
<pre class="brush:xquery">
declare function local:char-at(
$str as xs:string,
$pos as xs:integer
) as xs:string {
fn:substring($str, $pos, 1)
};
</pre>
for example has the type <code>function(xs:string, xs:integer) as xs:string</code>. It isn't possible to specify only the argument and not the result
type or the other way round. A good place-holder to use when no restriction
is wanted is <code>item()*</code>, as it matches any XQuery value.
Function types can also be nested. As an example we take <code>local:on-sequences</code>, which takes a function defined on single items and makes it work on sequences as well:
<pre class="brush:xquery">
declare function local:on-sequences(
$f as function(item()) as item()*
) as function(item()*) as item()* {
fn:map($f, ?)
};
</pre>
We'll see later how <code>fn:map(...)</code> works. The type of <code>local:on-sequences(...)</code> on the other hand is easily constructed, if a bit long:
<code>function(function(item()) as item()*) as function(item()*) as item()*</code>.
=Higher-Order Functions=
A ''higher-order function'' is a function that takes other functions as arguments and/or returns them as results. <code>fn:map</code> and <code>local:on-sequences</code> from the last chapter are nice examples.
With the help of higher-order functions, one can extract common patterns of
''behaviour'' and abstract them into a library function.
== Higher-Order Functions on Sequences ==
Some usage patterns on sequences are so common that the higher-order functions
describing them are in the XQuery standard libraries. They are listed here, together
with their possible XQuery implementation and some motivating examples.
===fn:map($f, $seq)===
{|
|-
| valign='top' width='90' | '''Signatures'''
|<code><b>fn:map</b>($f as function(item()) as item()*, $seq as item()*) as item()*</code><br />
|-
| valign='top' | '''Summary'''
|Applies the function item <code>$f</code> to every element of the sequence <code>$seq</code> and returns all of the results as a sequence.
|-
| valign='top' | '''XQuery'''
|<pre class="brush:xquery">
declare function local:map(
$f as function(item()) as item()*,
$seq as item()*
) as item()* {
for $x in $seq
return $f($seq)
};
</pre>
|-
| valign='top' | '''Examples'''
|
<ul><li>Squaring all numbers from 1 to 10:
<pre class="brush:xquery">
fn:map(math:pow(?, 2), 1 to 10)
</pre>
''Result:'' <code>1 4 9 16 25 36 49 64 81 100</code>
</li>
<li>Applying a list of functions to a string:
<pre class="brush:xquery">
let $fs := (
fn:upper-case#1,
fn:substring(?, 4),
fn:string-length#1
)
return fn:map(function($f) { $f('foobar') }, $fs)
</pre>
''Result:'' <code>FOOBAR bar 6</code>
</li></ul>
|}
===fn:filter($pred, $seq)===
{|
|-
| valign='top' width='90' | '''Signatures'''
|<code><b>fn:filter</b>($pred as function(item()) as xs:boolean, $seq as item()*) as item()*</code><br />
|-
| valign='top' | '''Summary'''
|Applies the boolean predicate <code>$pred</code> to all elements of the sequence <code>$seq</code>, returning those for which it returns <code>true()</code>.
|-
| valign='top' | '''XQuery'''
|<pre class="brush:xquery">
declare function local:filter(
$pred as function(item()) as xs:boolean,
$seq as item()*
) as item()* {
$seq[$pred(.)]
};
</pre>
|-
| valign='top' | '''Examples'''
|<ul><li>All even integers until 10:
<pre class="brush:xquery">
fn:filter(function($x) { $x mod 2 eq 0 }, 1 to 10)
</pre>
''Result:'' <code>2 4 6 8 10</code>
</li>
<li>Strings that start with an upper-case letter:
<pre class="brush:xquery">
let $first-upper := function($str) {
let $first := fn:substring($str, 1, 1)
return $first eq fn:upper-case($first)
}
return fn:filter($first-upper, ('FooBar', 'foo', 'BAR'))
</pre>
''Result:'' <code>FooBar BAR</code>
</li>
<li>Inefficient prime number generator:
<pre class="brush:xquery">
let $is-prime := function($x) {
$x gt 1 and
(every $y in 2 to ($x - 1) satisfies $x mod $y ne 0)
}
return filter($is-prime, 1 to 20)
</pre>
''Result:'' <code>2 3 5 7 11 13 17 19</code>
</li></ul>
|-
| valign='top' | '''Note'''
|<code>fn:filter</code> can be easily implemented with <code>fn:map</code>:
<pre class="brush:xquery">
declare function local:filter($pred, $seq) {
map(
function($x) {
if($pred($x)) then $x else ()
},
$seq
)
};
</pre>
|}
===fn:map-pairs($f, $seq1, $seq2)===
{|
|-
| valign='top' width='90' | '''Signatures'''
|<code><b>fn:map-pairs</b>($f as function(item(), item()) as item()*, $seq1 as item()*, $seq2 as item()*) as item()*</code><br />
|-
| valign='top' | '''Summary'''
|''zips'' the elements from the two sequences <code>$seq1</code> and <code>$seq2</code> together with the function <code>$f</code>. It stops after the shorter sequence ends.
|-
| valign='top' | '''XQuery'''
|<pre class="brush:xquery">
declare function local:map-pairs(
$f as function(item(), item()) as item()*,
$seq1 as item()*,
$seq2 as item()*
) as item()* {
for $pos in 1 to min(length($seq1), length($seq2))
return $f($seq1[$pos], $seq2[$pos])
};
</pre>
|-
| valign='top' | '''Examples'''
|<ul><li>Adding one to the numbers at odd positions:
<pre class="brush:xquery">
fn:map-pairs(
function($a, $b) { $a + $b },
fn:map(function($x) { $x mod 2 }, 1 to 10),
(1, 1, 1, 1, 1)
)
</pre>
''Result:'' <code>2 1 2 1 2</code>
</li>
<li>Line numbering:
<pre class="brush:xquery">
let $number-lines := function($str) {
fn:string-join(
fn:map-pairs(
concat(?, ': ', ?),
1 to 1000,
tokenize($str, '\r?\n|\r')
),
'&#xa;'
)
}
return $number-lines(
'hello world,
how are you?'
)
</pre>
''Result:''
<pre>
1: hello world,
2: how are you?
</pre>
</li>
<li>Checking if a sequence is sorted:
<pre class="brush:xquery">
let $is-sorted := function($seq) {
every $b in
fn:map-pairs(
function($a, $b) { $a le $b },
$seq,
fn:tail($seq)
)
satisfies $b
}
return (
$is-sorted(1 to 10),
$is-sorted((1, 2, 42, 4, 5))
)
</pre>
''Result:'' <code>true false</code>
</li></ul>
|}
== Folds ==
A ''fold'', also called ''reduce'' or ''accumulate'' in other languages, is a very
basic higher-order function on sequences. It starts from a seed value and incrementally
builds up a result, consuming one element from the sequence at a time and combining it with
the aggregate with a user-defined function.
Folds are one solution to the problem of not having ''state'' in functional programs.
Solving a problem in ''imperative'' programming languages often means repeatedly updating
the value of variables, which isn't allowed in functional languages.
Calculating the ''product'' of a sequence of integers for example is easy in <code>Java</code>:
<pre class="brush:java">
public int product(int[] seq) {
int result = 1;
for(int i : seq) {
result = result * i;
}
return result;
}
</pre>
Nice and efficient implementations using folds will be given below.
The ''linear'' folds on sequences come in two flavours. They differ in the direction in which they traverse the sequence:
===fn:fold-left($f, $seed, $seq)===
{|
|-
| valign='top' width='90' | '''Signatures'''
|<code><b>fn:fold-left</b>($f as function(item()*, item()) as item()*, $seed as item()*, $seq as item()*) as item()*</code><br />
|-
| valign='top' | '''Summary'''
|The ''left fold'' traverses the sequence from the left.
The query <code>fn:fold-left($f, 0, 1 to 5)</code> for example would be evaluated as:
<pre class="brush:xquery">
$f($f($f($f($f(0, 1), 2), 3), 4), 5)
</pre>
|-
| valign='top' | '''XQuery'''
|As folds are more general that ''FLWOR'' expressions, the implementation isn't as concise as the former ones:
<pre class="brush:xquery">
declare function local:fold-left(
$f as function(item()*, item()) as item()*,
$seed as item()*,
$seq as item()*
) as item()* {
if(empty($seq)) then $seed
else local:fold-left(
$f,
$f($seed, fn:head($seq)),
fn:tail($seq)
)
};
</pre>
|-
| valign='top' | '''Examples'''
|<ul><li>Product of a sequence of integers:
<pre class="brush:xquery">
let $product := fn:fold-left(
function($result, $i) { $result * $i },
1,
?
)
return $product(1 to 5)
</pre>
''Result:'' <code>120</code>
</li>
<li>Illustrating the evaluation order:
<pre class="brush:xquery">
fn:fold-left(
concat('$f(', ?, ', ', ?, ')'),
'$seed',
1 to 5
)
</pre>
''Result:'' <code>$f($f($f($f($f($seed, 1), 2), 3), 4), 5)</code>
</li>
<li>Building a decimal number from digits:
<pre class="brush:xquery">
let $from-digits := fold-left(
function($n, $d) { 10 * $n + $d },
0,
?
)
return (
$from-digits(1 to 5),
$from-digits((4, 2))
)
</pre>
''Result:'' <code>12345 42</code>
</li></ul>
|}
===fn:fold-right($f, $seed, $seq)===
{|
|-
| valign='top' width='90' | '''Signatures'''
|<code><b>fn:fold-right</b>($f as function(item(), item()*) as item()*, $seed as item()*, $seq as item()*) as item()*</code><br />
|-
| valign='top' | '''Summary'''
|The ''right fold'' <code>fn:fold-right($f, $seed, $seq)</code> traverses the from the right.
The query <code>fn:fold-right($f, 0, 1 to 5)</code> for example would be evaluated as:
<pre class="brush:xquery">
$f(1, $f(2, $f(3, $f(4, $f(5, 0)))))
</pre>
|-
| valign='top' | '''XQuery'''
|<pre class="brush:xquery">
declare function local:fold-right(
$f as function(item(), item()*) as item()*,
$seed as item()*,
$seq as item()*
) as item()* {
if(empty($seq)) then $seed
else $f(
fn:head($seq),
local:fold-right($f, $seed, tail($seq))
)
};
</pre>
Note that the order of the arguments of <code>$f</code> are inverted compared to that in <code>fn:fold-left(...)</code>.
|-
| valign='top' | '''Examples'''
|<ul><li>Product of a sequence of integers:
<pre class="brush:xquery">
let $product := fn:fold-right(
function($i, $result) { $result * $i },
1,
?
)
return $product(1 to 5)
</pre>
''Result:'' <code>120</code>
</li>
<li>Illustrating the evaluation order:
<pre class="brush:xquery">
fn:fold-right(
concat('$f(', ?, ', ', ?, ')'),
'$seed',
1 to 5
)
</pre>
''Result:'' <code>$f(1, $f(2, $f(3, $f(4, $f(5, $seed)))))</code>
</li>
<li>Reversing a sequence of items:
<pre class="brush:xquery">
let $reverse := fn:fold-right(
function($item, $rev) {
$rev, $item
},
(),
?
)
return $reverse(1 to 10)
</pre>
''Result:'' <code>10 9 8 7 6 5 4 3 2 1</code>
</li></ul>
|}
