Bureaucrats, editor, reviewer, Administrators
13,550
edits
Changes
Jump to navigation
Jump to search
{{Mark|Updated with Version 7.7:}} the function has been renamed, and the arguments have been swapped.<br/>
{{Mark|Updated with Version 7.7:}} the arguments have been swapped.<br/>
{{Mark|Updated with Version 7.7:}} the function has been renamed, and the arguments have been swapped.<br/>
$f as function(item(), item()) as item()*,
===fn:fold-left($f, $seed, $seq)===
return $product(1 to 5)</presyntaxhighlight>
return $product(1 to 5)</presyntaxhighlight>
[[Category:XQuery]]
no edit summary
This page talks about present some ''higher-order functions'' introduced with [[of the XQuery 3.0]]specification. The BaseX-specific <code>hof</code> module containing some more very usful functions can be found at [[Higher-Order Functions Module]]. {{Version|7.7}}: In the upcoming version of the [http://www.w3.org/TR/xpath-functions-30 XQuery Functions and Operators] specification, contains some additional useful functions have been modified! Function arguments are now placed last in the function signature.
=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 . 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 classsyntaxhighlight lang="brush:xquery">
for $item in (1, 'foo', fn:concat#3, function($a) { 42 * $a })
where $item instance of function(*)
return fn:function-arity($item)
</presyntaxhighlight>
''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 classsyntaxhighlight lang="brush:xquery">
declare function local:char-at(
$str as xs:string,
fn:substring($str, $pos, 1)
};
</presyntaxhighlight>
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 classsyntaxhighlight lang="brush:xquery">
declare function local:on-sequences(
$f fun as function(item()) as item()*
) as function(item()*) as item()* {
fn:for-each($ffun, ?)
};
</presyntaxhighlight> 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===
{|
|-
| width='90120' | '''Signatures'''|<code><b>{{Func|fn:for-each</b>(|$seq as item()*, $fun as function(item()) as item()*) as item()*</code><br/><font color='gray'>Old signature: fn:map($fun as function(item()) as item()*, $seq as item()*) as |item()*</font>}}
|-
| '''Summary'''
|Applies the function item specified <code>$funfunction</code> to every element item of the sequence <code>$seq</code> and returns all of the results as a single sequence.
|-
| '''Examples'''
|
<ul><li>Squaring Square all numbers from 1 to 10: <pre classsyntaxhighlight lang="brush:xquery">
fn:for-each(1 to 10, math:pow(?, 2))
</presyntaxhighlight>
''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 classsyntaxhighlight lang="brush:xquery">
let $fs := (
fn:upper-case#1,
)
return fn:for-each($fs, function($f) { $f('foobar') })
</presyntaxhighlight>
''Result:'' <code>FOOBAR bar 6</code>
</li>
<li>Process each item of a sequence with the arrow operator:
<syntaxhighlight lang="xquery">
("one", "two", "three") => fn:for-each(fn:upper-case(?))
</syntaxhighlight>
''Result:'' <code>ONE TWO THREE</code>
</li></ul>
|-
| '''XQuery 1.0'''
|At the core, for-each is nothing else than a simple FLWOR expression:<pre classsyntaxhighlight lang="brush:xquery">
declare function local:for-each(
$seq as item()*,
$fun as function(item()) as item()*
) as item()* {
for $x s in $seq return $fun($seqs)
};
</presyntaxhighlight>
|}
===fn:filter===
{|
|-
| width='90120' | '''Signatures'''|<code><b>{{Func|fn:filter</b>(|$seq as item()*, $pred as function(item()) as xs:boolean) as item()*</code><br /><font color='gray'>fn:filter($pred as function(item()) as xs:boolean, $seq as item()*) as |item()*</font>}}
|-
| '''Summary'''
| '''Examples'''
|<ul><li>All even integers until 10:
<pre classsyntaxhighlight lang="brush:xquery">
fn:filter(1 to 10, function($x) { $x mod 2 eq 0 })
</presyntaxhighlight>
''Result:'' <code>2 4 6 8 10</code>
</li>
<li>Strings that start with an upper-case letter:
<pre classsyntaxhighlight lang="brush:xquery">
let $first-upper := function($str) {
let $first := fn:substring($str, 1, 1)
}
return fn:filter(('FooBar', 'foo', 'BAR'), $first-upper)
</presyntaxhighlight>
''Result:'' <code>FooBar BAR</code>
</li>
<li>Inefficient prime number generator:
<pre classsyntaxhighlight lang="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(1 to 20, $is-prime)
</presyntaxhighlight>
''Result:'' <code>2 3 5 7 11 13 17 19</code>
</li></ul>
| '''Note'''
|<code>fn:filter</code> can be easily implemented with <code>fn:for-each</code>:
<pre classsyntaxhighlight lang="brush:xquery">
declare function local:filter($seq, $pred) {
for-each(
)
};
</presyntaxhighlight>
|-
| '''XQuery 1.0'''
|At the core, for-each is nothing else than a filter expression:<pre classsyntaxhighlight lang="brush:xquery">
declare function local:filter(
$seq as item()*,
$seq[$pred(.)]
};
</presyntaxhighlight>
|}
===fn:for-each-pair===
{|
|-
| width='90120' | '''Signatures'''|<code><b>{{Func|fn:for-each-pair</b>(|$seq1 as item()*, $seq2 as item()*, $f as function(item(), item()) as item()*) as item()*</code><br /><font color='gray'>Old signature: fn:map-pairs($f as function(item(), item()) as item()*, $seq1 as item()*, $seq2 as item()*) as |item()*</font>}}
|-
| '''Summary'''
|''zips'' Applies the elements from specified {{Code|$function}} to the two sequences successive pairs of items of <code>$seq1</code> and <code>$seq2</code> together with the function <code>$f</code>. It stops after the shorter Evaluation is stopped if one sequence endsyields no more items.
|-
| '''Examples'''
|<ul><li>Adding one to the numbers at odd positions:
<pre classsyntaxhighlight lang="brush: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 },
)
</presyntaxhighlight>
''Result:'' <code>2 1 2 1 2</code>
</li>
<li>Line numbering:
<pre classsyntaxhighlight lang="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?')</presyntaxhighlight>
''Result:''
<presyntaxhighlight lang="xquery">1: hello world,how2: how are 3: you?</presyntaxhighlight>
</li>
<li>Checking if a sequence is sorted:
<pre classsyntaxhighlight lang="brush:xquery">
let $is-sorted := function($seq) {
every $b in
$is-sorted((1, 2, 42, 4, 5))
)
</presyntaxhighlight>
''Result:'' <code>true false</code></li></ul>
|-
| '''XQuery 1.0'''
|<pre classsyntaxhighlight lang="brush: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(length(count($seq1), lengthcount($seq2))) return $ffun($seq1[$pos], $seq2[$pos])
};
</presyntaxhighlight>
|}
== 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 with 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 classsyntaxhighlight lang="brush:java">
public int product(int[] seq) {
int result = 1;
return result;
}
</presyntaxhighlight>
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===
{|
|-
| width='90120' | '''Signatures'''|<code><b>{{Func|fn:fold-left</b>(|$f seq as function(item()*, item()) $seed as item()*, $seed function as function(item()*, $seq item()) as item()*) as |item()*</code><br />}}
|-
| '''Summary'''
|The ''left fold'' traverses the sequence from the left.
The query <code>fn:fold-left($f1 to 5, 0, 1 to 5$f)</code> for example would be evaluated as:<pre classsyntaxhighlight lang="brush:xquery">
$f($f($f($f($f(0, 1), 2), 3), 4), 5)
</presyntaxhighlight>
|-
| '''Examples'''
|<ul><li>Product of a sequence of integers:
<pre classsyntaxhighlight lang="brush:xquery">let $product := fn:fold-left(1 to 5, 1, function($result, $icurr) { $result * $i curr }, 1, ?
)
''Result:'' <code>120</code>
</li>
<li>Illustrating the evaluation order:
<pre classsyntaxhighlight lang="brush:xquery">fn:fold-left(1 to 5, '$seed', concat('$f(', ?, ', ', ?, ')'), '$seed', 1 to 5
)
</presyntaxhighlight>
''Result:'' <code>$f($f($f($f($f($seed, 1), 2), 3), 4), 5)</code>
</li>
<li>Building a decimal number from digits:
<pre classsyntaxhighlight lang="brush:xquery">let $from-digits := fold-left(?, 0, function($n, $d) { 10 * $n + $d }, 0, ?
)
return (
$from-digits((4, 2))
)
</presyntaxhighlight>
''Result:'' <code>12345 42</code>
</li></ul>
| '''XQuery 1.0'''
|As folds are more general than ''FLWOR'' expressions, the implementation isn't as concise as the former ones:
<pre classsyntaxhighlight lang="brush:xquery">
declare function local:fold-left(
$f as function(item()*, item()) seq as item()*,
$seed as item()*,
$seq function as function(item()*, item()) as item()*
) as item()* {
if(empty($seq)) then $seed
else local:fold-left(
fn:tail($fseq), $ffunction($seed, fn:head($seq)), fn:tail($seq)function
)
};
</presyntaxhighlight>
|}
===fn:fold-right($f, $seed, $seq)===
{|
|-
| width='90120' | '''Signatures'''|<code><b>{{Func|fn:fold-right</b>(|$f seq as function(item()*, $seed as item()*) , $function as function(item()*, $seed as item()*, $seq ) as item()*) as |item()*</code><br />}}
|-
| '''Summary'''
|The ''right fold'' <code>fn:fold-right($fseq, $seed, $seqfun)</code> traverses the sequence from the right.The query <code>fn:fold-right($f1 to 5, 0, 1 to 5$f)</code> for example would be evaluated as:<pre classsyntaxhighlight lang="brush:xquery">
$f(1, $f(2, $f(3, $f(4, $f(5, 0)))))
</presyntaxhighlight>
|-
| '''Examples'''
|<ul><li>Product of a sequence of integers:
<pre classsyntaxhighlight lang="brush:xquery">let $product := fn:fold-right(1 to 5, 1, function($icurr, $result) { $result * $i curr }, 1, ?
)
''Result:'' <code>120</code>
</li>
<li>Illustrating the evaluation order:
<pre classsyntaxhighlight lang="brush:xquery">fn:fold-right(1 to 5, '$seed', concat('$f(', ?, ', ', ?, ')'), '$seed', 1 to 5
)
</presyntaxhighlight>
''Result:'' <code>$f(1, $f(2, $f(3, $f(4, $f(5, $seed)))))</code>
</li>
<li>Reversing a sequence of items:
<pre classsyntaxhighlight lang="brush:xquery">let $reverse := fn:fold-right(?, (),
function($item, $rev) {
$rev, $item
}, (), ?
)
return $reverse(1 to 10)
</presyntaxhighlight>
''Result:'' <code>10 9 8 7 6 5 4 3 2 1</code>
</li></ul>
|-
| '''XQuery 1.0'''
|<pre classsyntaxhighlight lang="brush:xquery">
declare function local:fold-right(
$f as function(item(), item()*) seq as item()*,
$seed as item()*,
$seq function as function(item(), item()*) as item()*
) as item()* {
if(empty($seq)) then $seed
else $ffunction(
fn:head($seq),
local:fold-right(tail($fseq), $seed, tail($seq)function)
)
};
</presyntaxhighlight>Note that the order of the arguments of <code>$ffun</code> are inverted compared to that in <code>fn:fold-left(...)</code>.
|}
