Bureaucrats, editor, reviewer, Administrators
13,554
edits
Changes
Jump to navigation
Jump to search
m
fn:tail($seq),
fn:tail($seqinput), $funaction($seedzero, fn:head($seqinput)), $funaction
Text replacement - "syntaxhighlight" to "pre"
This page talks about present some ''higher-order functions'' introduced with [[of the XQuery 3.0]]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#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 beused to specify the ''arity'' (number of arguments the function takes) andthe argument and result types.
The most general function type is <code>function(*)</code>. It's the type of allfunction items. The following query for example goes through a list of XQueryitems and, if it is a function item, prints its arity:
<pre classlang="brush:'xquery"'>
for $item in (1, 'foo', fn:concat#3, function($a) { 42 * $a })
where $item instance of function(*)
''Result:'' <code>3 1</code>
The notation for specifying argument and return types is quite intuitive, as itclosely resembles the function declaration. The XQuery function
<pre classlang="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 resulttype or the other way round. A good place-holder to use when no restrictionis 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 classlang="brush:'xquery"'>
declare function local:on-sequences(
$fun as function(item()) as item()*
};
</pre>
We'll 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>.
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''behaviourbehavior'' and abstract them into a library function.
== Higher-Order Functions on Sequences ==
Some usage patterns on sequences are so common that the higher-order functionsdescribing them are in the XQuery standard libraries. They are listed here, togetherwith their possible XQuery implementation and some motivating examples.
===fn:for-each===
{|
|-valign="top"| width='120' | '''SignaturesSignature'''|{{Func|<pre>fn:for-each|( $seq input as item()*, $fun action as function(item()) as item()*)|as item()*}}</pre>|-valign="top"
| '''Summary'''
|Applies the function item specified <code>$funaction</code> to every element item of the sequence <code>$seqinput</code> and returns all of the results as a single sequence.|-valign="top"
| '''Examples'''
|
<ul><li>Squaring Square all numbers from 1 to 10: <pre classlang="brush:'xquery"'>
fn:for-each(1 to 10, math:pow(?, 2))
</pre>
''Result:'' <code>1 4 9 16 25 36 49 64 81 100</code>
</li>
<li>Applying Apply a list of functions to a string:<pre classlang="brush:'xquery"'>
let $fs := (
fn:upper-case#1,
</pre>
''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>
|-valign="top"
| '''XQuery 1.0'''
|At the core, for-each is nothing else than a simple FLWOR expression:
<pre classlang="brush:'xquery"'>
declare function local:for-each(
$seq as item()*,
{|
|-valign="top"| width='120' | '''SignaturesSignature'''|{{Func|<pre>fn:filter|( $seq input as item()*, $pred predicate as function(item()) as xs:boolean)|as item()*}}</pre>|-valign="top"
| '''Summary'''
|Applies the boolean predicate <code>$predpredicate</code> to all elements of the sequence <code>$seqinput</code>, returning those for which it returns <code>true()</code>.|-valign="top"
| '''Examples'''
|<ul><li>All even integers until 10:
<pre classlang="brush:'xquery"'>
fn:filter(1 to 10, function($x) { $x mod 2 eq 0 })
</pre>
</li>
<li>Strings that start with an upper-case letter:
<pre classlang="brush:'xquery"'>
let $first-upper := function($str) {
let $first := fn:substring($str, 1, 1)
</li>
<li>Inefficient prime number generator:
<pre classlang="brush:'xquery"'>
let $is-prime := function($x) {
$x gt 1 and (every $y in 2 to ($x - 1) satisfies $x mod $y ne 0)
''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:for-each</code>:
<pre classlang="brush:'xquery"'>
declare function local:filter($seq, $pred) {
for-each(
};
</pre>
|-valign="top"
| '''XQuery 1.0'''
|At the core, for-each is nothing else than a filter expression:
<pre classlang="brush:'xquery"'>
declare function local:filter(
$seq as item()*,
{|
|-valign="top"| width='120' | '''SignaturesSignature'''|{{Func|<pre>fn:for-each-pair|( $seq1 input1 as item()*, $seq2 input2 as item()*, $fun action as function(item(), item()) as item()*|) as item()*}}</pre>|-valign="top"
| '''Summary'''
|''zips'' Applies the elements from specified {{Code|$action}} to the two sequences successive pairs of items of <code>$seq1input1</code> and <code>$seq2</code> together with the function <code>$finput2</code>. It stops after the shorter Evaluation is stopped if one sequence endsyields no more items.|-valign="top"
| '''Examples'''
|<ul><li>Adding one to the numbers at odd positions:
<pre classlang="brush:'xquery"'>
fn:for-each-pair(
fn:for-each(1 to 10, function($x) { $x mod 2 }),
</li>
<li>Line numbering:
<pre classlang="brush:'xquery"'>let $number-lines words := function($str) {
fn:string-join(
fn:for-each-pair(
1 to 10001000000000, tokenize($str, '\r?\n|\r+'),
concat(?, ': ', ?)
),
'&#xa;'
)
}
return $number-lineswords('hello world, how are you?')
</pre>
''Result:''
<pre classlang="brush:'xquery"'>1: hello world,how2: how are 3: you?
</pre>
</li>
<li>Checking if a sequence is sorted:
<pre classlang="brush:'xquery"'>
let $is-sorted := function($seq) {
every $b in
fn:for-each-pair(
$seq,
function($a, $b) { $a le $b }
)
</pre>
''Result:'' <code>true false</code></li></ul>
|-valign="top"
| '''XQuery 1.0'''
|<pre classlang="brush:'xquery"'>
declare function local:for-each-pair(
$seq1 as item()*,
== Folds ==
A ''fold'', also called ''reduce'' or ''accumulate'' in other languages, is a verybasic higher-order function on sequences. It starts from a seed value and incrementallybuilds up a result, consuming one element from the sequence at a time and combining it withthe 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 updatingthe 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 classlang="brush:java">
public int product(int[] seq) {
int result = 1;
}
</pre>
Nice and efficient implementations using folds will be given below.
The ''linear'' folds on sequences come in two flavoursflavors. They differ in the direction in which they traverse the sequence:
===fn:fold-left===
{|
|-valign="top"| width='120' | '''SignaturesSignature'''|{{Func|<pre>fn:fold-left|( $seq input as item()*, $seed zero as item()*, $fun action as function(item()*, item()) as item()*|) as item()*}}</pre>|-valign="top"
| '''Summary'''
|The ''left fold'' traverses the sequence {{Code|$input}} from the left.The query <code>fn:fold-left(1 to 5, 0, $f)</code> , for example , would be evaluated as:<pre classlang="brush:'xquery"'>
$f($f($f($f($f(0, 1), 2), 3), 4), 5)
</pre>
|-valign="top"
| '''Examples'''
|<ul><li>Product of a sequence of integers:
<pre classlang="brush:'xquery"'>
fn:fold-left(1 to 5, 1,
function($result, $curr) { $result * $curr }
</li>
<li>Illustrating the evaluation order:
<pre classlang="brush:'xquery"'>
fn:fold-left(1 to 5, '$seed',
concat('$f(', ?, ', ', ?, ')')
</li>
<li>Building a decimal number from digits:
<pre classlang="brush:'xquery"'>
let $from-digits := fold-left(?, 0,
function($n, $d) { 10 * $n + $d }
''Result:'' <code>12345 42</code>
</li></ul>
|-valign="top"
| '''XQuery 1.0'''
|As folds are more general than ''FLWOR'' expressions, the implementation isn't as concise as the former ones:
<pre classlang="brush:'xquery"'>
declare function local:fold-left(
$seq input as item()*, $seed zero as item()*, $fun action as function(item()*, item()) as item()*
) as item()* {
if(empty($seqinput)) then $seedzero
else local:fold-left(
)
};
{|
|-valign="top"| width='120' | '''SignaturesSignature'''|{{Func|<pre>fn:fold-right|( $seq input as item()*, $seed zero as item()*, $fun action as function(item(), item()*) as item()*|) as item()*}}</pre>|-valign="top"
| '''Summary'''
|The ''right fold'' <code>fn:fold-right($seq, $seed, $fun)</code> traverses the sequence {{Code|$input}} from the right.The query <code>fn:fold-right(1 to 5, 0, $f)</code> , for example , would be evaluated as:<pre classlang="brush:'xquery"'>
$f(1, $f(2, $f(3, $f(4, $f(5, 0)))))
</pre>
|-valign="top"
| '''Examples'''
|<ul><li>Product of a sequence of integers:
<pre classlang="brush:'xquery"'>
fn:fold-right(1 to 5, 1,
function($curr, $result) { $result * $curr }
</li>
<li>Illustrating the evaluation order:
<pre classlang="brush:'xquery"'>
fn:fold-right(1 to 5, '$seed',
concat('$f(', ?, ', ', ?, ')')
</li>
<li>Reversing a sequence of items:
<pre classlang="brush:'xquery"'>
let $reverse := fn:fold-right(?, (),
function($item, $rev) {
''Result:'' <code>10 9 8 7 6 5 4 3 2 1</code>
</li></ul>
|-valign="top"
| '''XQuery 1.0'''
|<pre classlang="brush:'xquery"'>
declare function local:fold-right(
$seq input as item()*, $seed zero as item()*, $fun action as function(item(), item()*) as item()*
) as item()* {
if(empty($seqinput)) then $seedzero else $funaction( fn:head($seqinput), local:fold-right(tail($seqinput), $seedzero, $funaction)
)
};
