Difference between revisions of "Higher-Order Functions"
Tags: Mobile web edit Mobile edit |
m (Text replacement - "</syntaxhighlight>" to "</pre>") |
||
Line 15: | Line 15: | ||
where $item instance of function(*) | where $item instance of function(*) | ||
return fn:function-arity($item) | return fn:function-arity($item) | ||
− | </ | + | </pre> |
''Result:'' <code>3 1</code> | ''Result:'' <code>3 1</code> | ||
Line 27: | Line 27: | ||
fn:substring($str, $pos, 1) | 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 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 39: | Line 39: | ||
fn:for-each($fun, ?) | fn:for-each($fun, ?) | ||
}; | }; | ||
− | </ | + | </pre> |
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 73: | Line 73: | ||
<syntaxhighlight lang="xquery"> | <syntaxhighlight lang="xquery"> | ||
fn:for-each(1 to 10, math:pow(?, 2)) | fn:for-each(1 to 10, math:pow(?, 2)) | ||
− | </ | + | </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> | ||
Line 84: | Line 84: | ||
) | ) | ||
return fn:for-each($fs, function($f) { $f('foobar') }) | return fn:for-each($fs, function($f) { $f('foobar') }) | ||
− | </ | + | </pre> |
''Result:'' <code>FOOBAR bar 6</code> | ''Result:'' <code>FOOBAR bar 6</code> | ||
</li> | </li> | ||
Line 90: | Line 90: | ||
<syntaxhighlight lang="xquery"> | <syntaxhighlight lang="xquery"> | ||
("one", "two", "three") => fn:for-each(fn:upper-case(?)) | ("one", "two", "three") => fn:for-each(fn:upper-case(?)) | ||
− | </ | + | </pre> |
''Result:'' <code>ONE TWO THREE</code> | ''Result:'' <code>ONE TWO THREE</code> | ||
</li></ul> | </li></ul> | ||
Line 104: | Line 104: | ||
return $fun($s) | return $fun($s) | ||
}; | }; | ||
− | </ | + | </pre> |
|} | |} | ||
Line 124: | Line 124: | ||
<syntaxhighlight lang="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> |
''Result:'' <code>2 4 6 8 10</code> | ''Result:'' <code>2 4 6 8 10</code> | ||
</li> | </li> | ||
Line 134: | Line 134: | ||
} | } | ||
return fn:filter(('FooBar', 'foo', 'BAR'), $first-upper) | return fn:filter(('FooBar', 'foo', 'BAR'), $first-upper) | ||
− | </ | + | </pre> |
''Result:'' <code>FooBar BAR</code> | ''Result:'' <code>FooBar BAR</code> | ||
</li> | </li> | ||
Line 143: | Line 143: | ||
} | } | ||
return filter(1 to 20, $is-prime) | return filter(1 to 20, $is-prime) | ||
− | </ | + | </pre> |
''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 158: | Line 158: | ||
) | ) | ||
}; | }; | ||
− | </ | + | </pre> |
|- valign="top" | |- valign="top" | ||
| '''XQuery 1.0''' | | '''XQuery 1.0''' | ||
Line 169: | Line 169: | ||
$seq[$pred(.)] | $seq[$pred(.)] | ||
}; | }; | ||
− | </ | + | </pre> |
|} | |} | ||
Line 194: | Line 194: | ||
function($a, $b) { $a + $b } | function($a, $b) { $a + $b } | ||
) | ) | ||
− | </ | + | </pre> |
''Result:'' <code>2 1 2 1 2</code> | ''Result:'' <code>2 1 2 1 2</code> | ||
</li> | </li> | ||
Line 210: | Line 210: | ||
} | } | ||
return $number-words('how are you?') | return $number-words('how are you?') | ||
− | </ | + | </pre> |
''Result:'' | ''Result:'' | ||
<syntaxhighlight lang="xquery"> | <syntaxhighlight lang="xquery"> | ||
Line 216: | Line 216: | ||
2: are | 2: are | ||
3: you? | 3: you? | ||
− | </ | + | </pre> |
</li> | </li> | ||
<li>Checking if a sequence is sorted: | <li>Checking if a sequence is sorted: | ||
Line 233: | Line 233: | ||
$is-sorted((1, 2, 42, 4, 5)) | $is-sorted((1, 2, 42, 4, 5)) | ||
) | ) | ||
− | </ | + | </pre> |
''Result:'' <code>true false</code></li></ul> | ''Result:'' <code>true false</code></li></ul> | ||
|- valign="top" | |- valign="top" | ||
Line 246: | Line 246: | ||
return $fun($seq1[$pos], $seq2[$pos]) | return $fun($seq1[$pos], $seq2[$pos]) | ||
}; | }; | ||
− | </ | + | </pre> |
|} | |} | ||
Line 265: | Line 265: | ||
return result; | return result; | ||
} | } | ||
− | </ | + | </pre> |
Nice and efficient implementations using folds will be given below. | Nice and efficient implementations using folds will be given below. | ||
Line 287: | Line 287: | ||
<syntaxhighlight lang="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> |
|- valign="top" | |- valign="top" | ||
| '''Examples''' | | '''Examples''' | ||
Line 295: | Line 295: | ||
function($result, $curr) { $result * $curr } | function($result, $curr) { $result * $curr } | ||
) | ) | ||
− | </ | + | </pre> |
''Result:'' <code>120</code> | ''Result:'' <code>120</code> | ||
</li> | </li> | ||
Line 303: | Line 303: | ||
concat('$f(', ?, ', ', ?, ')') | concat('$f(', ?, ', ', ?, ')') | ||
) | ) | ||
− | </ | + | </pre> |
''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> | ||
Line 315: | Line 315: | ||
$from-digits((4, 2)) | $from-digits((4, 2)) | ||
) | ) | ||
− | </ | + | </pre> |
''Result:'' <code>12345 42</code> | ''Result:'' <code>12345 42</code> | ||
</li></ul> | </li></ul> | ||
Line 334: | Line 334: | ||
) | ) | ||
}; | }; | ||
− | </ | + | </pre> |
|} | |} | ||
Line 353: | Line 353: | ||
<syntaxhighlight lang="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> |
|- valign="top" | |- valign="top" | ||
| '''Examples''' | | '''Examples''' | ||
Line 361: | Line 361: | ||
function($curr, $result) { $result * $curr } | function($curr, $result) { $result * $curr } | ||
) | ) | ||
− | </ | + | </pre> |
''Result:'' <code>120</code> | ''Result:'' <code>120</code> | ||
</li> | </li> | ||
Line 369: | Line 369: | ||
concat('$f(', ?, ', ', ?, ')') | concat('$f(', ?, ', ', ?, ')') | ||
) | ) | ||
− | </ | + | </pre> |
''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> | ||
Line 380: | Line 380: | ||
) | ) | ||
return $reverse(1 to 10) | return $reverse(1 to 10) | ||
− | </ | + | </pre> |
''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> | ||
Line 397: | Line 397: | ||
) | ) | ||
}; | }; | ||
− | </ | + | </pre> |
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 18:30, 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.
Contents
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)
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)
};
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, ?)
};
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
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 |
|
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) }; |
fn:filter
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 |
|
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 () } ) }; |
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(.)] }; |
fn:for-each-pair
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 |
|
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]) }; |
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;
}
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
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 |
Examples |
|
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( $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
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 |
Examples |
|
XQuery 1.0 | <syntaxhighlight lang="xquery">
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 |