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/>
===fn:fold-left($f, $seed, $seq)===
let $product := fn:fold-left(1 to 5, 1, function($result, $icurr) { $result * $i curr }, 1, ?
return $product(1 to 5)
let $product := fn:fold-right(1 to 5, 1, function($icurr, $result) { $result * $i curr }, 1, ?
return $product(1 to 5)
[[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 class="brush:xquery">
''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 class="brush:xquery">
</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 class="brush:xquery">
declare function local:on-sequences(
$f fun as function(item()) as item()*
) as function(item()*) as item()* {
fn:for-each($ffun, ?)
};
</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===
{|
|-
| width='90120' | '''Signatures'''|<code><b>{{Func|fn:for-each</b>(|$seq as item()*, $f as function(item()) as item()*) as item()*</code><br/><font color='gray'>Old signature: fn:map($f as function(item()) as item()*, $seq as item()*) as |item()*</font>}}
|-
| '''Summary'''
|Applies the function item specified <code>$ffunction</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 class="brush:xquery">
fn:for-each(1 to 10, math:pow(?, 2))
''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 class="brush:xquery">
let $fs := (
</pre>
''Result:'' <code>FOOBAR bar 6</code>
</li>
<li>Process each item of a sequence with the arrow operator:
<pre class="brush:xquery">
("one", "two", "three") => fn:for-each(fn:upper-case(?))
</pre>
''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 class="brush:xquery">declare function local:mapfor-each( $f as function(item()) seq as item()*, $seq fun as function(item()) as item()*
) as item()* {
for $x s in $seq return $ffun($seqs)
};
</pre>
===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'''
|<code>fn:filter</code> can be easily implemented with <code>fn:for-each</code>:
<pre class="brush:xquery">
declare function local:filter($predseq, $seqpred) {
for-each(
$seq,
|-
| '''XQuery 1.0'''
|At the core, for-each is nothing else than a filter expression:<pre class="brush:xquery">
declare function local:filter(
$seq as item()*, $pred as function(item()) as xs:boolean, $seq as item()*
) as item()* {
$seq[$pred(.)]
===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'''
fn:for-each(1 to 10, function($x) { $x mod 2 }),
(1, 1, 1, 1, 1),
function($a, $b) { $a + $b },
)
</pre>
<li>Line numbering:
<pre class="brush:xquery">
let $number-lines words := function($str) {
fn:string-join(
fn:mapfor-pairseach-pair( 1 to 10001000000000, tokenize($str, '\r?\n|\r+'),
concat(?, ': ', ?)
),
'&#xa;'
)
}
return $number-lineswords( 'hello world, how are you?')
</pre>
''Result:''
<preclass="brush:xquery">1: hello world,how2: how are 3: you?
</pre>
</li>
let $is-sorted := function($seq) {
every $b in
fn:mapfor-pairseach-pair(
$seq,
fn:tail($seq),
| '''XQuery 1.0'''
|<pre class="brush:xquery">
declare function local:mapfor-pairs( $f as function(item(), item()) as itemeach-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])
};
</pre>
== 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 class="brush:java">
public int product(int[] seq) {
}
</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===
{|
|-
| 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 class="brush:xquery">
$f($f($f($f($f(0, 1), 2), 3), 4), 5)
|<ul><li>Product of a sequence of integers:
<pre class="brush:xquery">
)
</pre>
''Result:'' <code>120</code>
<li>Illustrating the evaluation order:
<pre class="brush:xquery">
fn:fold-left(1 to 5, '$seed', concat('$f(', ?, ', ', ?, ')'), '$seed', 1 to 5
)
</pre>
<li>Building a decimal number from digits:
<pre class="brush:xquery">
let $from-digits := fold-left(?, 0, function($n, $d) { 10 * $n + $d }, 0, ?
)
return (
<pre class="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
)
};
|}
===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 class="brush:xquery">
$f(1, $f(2, $f(3, $f(4, $f(5, 0)))))
|<ul><li>Product of a sequence of integers:
<pre class="brush:xquery">
)
</pre>
''Result:'' <code>120</code>
<li>Illustrating the evaluation order:
<pre class="brush:xquery">
fn:fold-right(1 to 5, '$seed', concat('$f(', ?, ', ', ?, ')'), '$seed', 1 to 5
)
</pre>
<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 class="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)
)
};
</pre>
Note that the order of the arguments of <code>$ffun</code> are inverted compared to that in <code>fn:fold-left(...)</code>.
|}
