Difference between revisions of "Higher-Order Functions Module"
Jump to navigation
Jump to search
LeoWoerteler (talk | contribs) (Created page with "This module adds some useful higher-order functions that were left out of the official spec. All functions are introduced with the <code>hof:</code> prefix, which is linked to th...") |
m (Text replacement - "<syntaxhighlight lang="xquery">" to "<pre lang='xquery'>") Tags: Mobile web edit Mobile edit |
||
(78 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
− | This | + | This [[Module Library|XQuery Module]] adds some useful higher-order functions, additional to the [[Higher-Order Functions]] provided by the official specification. |
− | + | With {{Announce|Version 11}}, many functions have been removed in favor of new features of XQuery 4: | |
− | |||
{| | {| | ||
− | |- | + | |- valign="top" |
− | | | + | | '''BaseX 10''' |
− | |<code>< | + | | '''XQuery 4''' |
− | |- | + | |- valign="top" |
− | + | | {{Code|hof:drop-while}} | |
− | | | + | | [https://qt4cg.org/specifications/xpath-functions-40/Overview.html#func-drop-while <code>fn:items-starting-where</code>] |
− | |- | + | |- valign="top" |
− | + | | {{Code|hof:id}} | |
− | | | + | | [https://qt4cg.org/specifications/xpath-functions-40/Overview.html#func-identity <code>fn:identity</code>] |
− | + | |- valign="top" | |
+ | | {{Code|hof:until}} | ||
+ | | [https://qt4cg.org/specifications/xpath-functions-40/Overview.html#func-iterate-while <code>fn:iterate-while</code>] | ||
+ | |- valign="top" | ||
+ | | {{Code|hof:take-while}} | ||
+ | | [https://qt4cg.org/specifications/xpath-functions-40/Overview.html#func-take-while <code>fn:items-before</code>] | ||
|} | |} | ||
− | = | + | =Conventions= |
− | + | ||
− | + | All functions in this module are assigned to the <code><nowiki>http://basex.org/modules/hof</nowiki></code> namespace, which is statically bound to the {{Code|hof}} prefix.<br/> | |
− | + | ||
− | + | =Loops= | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==hof:fold-left1== | ==hof:fold-left1== | ||
− | {| | + | |
− | |- | + | {| width='100%' |
− | + | |- valign="top" | |
− | |< | + | | width='120' | '''Signature''' |
− | |- | + | |<pre>hof:fold-left1( |
− | + | $input as item()+, | |
− | |Works the same as [[Higher- | + | $action as function(item()*, item()) as item()* |
− | |- | + | ) as item()*</pre> |
− | + | |- valign="top" | |
− | + | | '''Summary''' | |
− | + | |Works the same as [[Higher-Order Functions#fn:fold-left|fn:fold-left]], but does not need a seed, because the sequence must be non-empty. | |
− | + | |- valign="top" | |
+ | | '''Examples''' | ||
| | | | ||
− | * | + | * {{Code|hof:fold-left1(1 to 10, function($a, $b) { $a + $b })}} returns {{Code|55}}. |
− | * | + | * {{Code|hof:fold-left1((), function($a, $b) { $a + $b })}} throws {{Code|XPTY0004}}, because {{Code|$seq}} has to be non-empty. |
|} | |} | ||
− | ==hof: | + | ==hof:scan-left== |
− | {| | + | |
− | |- | + | {| width='100%' |
− | + | |- valign="top" | |
− | |< | + | | width='120' | '''Signature''' |
− | |- | + | |<pre>hof:scan-left( |
− | + | $input as item()*, | |
− | | | + | $zero as item()*, |
− | |- | + | $action as function(item()*, item()) as item()* |
− | + | ) as item()*</pre> | |
+ | |- valign="top" | ||
+ | | '''Summary''' | ||
+ | |This function is similar to [[Higher-Order Functions#fn:fold-left|fn:fold-left]], but it returns a list of successive reduced values from the left. It is equivalent to: | ||
+ | <pre lang='xquery'> | ||
+ | declare function hof:scan-left($input, $acc, $action) { | ||
+ | if(empty($input)) then $acc else ( | ||
+ | $acc, | ||
+ | hof:scan-left(tail($input), $action($acc, head($input)), $action) | ||
+ | ) | ||
+ | }; | ||
+ | </pre> | ||
+ | |- valign="top" | ||
+ | | '''Examples''' | ||
| | | | ||
− | * | + | * Returns triangular numbers: |
− | + | <pre lang='xquery'> | |
− | <pre | + | hof:scan-left(1 to 10, 0, function($a, $b) { $a + $b }) |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
</pre> | </pre> | ||
− | |||
|} | |} | ||
+ | |||
+ | =Sorting= | ||
==hof:top-k-by== | ==hof:top-k-by== | ||
− | {| | + | |
− | |- | + | {| width='100%' |
− | + | |- valign="top" | |
− | |< | + | | width='120' | '''Signature''' |
− | |- | + | |<pre>hof:top-k-by( |
− | + | $input as item()*, | |
− | |Returns the | + | $key as function(item()) as item(), |
− | <pre | + | $k as xs:integer |
− | ( | + | ) as item()*</pre> |
− | + | |- valign="top" | |
− | + | | '''Summary''' | |
− | + | |Returns the {{Code|$k}} items in {{Code|$input}} that are greatest when sorted by the result of {{Code|$key}} applied to the item. The function is a much more efficient implementation of the following scheme: | |
+ | <pre lang='xquery'> | ||
+ | (for $item in $input | ||
+ | order by $key($item) descending | ||
+ | return $item | ||
)[position() <= $k] | )[position() <= $k] | ||
</pre> | </pre> | ||
− | |- | + | |- valign="top" |
− | + | | '''Examples''' | |
− | |||
− | |||
− | |||
| | | | ||
− | * | + | * {{Code|hof:top-k-by(1 to 1000, hof:id#1, 5)}} returns {{Code|1000 999 998 997 996}} |
− | * | + | * {{Code|hof:top-k-by(1 to 1000, function($x) { -$x }, 3)}} returns {{Code|1 2 3}} |
− | * <code>hof:top-k-by( | + | * <code>hof:top-k-by(<x a='1' b='2' c='3'/>/@*, xs:integer#1, 2)/node-name()</code> returns {{Code|c b}} |
|} | |} | ||
==hof:top-k-with== | ==hof:top-k-with== | ||
− | {| | + | |
− | |- | + | {| width='100%' |
− | + | |- valign="top" | |
− | |< | + | | width='120' | '''Signature''' |
− | |- | + | |<pre>hof:top-k-with( |
− | + | $input as item()*, | |
− | |Returns the | + | $comparator as function(item(), item()) as xs:boolean, |
− | |- | + | $k as xs:integer |
− | | valign= | + | ) as item()*</pre> |
+ | |- valign="top" | ||
+ | | '''Summary''' | ||
+ | |Returns the {{Code|$k}} items in {{Code|$input}} that are greatest when sorted in the order of the ''less-than'' predicate {{Code|$comparator}}. The function is a general version of {{Function||hof:top-k-by}}. | ||
+ | |- valign="top" | ||
+ | | '''Examples''' | ||
+ | | | ||
+ | * {{Code|hof:top-k-with(1 to 1000, function($a, $b) { $a lt $b }, 5)}} returns {{Code|1000 999 998 997 996}} | ||
+ | * {{Code|hof:top-k-with(-5 to 5, function($a, $b) { abs($a) gt abs($b) }, 5)}} returns {{Code|0 1 -1 2 -2}} | ||
+ | |} | ||
+ | |||
+ | =Identity= | ||
+ | |||
+ | ==hof:const== | ||
+ | |||
+ | {| width='100%' | ||
+ | |- valign="top" | ||
+ | | width='120' | '''Signature''' | ||
+ | |<pre>hof:const( | ||
+ | $input as item()*, | ||
+ | $ignore as item()* | ||
+ | ) as item()*</pre> | ||
+ | |- valign="top" | ||
+ | | '''Summary''' | ||
+ | |Returns its first argument unchanged and ignores the second. This function isn’t useful on its own, but can be used as argument to other higher-order functions, e.g., when a function combining two values is expected and one only wants to retain the left one. | ||
+ | |- valign="top" | ||
+ | | '''Examples''' | ||
| | | | ||
− | * < | + | * {{Code|hof:const(42, 1337)}} returns {{Code|42}}. |
− | * < | + | * With higher-order functions: |
+ | <pre lang='xquery'> | ||
+ | let $zip-sum := function($f, $seq1, $seq2) { | ||
+ | sum(for-each-pair($seq1, $seq2, $f)) | ||
+ | } | ||
+ | let $sum-all := $zip-sum(function($a, $b) { $a + $b }, ?, ?) | ||
+ | let $sum-left := $zip-sum(hof:const#2, ?, ?) | ||
+ | return ( | ||
+ | $sum-all((1, 1, 1, 1, 1), 1 to 5), | ||
+ | $sum-left((1, 1, 1, 1, 1), 1 to 5) | ||
+ | ) | ||
+ | </pre> | ||
+ | * Another use-case: When inserting a key into a map, {{Code|$f}} decides how to combine the new value with a possibly existing old one. {{Code|hof:const}} here means ignoring the old value, so that's normal insertion. | ||
+ | <pre lang='xquery'> | ||
+ | let $insert-with := function($f, $map, $k, $v) { | ||
+ | let $old := $map($k) | ||
+ | let $new := if($old) then $f($v, $old) else $v | ||
+ | return map:merge(($map, map:entry($k, $new))) | ||
+ | } | ||
+ | let $map := map { 'foo': 1 } | ||
+ | let $add := $insert-with(function($a, $b) { $a + $b }, ?, ?, ?) | ||
+ | let $ins := $insert-with(hof:const#2, ?, ?, ?) | ||
+ | return ( | ||
+ | $add($map, 'foo', 2)('foo'), | ||
+ | $ins($map, 'foo', 42)('foo') | ||
+ | ) | ||
+ | </pre> | ||
+ | returns {{Code|3 42}} | ||
|} | |} | ||
− | = | + | =Changelog= |
+ | |||
+ | ;Version 11.0 | ||
+ | * Removed: {{Code|hof:until}} (replaced with {{Code|fn:iterate-while}}, {{Code|hof:if}} (replaced with {{Code|fn:identity}}, {{Code|hof:drop-while}} (replaced with {{Code|fn:items-starting-where}}), {{Code|hof:take-while}} (replaced with {{Code|fn:items-before}}) | ||
+ | |||
+ | ;Version 9.5 | ||
+ | * Added: {{Function||hof:drop-while}} | ||
+ | |||
+ | ;Version 8.1 | ||
+ | * Added: {{Function||hof:scan-left}}, {{Function||hof:take-while}} | ||
− | * | + | ;Version 7.2 |
− | + | * Added: {{Function||hof:top-k-by}}, {{Function||hof:top-k-with}} | |
+ | * Removed: hof:iterate | ||
− | + | ;Version 7.0 | |
+ | * module added |
Latest revision as of 18:35, 1 December 2023
This XQuery Module adds some useful higher-order functions, additional to the Higher-Order Functions provided by the official specification.
With Version 11, many functions have been removed in favor of new features of XQuery 4:
BaseX 10 | XQuery 4 |
hof:drop-while
|
fn:items-starting-where
|
hof:id
|
fn:identity
|
hof:until
|
fn:iterate-while
|
hof:take-while
|
fn:items-before
|
Contents
Conventions[edit]
All functions in this module are assigned to the http://basex.org/modules/hof
namespace, which is statically bound to the hof
prefix.
Loops[edit]
hof:fold-left1[edit]
Signature | hof:fold-left1( $input as item()+, $action as function(item()*, item()) as item()* ) as item()* |
Summary | Works the same as fn:fold-left, but does not need a seed, because the sequence must be non-empty. |
Examples |
|
hof:scan-left[edit]
Signature | hof:scan-left( $input as item()*, $zero as item()*, $action as function(item()*, item()) as item()* ) as item()* |
Summary | This function is similar to fn:fold-left, but it returns a list of successive reduced values from the left. It is equivalent to:
declare function hof:scan-left($input, $acc, $action) {
if(empty($input)) then $acc else (
$acc,
hof:scan-left(tail($input), $action($acc, head($input)), $action)
)
};
|
Examples |
hof:scan-left(1 to 10, 0, function($a, $b) { $a + $b })
|
Sorting[edit]
hof:top-k-by[edit]
Signature | hof:top-k-by( $input as item()*, $key as function(item()) as item(), $k as xs:integer ) as item()* |
Summary | Returns the $k items in $input that are greatest when sorted by the result of $key applied to the item. The function is a much more efficient implementation of the following scheme:
(for $item in $input
order by $key($item) descending
return $item
)[position() <= $k]
|
Examples |
|
hof:top-k-with[edit]
Signature | hof:top-k-with( $input as item()*, $comparator as function(item(), item()) as xs:boolean, $k as xs:integer ) as item()* |
Summary | Returns the $k items in $input that are greatest when sorted in the order of the less-than predicate $comparator . The function is a general version of hof:top-k-by .
|
Examples |
|
Identity[edit]
hof:const[edit]
Signature | hof:const( $input as item()*, $ignore as item()* ) as item()* |
Summary | Returns its first argument unchanged and ignores the second. This function isn’t useful on its own, but can be used as argument to other higher-order functions, e.g., when a function combining two values is expected and one only wants to retain the left one. |
Examples |
let $zip-sum := function($f, $seq1, $seq2) {
sum(for-each-pair($seq1, $seq2, $f))
}
let $sum-all := $zip-sum(function($a, $b) { $a + $b }, ?, ?)
let $sum-left := $zip-sum(hof:const#2, ?, ?)
return (
$sum-all((1, 1, 1, 1, 1), 1 to 5),
$sum-left((1, 1, 1, 1, 1), 1 to 5)
)
let $insert-with := function($f, $map, $k, $v) {
let $old := $map($k)
let $new := if($old) then $f($v, $old) else $v
return map:merge(($map, map:entry($k, $new)))
}
let $map := map { 'foo': 1 }
let $add := $insert-with(function($a, $b) { $a + $b }, ?, ?, ?)
let $ins := $insert-with(hof:const#2, ?, ?, ?)
return (
$add($map, 'foo', 2)('foo'),
$ins($map, 'foo', 42)('foo')
)
returns |
Changelog[edit]
- Version 11.0
- Removed:
hof:until
(replaced withfn:iterate-while
,hof:if
(replaced withfn:identity
,hof:drop-while
(replaced withfn:items-starting-where
),hof:take-while
(replaced withfn:items-before
)
- Version 9.5
- Added:
hof:drop-while
- Version 8.1
- Added:
hof:scan-left
,hof:take-while
- Version 7.2
- Added:
hof:top-k-by
,hof:top-k-with
- Removed: hof:iterate
- Version 7.0
- module added