Difference between revisions of "Higher-Order Functions"

From BaseX Documentation
Jump to navigation Jump to search
m (Text replacement - "syntaxhighlight" to "pre")
 
(31 intermediate revisions by 3 users not shown)
Line 1: Line 1:
This page talks about ''higher-order functions'' introduced with [[XQuery 3.0]]. The BaseX-specific <code>hof</code> module containing some more very usful functions can be found at [[Higher-Order Functions Module]].
+
This page present some ''higher-order functions'' of the XQuery specification. The BaseX-specific [[Higher-Order Functions Module]] contains some additional useful functions.
  
 
=Function Items=
 
=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.
+
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. This feature makes 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.
 
 
The [[XQuery_3.0#Function_Items|XQuery 3.0]] page goes into details on how function items can be obtained.
 
  
 
== Function Types ==
 
== Function Types ==
  
Like every XQuery item, function items have a ''sequence type''. It can be
+
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.
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
+
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:
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">
+
<pre lang='xquery'>
 
for $item in (1, 'foo', fn:concat#3, function($a) { 42 * $a })
 
for $item in (1, 'foo', fn:concat#3, function($a) { 42 * $a })
 
where $item instance of function(*)
 
where $item instance of function(*)
Line 24: Line 18:
 
''Result:'' <code>3 1</code>
 
''Result:'' <code>3 1</code>
  
The notation for specifying argument and return types is quite intuitive, as it
+
The notation for specifying argument and return types is quite intuitive, as it closely resembles the function declaration. The XQuery function
closely resembles the function declaration. The XQuery function
 
  
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
declare function local:char-at(
 
declare function local:char-at(
   $str as xs:string,
+
   $str as xs:string,
   $pos as xs:integer
+
   $pos as xs:integer
 
) as xs:string {
 
) as xs:string {
 
   fn:substring($str, $pos, 1)
 
   fn:substring($str, $pos, 1)
Line 36: Line 29:
 
</pre>
 
</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
+
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.
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:
 
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">
+
<pre lang='xquery'>
 
declare function local:on-sequences(
 
declare function local:on-sequences(
 
   $fun as function(item()) as item()*
 
   $fun as function(item()) as item()*
Line 49: Line 40:
 
};
 
};
 
</pre>
 
</pre>
We'll see later how <code>fn:for-each(...)</code> works. The type of <code>local:on-sequences(...)</code> on the other hand is easily constructed, if a bit long:
+
 
 +
We willl see later how <code>fn:for-each(...)</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>.
 
<code>function(function(item()) as item()*) as function(item()*) as item()*</code>.
Line 57: Line 49:
 
A ''higher-order function'' is a function that takes other functions as arguments and/or returns them as results. <code>fn:for-each</code> and <code>local:on-sequences</code> from the last chapter are nice examples.
 
A ''higher-order function'' is a function that takes other functions as arguments and/or returns them as results. <code>fn:for-each</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
+
With the help of higher-order functions, one can extract common patterns of ''behavior'' and abstract them into a library function.
''behaviour'' and abstract them into a library function.
 
  
== Higher-Order Functions on Sequences ==
+
== Sequences ==
  
Some usage patterns on sequences are so common that the higher-order functions
+
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.
describing them are in the XQuery standard libraries. They are listed here, together
 
with their possible XQuery implementation and some motivating examples.
 
  
 
===fn:for-each===
 
===fn:for-each===
  
 
{|
 
{|
|-
+
|- valign="top"
| width='120' | '''Signatures'''
+
| width='120' | '''Signature'''
|{{Func|fn:for-each|$seq as item()*, $fun as function(item()) as item()*)|item()*}}<br/><font color='gray'>Old signature: fn:map($fun as function(item()) as item()*, $seq as item()*) as item()*</font>
+
|<pre>fn:for-each(
|-
+
  $input  as item()*,
 +
  $action  as function(item()) as item()*
 +
) as item()*</pre>
 +
|- valign="top"
 
| '''Summary'''
 
| '''Summary'''
|Applies the function item <code>$fun</code> to every element of the sequence <code>$seq</code> and returns all of the results as a sequence.
+
|Applies the specified <code>$action</code> to every item of <code>$input</code> and returns all results as a single sequence.
|-
+
|- valign="top"
 
| '''Examples'''
 
| '''Examples'''
 
|
 
|
<ul><li>Squaring all numbers from 1 to 10:
+
<ul><li>Square all numbers from 1 to 10:
  <pre class="brush:xquery">
+
<pre lang='xquery'>
 
fn:for-each(1 to 10, math:pow(?, 2))
 
fn:for-each(1 to 10, math:pow(?, 2))
 
</pre>
 
</pre>
 
''Result:'' <code>1 4 9 16 25 36 49 64 81 100</code>
 
''Result:'' <code>1 4 9 16 25 36 49 64 81 100</code>
 
</li>
 
</li>
<li>Applying a list of functions to a string:
+
<li>Apply a list of functions to a string:
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
let $fs := (
 
let $fs := (
 
   fn:upper-case#1,
 
   fn:upper-case#1,
Line 94: Line 86:
 
</pre>
 
</pre>
 
''Result:'' <code>FOOBAR bar 6</code>
 
''Result:'' <code>FOOBAR bar 6</code>
 +
</li>
 +
<li>Process each item of a sequence with the arrow operator:
 +
<pre lang='xquery'>
 +
("one", "two", "three") => fn:for-each(fn:upper-case(?))
 +
</pre>
 +
''Result:'' <code>ONE TWO THREE</code>
 
</li></ul>
 
</li></ul>
|-
+
|- valign="top"
 
| '''XQuery 1.0'''
 
| '''XQuery 1.0'''
|<pre class="brush:xquery">
+
|At the core, for-each is nothing else than a simple FLWOR expression:
 +
<pre lang='xquery'>
 
declare function local:for-each(
 
declare function local:for-each(
 
   $seq as item()*,
 
   $seq as item()*,
Line 111: Line 110:
  
 
{|
 
{|
|-
+
|- valign="top"
| width='120' | '''Signatures'''
+
| width='120' | '''Signature'''
|{{Func|fn:filter|$seq as item()*, $pred as function(item()) as xs:boolean)|item()*}}<br /><font color='gray'>fn:filter($pred as function(item()) as xs:boolean, $seq as item()*) as item()*</font>
+
|<pre>fn:filter(
|-
+
  $input      as item()*,
 +
  $predicate  as function(item()) as xs:boolean
 +
) as item()*</pre>
 +
|- valign="top"
 
| '''Summary'''
 
| '''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>.
+
|Applies the boolean <code>$predicate</code> to all elements of the sequence <code>$input</code>, returning those for which it returns <code>true()</code>.
|-
+
|- valign="top"
 
| '''Examples'''
 
| '''Examples'''
 
|<ul><li>All even integers until 10:
 
|<ul><li>All even integers until 10:
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
fn:filter(1 to 10, function($x) { $x mod 2 eq 0 })
 
fn:filter(1 to 10, function($x) { $x mod 2 eq 0 })
 
</pre>
 
</pre>
Line 126: Line 128:
 
</li>
 
</li>
 
<li>Strings that start with an upper-case letter:
 
<li>Strings that start with an upper-case letter:
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
let $first-upper := function($str) {
 
let $first-upper := function($str) {
 
   let $first := fn:substring($str, 1, 1)
 
   let $first := fn:substring($str, 1, 1)
Line 136: Line 138:
 
</li>
 
</li>
 
<li>Inefficient prime number generator:
 
<li>Inefficient prime number generator:
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
let $is-prime := function($x) {
 
let $is-prime := function($x) {
 
   $x gt 1 and (every $y in 2 to ($x - 1) satisfies $x mod $y ne 0)
 
   $x gt 1 and (every $y in 2 to ($x - 1) satisfies $x mod $y ne 0)
Line 144: Line 146:
 
''Result:'' <code>2 3 5 7 11 13 17 19</code>
 
''Result:'' <code>2 3 5 7 11 13 17 19</code>
 
</li></ul>
 
</li></ul>
|-
+
|- valign="top"
 
| '''Note'''
 
| '''Note'''
 
|<code>fn:filter</code> can be easily implemented with <code>fn:for-each</code>:
 
|<code>fn:filter</code> can be easily implemented with <code>fn:for-each</code>:
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
declare function local:filter($seq, $pred) {
 
declare function local:filter($seq, $pred) {
 
   for-each(
 
   for-each(
Line 157: Line 159:
 
};
 
};
 
</pre>
 
</pre>
|-
+
|- valign="top"
 
| '''XQuery 1.0'''
 
| '''XQuery 1.0'''
|<pre class="brush:xquery">
+
|At the core, for-each is nothing else than a filter expression:
 +
<pre lang='xquery'>
 
declare function local:filter(
 
declare function local:filter(
 
   $seq as item()*,
 
   $seq as item()*,
Line 172: Line 175:
  
 
{|
 
{|
|-
+
|- valign="top"
| width='120' | '''Signatures'''
+
| width='120' | '''Signature'''
|{{Func|fn:for-each-pair|$seq1 as item()*, $seq2 as item()*, $fun as function(item(), item()) as item()*|item()*}}<br /><font color='gray'>Old signature: fn:map-pairs($fun as function(item(), item()) as item()*, $seq1 as item()*, $seq2 as item()*) as item()*</font>
+
|<pre>fn:for-each-pair(
|-
+
  $input1  as item()*,
 +
  $input2  as item()*,
 +
  $action  as function(item(), item()) as item()*
 +
) as item()*</pre>
 +
|- valign="top"
 
| '''Summary'''
 
| '''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.
+
|Applies the specified {{Code|$action}} to the successive pairs of items of <code>$input1</code> and <code>$input2</code>. Evaluation is stopped if one sequence yields no more items.
|-
+
|- valign="top"
 
| '''Examples'''
 
| '''Examples'''
 
|<ul><li>Adding one to the numbers at odd positions:
 
|<ul><li>Adding one to the numbers at odd positions:
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
fn:for-each-pair(
 
fn:for-each-pair(
 
   fn:for-each(1 to 10, function($x) { $x mod 2 }),
 
   fn:for-each(1 to 10, function($x) { $x mod 2 }),
Line 191: Line 198:
 
</li>
 
</li>
 
<li>Line numbering:
 
<li>Line numbering:
<pre class="brush:xquery">
+
<pre lang='xquery'>
let $number-lines := function($str) {
+
let $number-words := function($str) {
 
   fn:string-join(
 
   fn:string-join(
 
     fn:for-each-pair(
 
     fn:for-each-pair(
       1 to 1000,
+
       1 to 1000000000,
       tokenize($str, '\r?\n|\r'),
+
       tokenize($str, ' +'),
 
       concat(?, ': ', ?)
 
       concat(?, ': ', ?)
 
     ),
 
     ),
     '&amp;#xa;'
+
     '&#xa;'
 
   )
 
   )
 
}
 
}
return $number-lines('hello world,
+
return $number-words('how are you?')
how are you?')
 
 
</pre>
 
</pre>
 
''Result:''
 
''Result:''
<pre>
+
<pre lang='xquery'>
1: hello world,
+
1: how
2: how are you?
+
2: are
 +
3: you?
 
</pre>
 
</pre>
 
</li>
 
</li>
 
<li>Checking if a sequence is sorted:
 
<li>Checking if a sequence is sorted:
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
let $is-sorted := function($seq) {
 
let $is-sorted := function($seq) {
 
   every $b in
 
   every $b in
 
     fn:for-each-pair(
 
     fn:for-each-pair(
 
       $seq,
 
       $seq,
       fn:tail($seq),
+
       tail($seq),
 
       function($a, $b) { $a le $b }
 
       function($a, $b) { $a le $b }
 
     )
 
     )
Line 228: Line 235:
 
</pre>
 
</pre>
 
''Result:'' <code>true false</code></li></ul>
 
''Result:'' <code>true false</code></li></ul>
|-
+
|- valign="top"
 
| '''XQuery 1.0'''
 
| '''XQuery 1.0'''
|<pre class="brush:xquery">
+
|<pre lang='xquery'>
 
declare function local:for-each-pair(
 
declare function local:for-each-pair(
 
   $seq1 as item()*,
 
   $seq1 as item()*,
Line 244: Line 251:
 
== Folds ==
 
== Folds ==
  
A ''fold'', also called ''reduce'' or ''accumulate'' in other languages, is a very
+
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 of a user-defined function.
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.
+
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.
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>:
 
Calculating the ''product'' of a sequence of integers for example is easy in <code>Java</code>:
<pre class="brush:java">
+
 
 +
<pre lang="java">
 
public int product(int[] seq) {
 
public int product(int[] seq) {
 
   int result = 1;
 
   int result = 1;
Line 263: Line 266:
 
}
 
}
 
</pre>
 
</pre>
 +
 
Nice and efficient implementations using folds will be given below.
 
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:
+
The ''linear'' folds on sequences come in two flavors. They differ in the direction in which they traverse the sequence:
  
 
===fn:fold-left===
 
===fn:fold-left===
  
 
{|
 
{|
|-
+
|- valign="top"
| width='120' | '''Signatures'''
+
| width='120' | '''Signature'''
|{{Func|fn:fold-left|$seq as item()*, $seed as item()*, $fun as function(item()*, item()) as item()*|item()*}}<br /><font color='gray'>Old signature: fn:fold-left</b>($fun as function(item()*, item()) as item()*, $seed as item()*, $seq as item()*) as item()*</font>
+
|<pre>fn:fold-left(
|-
+
  $input  as item()*,
 +
  $zero    as item()*,
 +
  $action  as function(item()*, item()) as item()*
 +
) as item()*</pre>
 +
|- valign="top"
 
| '''Summary'''
 
| '''Summary'''
|The ''left fold'' traverses the sequence from the left.
+
|The ''left fold'' traverses the {{Code|$input}} from the left.
The query <code>fn:fold-left(1 to 5, 0, $f)</code> for example would be evaluated as:
+
The query <code>fn:fold-left(1 to 5, 0, $f)</code>, for example, would be evaluated as:
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
$f($f($f($f($f(0, 1), 2), 3), 4), 5)
 
$f($f($f($f($f(0, 1), 2), 3), 4), 5)
 
</pre>
 
</pre>
|-
+
|- valign="top"
 
| '''Examples'''
 
| '''Examples'''
 
|<ul><li>Product of a sequence of integers:
 
|<ul><li>Product of a sequence of integers:
<pre class="brush:xquery">
+
<pre lang='xquery'>
let $product := fn:fold-left(?, 1,
+
fn:fold-left(1 to 5, 1,
   function($result, $i) { $result * $i }
+
   function($result, $curr) { $result * $curr }
 
)
 
)
return $product(1 to 5)
 
 
</pre>
 
</pre>
 
''Result:'' <code>120</code>
 
''Result:'' <code>120</code>
 
</li>
 
</li>
 
<li>Illustrating the evaluation order:
 
<li>Illustrating the evaluation order:
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
fn:fold-left(1 to 5, '$seed',
 
fn:fold-left(1 to 5, '$seed',
 
   concat('$f(', ?, ', ', ?, ')')
 
   concat('$f(', ?, ', ', ?, ')')
Line 300: Line 307:
 
</li>
 
</li>
 
<li>Building a decimal number from digits:
 
<li>Building a decimal number from digits:
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
let $from-digits := fold-left(?, 0,
 
let $from-digits := fold-left(?, 0,
 
   function($n, $d) { 10 * $n + $d }
 
   function($n, $d) { 10 * $n + $d }
Line 311: Line 318:
 
''Result:'' <code>12345 42</code>
 
''Result:'' <code>12345 42</code>
 
</li></ul>
 
</li></ul>
|-
+
|- valign="top"
 
| '''XQuery 1.0'''
 
| '''XQuery 1.0'''
 
|As folds are more general than ''FLWOR'' expressions, the implementation isn't as concise as the former ones:
 
|As folds are more general than ''FLWOR'' expressions, the implementation isn't as concise as the former ones:
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
declare function local:fold-left(
 
declare function local:fold-left(
   $seq as item()*,
+
   $input  as item()*,
   $seed as item()*,
+
   $zero    as item()*,
   $fun as function(item()*, item()) as item()*
+
   $action  as function(item()*, item()) as item()*
 
) as item()* {
 
) as item()* {
   if(empty($seq)) then $seed
+
   if(empty($input)) then $zero
 
   else local:fold-left(
 
   else local:fold-left(
     fn:tail($seq),
+
     tail($input),
     $fun($seed, fn:head($seq)),
+
     $action($zero, head($input)),
     $fun
+
     $action
 
   )  
 
   )  
 
};
 
};
Line 333: Line 340:
  
 
{|
 
{|
|-
+
|- valign="top"
| width='120' | '''Signatures'''
+
| width='120' | '''Signature'''
|{{Func|fn:fold-right|$seq as item()*, $seed as item()*, $fun as function(item(), item()*|item()*}}<br /><font color='gray'>Old signature: fn:fold-right</b>($fun as function(item(), item()*) as item()*, $seed as item()*, $seq as item()*) as item()*</font>
+
|<pre>fn:fold-right(
|-
+
  $input  as item()*,
 +
  $zero    as item()*,
 +
  $action  as function(item(), item()*) as item()*
 +
) as item()*</pre>
 +
|- valign="top"
 
| '''Summary'''
 
| '''Summary'''
|The ''right fold'' <code>fn:fold-right($seq, $seed, $fun)</code> traverses the from the right.
+
|The ''right fold'' traverses the {{Code|$input}} from the right.
The query <code>fn:fold-right(1 to 5, 0, $f)</code> for example would be evaluated as:
+
The query <code>fn:fold-right(1 to 5, 0, $f)</code>, for example, would be evaluated as:
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
$f(1, $f(2, $f(3, $f(4, $f(5, 0)))))
 
$f(1, $f(2, $f(3, $f(4, $f(5, 0)))))
 
</pre>
 
</pre>
|-
+
|- valign="top"
 
| '''Examples'''
 
| '''Examples'''
 
|<ul><li>Product of a sequence of integers:
 
|<ul><li>Product of a sequence of integers:
<pre class="brush:xquery">
+
<pre lang='xquery'>
let $product := fn:fold-right(?, 1,
+
fn:fold-right(1 to 5, 1,
   function($i, $result) { $result * $i }
+
   function($curr, $result) { $result * $curr }
 
)
 
)
return $product(1 to 5)
 
 
</pre>
 
</pre>
 
''Result:'' <code>120</code>
 
''Result:'' <code>120</code>
 
</li>
 
</li>
 
<li>Illustrating the evaluation order:
 
<li>Illustrating the evaluation order:
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
fn:fold-right(1 to 5, '$seed',
 
fn:fold-right(1 to 5, '$seed',
 
   concat('$f(', ?, ', ', ?, ')')
 
   concat('$f(', ?, ', ', ?, ')')
Line 363: Line 373:
 
</li>
 
</li>
 
<li>Reversing a sequence of items:
 
<li>Reversing a sequence of items:
<pre class="brush:xquery">
+
<pre lang='xquery'>
 
let $reverse := fn:fold-right(?, (),
 
let $reverse := fn:fold-right(?, (),
 
   function($item, $rev) {
 
   function($item, $rev) {
Line 373: Line 383:
 
''Result:'' <code>10 9 8 7 6 5 4 3 2 1</code>
 
''Result:'' <code>10 9 8 7 6 5 4 3 2 1</code>
 
</li></ul>
 
</li></ul>
|-
+
|- valign="top"
 
| '''XQuery 1.0'''
 
| '''XQuery 1.0'''
|<pre class="brush:xquery">
+
|<pre lang='xquery'>
 
declare function local:fold-right(
 
declare function local:fold-right(
   $seq as item()*,
+
   $input  as item()*,
   $seed as item()*,
+
   $zero    as item()*,
   $fun as function(item(), item()*) as item()*
+
   $action  as function(item(), item()*) as item()*
 
) as item()* {
 
) as item()* {
   if(empty($seq)) then $seed
+
   if(empty($input)) then $zero
   else $fun(
+
   else $action(
     fn:head($seq),
+
     head($input),
     local:fold-right(tail($seq), $seed, $fun)
+
     local:fold-right(tail($input), $zero, $action)
 
   )
 
   )
 
};
 
};
Line 390: Line 400:
 
Note that the order of the arguments of <code>$fun</code> are inverted compared to that in <code>fn:fold-left(...)</code>.
 
Note that the order of the arguments of <code>$fun</code> are inverted compared to that in <code>fn:fold-left(...)</code>.
 
|}
 
|}
 
[[Category:XQuery]]
 

Latest revision as of 17:39, 1 December 2023

This page present some higher-order functions of the XQuery specification. The BaseX-specific Higher-Order Functions Module contains some additional useful functions.

Function Items[edit]

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. This feature makes functions first-class citizens of the language. The XQuery 3.0 page goes into details on how function items can be obtained.

Function Types[edit]

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 function(*). 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:

for $item in (1, 'foo', fn:concat#3, function($a) { 42 * $a })
where $item instance of function(*)
return fn:function-arity($item)

Result: 3 1

The notation for specifying argument and return types is quite intuitive, as it closely resembles the function declaration. The XQuery function

declare function local:char-at(
  $str  as xs:string,
  $pos  as xs:integer
) as xs:string {
  fn:substring($str, $pos, 1)
};

for example has the type function(xs:string, xs:integer) as xs:string. 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 item()*, as it matches any XQuery value.

Function types can also be nested. As an example we take local:on-sequences, which takes a function defined on single items and makes it work on sequences as well:

declare function local:on-sequences(
  $fun as function(item()) as item()*
) as function(item()*) as item()* {
  fn:for-each($fun, ?)
};

We willl see later how fn:for-each(...) works. The type of local:on-sequences(...) on the other hand is easily constructed, if a bit long:

function(function(item()) as item()*) as function(item()*) as item()*.

Higher-Order Functions[edit]

A higher-order function is a function that takes other functions as arguments and/or returns them as results. fn:for-each and local:on-sequences from the last chapter are nice examples.

With the help of higher-order functions, one can extract common patterns of behavior and abstract them into a library function.

Sequences[edit]

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:for-each[edit]

Signature
fn:for-each(
  $input   as item()*,
  $action  as function(item()) as item()*
) as item()*
Summary Applies the specified $action to every item of $input and returns all results as a single sequence.
Examples
  • Square all numbers from 1 to 10:
    fn:for-each(1 to 10, math:pow(?, 2))
    

    Result: 1 4 9 16 25 36 49 64 81 100

  • Apply a list of functions to a string:
    let $fs := (
      fn:upper-case#1,
      fn:substring(?, 4),
      fn:string-length#1
    )
    return fn:for-each($fs, function($f) { $f('foobar') })
    

    Result: FOOBAR bar 6

  • Process each item of a sequence with the arrow operator:
    ("one", "two", "three") => fn:for-each(fn:upper-case(?))
    

    Result: ONE TWO THREE

XQuery 1.0 At the core, for-each is nothing else than a simple FLWOR expression:
declare function local:for-each(
  $seq as item()*,
  $fun as function(item()) as item()*
) as item()* {
  for $s in $seq
  return $fun($s)
};

fn:filter[edit]

Signature
fn:filter(
  $input      as item()*,
  $predicate  as function(item()) as xs:boolean
) as item()*
Summary Applies the boolean $predicate to all elements of the sequence $input, returning those for which it returns true().
Examples
  • All even integers until 10:
    fn:filter(1 to 10, function($x) { $x mod 2 eq 0 })
    

    Result: 2 4 6 8 10

  • Strings that start with an upper-case letter:
    let $first-upper := function($str) {
      let $first := fn:substring($str, 1, 1)
      return $first eq fn:upper-case($first)
    }
    return fn:filter(('FooBar', 'foo', 'BAR'), $first-upper)
    

    Result: FooBar BAR

  • Inefficient prime number generator:
    let $is-prime := function($x) {
      $x gt 1 and (every $y in 2 to ($x - 1) satisfies $x mod $y ne 0)
    }
    return filter(1 to 20, $is-prime)
    

    Result: 2 3 5 7 11 13 17 19

Note fn:filter can be easily implemented with fn:for-each:
declare function local:filter($seq, $pred) {
  for-each(
    $seq,
    function($x) {
      if($pred($x)) then $x else ()
    }
  )
};
XQuery 1.0 At the core, for-each is nothing else than a filter expression:
declare function local:filter(
  $seq as item()*,
  $pred as function(item()) as xs:boolean
) as item()* {
  $seq[$pred(.)]
};

fn:for-each-pair[edit]

Signature
fn:for-each-pair(
  $input1   as item()*,
  $input2   as item()*,
  $action  as function(item(), item()) as item()*
) as item()*
Summary Applies the specified $action to the successive pairs of items of $input1 and $input2. Evaluation is stopped if one sequence yields no more items.
Examples
  • Adding one to the numbers at odd positions:
    fn:for-each-pair(
      fn:for-each(1 to 10, function($x) { $x mod 2 }),
      (1, 1, 1, 1, 1),
      function($a, $b) { $a + $b }
    )
    

    Result: 2 1 2 1 2

  • Line numbering:
    let $number-words := function($str) {
      fn:string-join(
        fn:for-each-pair(
          1 to 1000000000,
          tokenize($str, ' +'),
          concat(?, ': ', ?)
        ),
        '
    '
      )
    }
    return $number-words('how are you?')
    

    Result:

    1: how
    2: are
    3: you?
    
  • Checking if a sequence is sorted:
    let $is-sorted := function($seq) {
      every $b in
        fn:for-each-pair(
          $seq,
          tail($seq),
          function($a, $b) { $a le $b }
        )
      satisfies $b
    }
    return (
      $is-sorted(1 to 10),
      $is-sorted((1, 2, 42, 4, 5))
    )
    
    Result: true false
XQuery 1.0
declare function local:for-each-pair(
  $seq1 as item()*,
  $seq2 as item()*,
  $fun as function(item(), item()) as item()*
) as item()* {
  for $pos in 1 to min((count($seq1), count($seq2)))
  return $fun($seq1[$pos], $seq2[$pos])
};

Folds[edit]

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 of 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 Java:

public int product(int[] seq) {
  int result = 1;
  for(int i : seq) {
    result = result * i;
  }
  return result;
}

Nice and efficient implementations using folds will be given below.

The linear folds on sequences come in two flavors. They differ in the direction in which they traverse the sequence:

fn:fold-left[edit]

Signature
fn:fold-left(
  $input   as item()*,
  $zero    as item()*,
  $action  as function(item()*, item()) as item()*
) as item()*
Summary The left fold traverses the $input from the left.

The query fn:fold-left(1 to 5, 0, $f), for example, would be evaluated as:

$f($f($f($f($f(0, 1), 2), 3), 4), 5)
Examples
  • Product of a sequence of integers:
    fn:fold-left(1 to 5, 1,
      function($result, $curr) { $result * $curr }
    )
    

    Result: 120

  • Illustrating the evaluation order:
    fn:fold-left(1 to 5, '$seed',
      concat('$f(', ?, ', ', ?, ')')
    )
    

    Result: $f($f($f($f($f($seed, 1), 2), 3), 4), 5)

  • Building a decimal number from digits:
    let $from-digits := fold-left(?, 0,
      function($n, $d) { 10 * $n + $d }
    )
    return (
      $from-digits(1 to 5),
      $from-digits((4, 2))
    )
    

    Result: 12345 42

XQuery 1.0 As folds are more general than FLWOR expressions, the implementation isn't as concise as the former ones:
declare function local:fold-left(
  $input   as item()*,
  $zero    as item()*,
  $action  as function(item()*, item()) as item()*
) as item()* {
  if(empty($input)) then $zero
  else local:fold-left(
    tail($input),
    $action($zero, head($input)),
    $action
  ) 
};

fn:fold-right[edit]

Signature
fn:fold-right(
  $input   as item()*,
  $zero    as item()*,
  $action  as function(item(), item()*) as item()*
) as item()*
Summary The right fold traverses the $input from the right.

The query fn:fold-right(1 to 5, 0, $f), for example, would be evaluated as:

$f(1, $f(2, $f(3, $f(4, $f(5, 0)))))
Examples
  • Product of a sequence of integers:
    fn:fold-right(1 to 5, 1,
      function($curr, $result) { $result * $curr }
    )
    

    Result: 120

  • Illustrating the evaluation order:
    fn:fold-right(1 to 5, '$seed',
      concat('$f(', ?, ', ', ?, ')')
    )
    

    Result: $f(1, $f(2, $f(3, $f(4, $f(5, $seed)))))

  • Reversing a sequence of items:
    let $reverse := fn:fold-right(?, (),
      function($item, $rev) {
        $rev, $item
      }
    )
    return $reverse(1 to 10)
    

    Result: 10 9 8 7 6 5 4 3 2 1

XQuery 1.0
declare function local:fold-right(
  $input   as item()*,
  $zero    as item()*,
  $action  as function(item(), item()*) as item()*
) as item()* {
  if(empty($input)) then $zero
  else $action(
    head($input),
    local:fold-right(tail($input), $zero, $action)
  )
};

Note that the order of the arguments of $fun are inverted compared to that in fn:fold-left(...).