Difference between revisions of "Higher-Order Functions"

From BaseX Documentation
Jump to navigation Jump to search
Line 11: Line 11:
 
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:
 
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">
+
<syntaxhighlight 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(*)
 
return fn:function-arity($item)
 
return fn:function-arity($item)
</pre>
+
</syntaxhighlight>
 
''Result:'' <code>3 1</code>
 
''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
 
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">
+
<syntaxhighlight lang="xquery">
 
declare function local:char-at(
 
declare function local:char-at(
 
   $str as xs:string,
 
   $str as xs:string,
Line 27: Line 27:
 
   fn:substring($str, $pos, 1)
 
   fn:substring($str, $pos, 1)
 
};
 
};
</pre>
+
</syntaxhighlight>
  
 
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.
 
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.
Line 33: Line 33:
 
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">
+
<syntaxhighlight 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 39: Line 39:
 
   fn:for-each($fun, ?)
 
   fn:for-each($fun, ?)
 
};
 
};
</pre>
+
</syntaxhighlight>
  
 
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:
 
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:
Line 68: Line 68:
 
|
 
|
 
<ul><li>Square all numbers from 1 to 10:
 
<ul><li>Square all numbers from 1 to 10:
  <pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
fn:for-each(1 to 10, math:pow(?, 2))
 
fn:for-each(1 to 10, math:pow(?, 2))
</pre>
+
</syntaxhighlight>
 
''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>Apply a list of functions to a string:
 
<li>Apply a list of functions to a string:
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
let $fs := (
 
let $fs := (
 
   fn:upper-case#1,
 
   fn:upper-case#1,
Line 81: Line 81:
 
)
 
)
 
return fn:for-each($fs, function($f) { $f('foobar') })
 
return fn:for-each($fs, function($f) { $f('foobar') })
</pre>
+
</syntaxhighlight>
 
''Result:'' <code>FOOBAR bar 6</code>
 
''Result:'' <code>FOOBAR bar 6</code>
 
</li>
 
</li>
 
<li>Process each item of a sequence with the arrow operator:
 
<li>Process each item of a sequence with the arrow operator:
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
("one", "two", "three") => fn:for-each(fn:upper-case(?))
 
("one", "two", "three") => fn:for-each(fn:upper-case(?))
</pre>
+
</syntaxhighlight>
 
''Result:'' <code>ONE TWO THREE</code>
 
''Result:'' <code>ONE TWO THREE</code>
 
</li></ul>
 
</li></ul>
Line 93: Line 93:
 
| '''XQuery 1.0'''
 
| '''XQuery 1.0'''
 
|At the core, for-each is nothing else than a simple FLWOR expression:
 
|At the core, for-each is nothing else than a simple FLWOR expression:
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
declare function local:for-each(
 
declare function local:for-each(
 
   $seq as item()*,
 
   $seq as item()*,
Line 101: Line 101:
 
   return $fun($s)
 
   return $fun($s)
 
};
 
};
</pre>
+
</syntaxhighlight>
 
|}
 
|}
  
Line 116: Line 116:
 
| '''Examples'''
 
| '''Examples'''
 
|<ul><li>All even integers until 10:
 
|<ul><li>All even integers until 10:
<pre class="brush:xquery">
+
<syntaxhighlight 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>
+
</syntaxhighlight>
 
''Result:'' <code>2 4 6 8 10</code>
 
''Result:'' <code>2 4 6 8 10</code>
 
</li>
 
</li>
 
<li>Strings that start with an upper-case letter:
 
<li>Strings that start with an upper-case letter:
<pre class="brush:xquery">
+
<syntaxhighlight 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 128: Line 128:
 
}
 
}
 
return fn:filter(('FooBar', 'foo', 'BAR'), $first-upper)
 
return fn:filter(('FooBar', 'foo', 'BAR'), $first-upper)
</pre>
+
</syntaxhighlight>
 
''Result:'' <code>FooBar BAR</code>
 
''Result:'' <code>FooBar BAR</code>
 
</li>
 
</li>
 
<li>Inefficient prime number generator:
 
<li>Inefficient prime number generator:
<pre class="brush:xquery">
+
<syntaxhighlight 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)
 
}
 
}
 
return filter(1 to 20, $is-prime)
 
return filter(1 to 20, $is-prime)
</pre>
+
</syntaxhighlight>
 
''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>
Line 143: Line 143:
 
| '''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">
+
<syntaxhighlight lang="xquery">
 
declare function local:filter($seq, $pred) {
 
declare function local:filter($seq, $pred) {
 
   for-each(
 
   for-each(
Line 152: Line 152:
 
   )
 
   )
 
};
 
};
</pre>
+
</syntaxhighlight>
 
|-
 
|-
 
| '''XQuery 1.0'''
 
| '''XQuery 1.0'''
 
|At the core, for-each is nothing else than a filter expression:
 
|At the core, for-each is nothing else than a filter expression:
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
declare function local:filter(
 
declare function local:filter(
 
   $seq as item()*,
 
   $seq as item()*,
Line 163: Line 163:
 
   $seq[$pred(.)]
 
   $seq[$pred(.)]
 
};
 
};
</pre>
+
</syntaxhighlight>
 
|}
 
|}
  
Line 178: Line 178:
 
| '''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">
+
<syntaxhighlight 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 184: Line 184:
 
   function($a, $b) { $a + $b }
 
   function($a, $b) { $a + $b }
 
)
 
)
</pre>
+
</syntaxhighlight>
 
''Result:'' <code>2 1 2 1 2</code>
 
''Result:'' <code>2 1 2 1 2</code>
 
</li>
 
</li>
 
<li>Line numbering:
 
<li>Line numbering:
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
let $number-words := function($str) {
 
let $number-words := function($str) {
 
   fn:string-join(
 
   fn:string-join(
Line 200: Line 200:
 
}
 
}
 
return $number-words('how are you?')
 
return $number-words('how are you?')
</pre>
+
</syntaxhighlight>
 
''Result:''
 
''Result:''
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
1: how
 
1: how
 
2: are
 
2: are
 
3: you?
 
3: you?
</pre>
+
</syntaxhighlight>
 
</li>
 
</li>
 
<li>Checking if a sequence is sorted:
 
<li>Checking if a sequence is sorted:
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
let $is-sorted := function($seq) {
 
let $is-sorted := function($seq) {
 
   every $b in
 
   every $b in
Line 223: Line 223:
 
   $is-sorted((1, 2, 42, 4, 5))
 
   $is-sorted((1, 2, 42, 4, 5))
 
)
 
)
</pre>
+
</syntaxhighlight>
 
''Result:'' <code>true false</code></li></ul>
 
''Result:'' <code>true false</code></li></ul>
 
|-
 
|-
 
| '''XQuery 1.0'''
 
| '''XQuery 1.0'''
|<pre class="brush:xquery">
+
|<syntaxhighlight lang="xquery">
 
declare function local:for-each-pair(
 
declare function local:for-each-pair(
 
   $seq1 as item()*,
 
   $seq1 as item()*,
Line 236: Line 236:
 
   return $fun($seq1[$pos], $seq2[$pos])
 
   return $fun($seq1[$pos], $seq2[$pos])
 
};
 
};
</pre>
+
</syntaxhighlight>
 
|}
 
|}
  
Line 247: Line 247:
 
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">
+
<syntaxhighlight lang="java">
 
public int product(int[] seq) {
 
public int product(int[] seq) {
 
   int result = 1;
 
   int result = 1;
Line 255: Line 255:
 
   return result;
 
   return result;
 
}
 
}
</pre>
+
</syntaxhighlight>
  
 
Nice and efficient implementations using folds will be given below.
 
Nice and efficient implementations using folds will be given below.
Line 271: Line 271:
 
|The ''left fold'' traverses the sequence from the left.
 
|The ''left fold'' traverses the sequence 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">
+
<syntaxhighlight 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>
+
</syntaxhighlight>
 
|-
 
|-
 
| '''Examples'''
 
| '''Examples'''
 
|<ul><li>Product of a sequence of integers:
 
|<ul><li>Product of a sequence of integers:
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
fn:fold-left(1 to 5, 1,
 
fn:fold-left(1 to 5, 1,
 
   function($result, $curr) { $result * $curr }
 
   function($result, $curr) { $result * $curr }
 
)
 
)
</pre>
+
</syntaxhighlight>
 
''Result:'' <code>120</code>
 
''Result:'' <code>120</code>
 
</li>
 
</li>
 
<li>Illustrating the evaluation order:
 
<li>Illustrating the evaluation order:
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
fn:fold-left(1 to 5, '$seed',
 
fn:fold-left(1 to 5, '$seed',
 
   concat('$f(', ?, ', ', ?, ')')
 
   concat('$f(', ?, ', ', ?, ')')
 
)
 
)
</pre>
+
</syntaxhighlight>
 
''Result:'' <code>$f($f($f($f($f($seed, 1), 2), 3), 4), 5)</code>
 
''Result:'' <code>$f($f($f($f($f($seed, 1), 2), 3), 4), 5)</code>
 
</li>
 
</li>
 
<li>Building a decimal number from digits:
 
<li>Building a decimal number from digits:
<pre class="brush:xquery">
+
<syntaxhighlight 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 301: Line 301:
 
   $from-digits((4, 2))
 
   $from-digits((4, 2))
 
)
 
)
</pre>
+
</syntaxhighlight>
 
''Result:'' <code>12345 42</code>
 
''Result:'' <code>12345 42</code>
 
</li></ul>
 
</li></ul>
Line 307: Line 307:
 
| '''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">
+
<syntaxhighlight lang="xquery">
 
declare function local:fold-left(
 
declare function local:fold-left(
 
   $seq as item()*,
 
   $seq as item()*,
Line 320: Line 320:
 
   )  
 
   )  
 
};
 
};
</pre>
+
</syntaxhighlight>
 
|}
 
|}
  
Line 333: Line 333:
 
|The ''right fold'' <code>fn:fold-right($seq, $seed, $fun)</code> traverses the sequence from the right.
 
|The ''right fold'' <code>fn:fold-right($seq, $seed, $fun)</code> traverses the sequence 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">
+
<syntaxhighlight 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>
+
</syntaxhighlight>
 
|-
 
|-
 
| '''Examples'''
 
| '''Examples'''
 
|<ul><li>Product of a sequence of integers:
 
|<ul><li>Product of a sequence of integers:
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
fn:fold-right(1 to 5, 1,
 
fn:fold-right(1 to 5, 1,
 
   function($curr, $result) { $result * $curr }
 
   function($curr, $result) { $result * $curr }
 
)
 
)
</pre>
+
</syntaxhighlight>
 
''Result:'' <code>120</code>
 
''Result:'' <code>120</code>
 
</li>
 
</li>
 
<li>Illustrating the evaluation order:
 
<li>Illustrating the evaluation order:
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
fn:fold-right(1 to 5, '$seed',
 
fn:fold-right(1 to 5, '$seed',
 
   concat('$f(', ?, ', ', ?, ')')
 
   concat('$f(', ?, ', ', ?, ')')
 
)
 
)
</pre>
+
</syntaxhighlight>
 
''Result:'' <code>$f(1, $f(2, $f(3, $f(4, $f(5, $seed)))))</code>
 
''Result:'' <code>$f(1, $f(2, $f(3, $f(4, $f(5, $seed)))))</code>
 
</li>
 
</li>
 
<li>Reversing a sequence of items:
 
<li>Reversing a sequence of items:
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
let $reverse := fn:fold-right(?, (),
 
let $reverse := fn:fold-right(?, (),
 
   function($item, $rev) {
 
   function($item, $rev) {
Line 362: Line 362:
 
)
 
)
 
return $reverse(1 to 10)
 
return $reverse(1 to 10)
</pre>
+
</syntaxhighlight>
 
''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>
 
|-
 
|-
 
| '''XQuery 1.0'''
 
| '''XQuery 1.0'''
|<pre class="brush:xquery">
+
|<syntaxhighlight lang="xquery">
 
declare function local:fold-right(
 
declare function local:fold-right(
 
   $seq as item()*,
 
   $seq as item()*,
Line 379: Line 379:
 
   )
 
   )
 
};
 
};
</pre>
+
</syntaxhighlight>
 
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>.
 
|}
 
|}

Revision as of 13:17, 27 February 2020

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

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

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:

<syntaxhighlight lang="xquery"> for $item in (1, 'foo', fn:concat#3, function($a) { 42 * $a }) where $item instance of function(*) return fn:function-arity($item) </syntaxhighlight> Result: 3 1

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

<syntaxhighlight lang="xquery"> declare function local:char-at(

 $str as xs:string,
 $pos as xs:integer

) as xs:string {

 fn:substring($str, $pos, 1)

}; </syntaxhighlight>

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:

<syntaxhighlight lang="xquery"> declare function local:on-sequences(

 $fun as function(item()) as item()*

) as function(item()*) as item()* {

 fn:for-each($fun, ?)

}; </syntaxhighlight>

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

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

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

Signatures fn:for-each($seq as item()*, $function as function(item()) as item()*)) as item()*
Summary Applies the specified $function to every item of $seq and returns all results as a single sequence.
Examples
  • Square all numbers from 1 to 10: <syntaxhighlight lang="xquery"> fn:for-each(1 to 10, math:pow(?, 2)) </syntaxhighlight> Result: 1 4 9 16 25 36 49 64 81 100
  • Apply a list of functions to a string: <syntaxhighlight lang="xquery"> let $fs := ( fn:upper-case#1, fn:substring(?, 4), fn:string-length#1 ) return fn:for-each($fs, function($f) { $f('foobar') }) </syntaxhighlight> Result: FOOBAR bar 6
  • Process each item of a sequence with the arrow operator: <syntaxhighlight lang="xquery"> ("one", "two", "three") => fn:for-each(fn:upper-case(?)) </syntaxhighlight> Result: ONE TWO THREE
XQuery 1.0 At the core, for-each is nothing else than a simple FLWOR expression:

<syntaxhighlight lang="xquery"> declare function local:for-each(

 $seq as item()*,
 $fun as function(item()) as item()*

) as item()* {

 for $s in $seq
 return $fun($s)

}; </syntaxhighlight>

fn:filter

Signatures fn:filter($seq as item()*, $pred as function(item()) as xs:boolean)) as item()*
Summary Applies the boolean predicate $pred to all elements of the sequence $seq, returning those for which it returns true().
Examples
  • All even integers until 10:

    <syntaxhighlight lang="xquery"> fn:filter(1 to 10, function($x) { $x mod 2 eq 0 }) </syntaxhighlight> Result: 2 4 6 8 10

  • Strings that start with an upper-case letter: <syntaxhighlight lang="xquery"> 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) </syntaxhighlight> Result: FooBar BAR
  • Inefficient prime number generator: <syntaxhighlight lang="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(1 to 20, $is-prime) </syntaxhighlight> Result: 2 3 5 7 11 13 17 19
Note fn:filter can be easily implemented with fn:for-each:

<syntaxhighlight lang="xquery"> declare function local:filter($seq, $pred) {

 for-each(
   $seq,
   function($x) {
     if($pred($x)) then $x else ()
   }
 )

}; </syntaxhighlight>

XQuery 1.0 At the core, for-each is nothing else than a filter expression:

<syntaxhighlight lang="xquery"> declare function local:filter(

 $seq as item()*,
 $pred as function(item()) as xs:boolean

) as item()* {

 $seq[$pred(.)]

}; </syntaxhighlight>

fn:for-each-pair

Signatures fn:for-each-pair($seq1 as item()*, $seq2 as item()*, $function as function(item(), item()) as item()*) as item()*
Summary Applies the specified $function to the successive pairs of items of $seq1 and $seq2. Evaluation is stopped if one sequence yields no more items.
Examples
  • Adding one to the numbers at odd positions:

    <syntaxhighlight lang="xquery"> 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 }
    

    ) </syntaxhighlight> Result: 2 1 2 1 2

  • Line numbering: <syntaxhighlight lang="xquery"> let $number-words := function($str) { fn:string-join( fn:for-each-pair( 1 to 1000000000, tokenize($str, ' +'), concat(?, ': ', ?) ), ' ' ) } return $number-words('how are you?') </syntaxhighlight> Result: <syntaxhighlight lang="xquery"> 1: how 2: are 3: you? </syntaxhighlight>
  • Checking if a sequence is sorted: <syntaxhighlight lang="xquery"> let $is-sorted := function($seq) { every $b in fn:for-each-pair( $seq, fn:tail($seq), function($a, $b) { $a le $b } ) satisfies $b } return ( $is-sorted(1 to 10), $is-sorted((1, 2, 42, 4, 5)) ) </syntaxhighlight> Result: true false
XQuery 1.0 <syntaxhighlight lang="xquery">

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])

}; </syntaxhighlight>

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

<syntaxhighlight lang="java"> public int product(int[] seq) {

 int result = 1;
 for(int i : seq) {
   result = result * i;
 }
 return result;

} </syntaxhighlight>

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

Signatures fn:fold-left($seq as item()*, $seed as item()*, $function as function(item()*, item()) as item()*) as item()*
Summary The left fold traverses the sequence from the left.

The query fn:fold-left(1 to 5, 0, $f) for example would be evaluated as: <syntaxhighlight lang="xquery"> $f($f($f($f($f(0, 1), 2), 3), 4), 5) </syntaxhighlight>

Examples
  • Product of a sequence of integers:

    <syntaxhighlight lang="xquery"> fn:fold-left(1 to 5, 1,

     function($result, $curr) { $result * $curr }
    

    ) </syntaxhighlight> Result: 120

  • Illustrating the evaluation order: <syntaxhighlight lang="xquery"> fn:fold-left(1 to 5, '$seed', concat('$f(', ?, ', ', ?, ')') ) </syntaxhighlight> Result: $f($f($f($f($f($seed, 1), 2), 3), 4), 5)
  • Building a decimal number from digits: <syntaxhighlight lang="xquery"> let $from-digits := fold-left(?, 0, function($n, $d) { 10 * $n + $d } ) return ( $from-digits(1 to 5), $from-digits((4, 2)) ) </syntaxhighlight> Result: 12345 42
XQuery 1.0 As folds are more general than FLWOR expressions, the implementation isn't as concise as the former ones:

<syntaxhighlight lang="xquery"> declare function local:fold-left(

 $seq as item()*,
 $seed as item()*,
 $function as function(item()*, item()) as item()*

) as item()* {

 if(empty($seq)) then $seed
 else local:fold-left(
   fn:tail($seq),
   $function($seed, fn:head($seq)),
   $function
 ) 

}; </syntaxhighlight>

fn:fold-right

Signatures fn:fold-right($seq as item()*, $seed as item()*, $function as function(item(), item()*) as item()*) as item()*
Summary The right fold fn:fold-right($seq, $seed, $fun) traverses the sequence from the right.

The query fn:fold-right(1 to 5, 0, $f) for example would be evaluated as: <syntaxhighlight lang="xquery"> $f(1, $f(2, $f(3, $f(4, $f(5, 0))))) </syntaxhighlight>

Examples
  • Product of a sequence of integers:

    <syntaxhighlight lang="xquery"> fn:fold-right(1 to 5, 1,

     function($curr, $result) { $result * $curr }
    

    ) </syntaxhighlight> Result: 120

  • Illustrating the evaluation order: <syntaxhighlight lang="xquery"> fn:fold-right(1 to 5, '$seed', concat('$f(', ?, ', ', ?, ')') ) </syntaxhighlight> Result: $f(1, $f(2, $f(3, $f(4, $f(5, $seed)))))
  • Reversing a sequence of items: <syntaxhighlight lang="xquery"> let $reverse := fn:fold-right(?, (), function($item, $rev) { $rev, $item } ) return $reverse(1 to 10) </syntaxhighlight> Result: 10 9 8 7 6 5 4 3 2 1
XQuery 1.0 <syntaxhighlight lang="xquery">

declare function local:fold-right(

 $seq as item()*,
 $seed as item()*,
 $function as function(item(), item()*) as item()*

) as item()* {

 if(empty($seq)) then $seed
 else $function(
   fn:head($seq),
   local:fold-right(tail($seq), $seed, $function)
 )

}; </syntaxhighlight> Note that the order of the arguments of $fun are inverted compared to that in fn:fold-left(...).