Difference between revisions of "Higher-Order Functions Module"
(43 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
− | This [[Module Library|XQuery Module]] adds some useful higher-order functions, additional to the [[Higher-Order Functions]] provided by the official specification | + | This [[Module Library|XQuery Module]] adds some useful higher-order functions, additional to the [[Higher-Order Functions]] provided by the official specification. |
− | = | + | =Conventions= |
− | ==hof: | + | 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== | ||
+ | |||
+ | {| width='100%' | ||
|- | |- | ||
− | | | + | | width='120' | '''Signatures''' |
− | | | + | |{{Func|hof:fold-left1|$seq as item()+, $f as function(item()*, item()) as item()*|item()*}} |
|- | |- | ||
− | + | | '''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. |
|- | |- | ||
− | + | | '''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:until== |
− | {| | + | |
+ | {| width='100%' | ||
|- | |- | ||
− | | | + | | width='120' | '''Signatures''' |
− | | | + | |{{Func|hof:until|$pred as function(item()*) as xs:boolean, $f as function(item()*) as item()*, $start as item()*|item()*}} |
|- | |- | ||
− | + | | '''Summary''' | |
− | | | + | |Applies the predicate function {{Code|$pred}} to {{Code|$start}}. If the result is {{Code|false}}, {{Code|$f}} is invoked with the start value – or, subsequently, with the result of this function – until the predicate function returns {{Code|true()}}. |
|- | |- | ||
− | + | | '''Examples''' | |
| | | | ||
− | * | + | * Doubles a numeric value until a maximum is reached: |
− | + | <syntaxhighlight lang="xquery"> | |
− | < | + | hof:until( |
− | + | function($output) { $output ge 1000 }, | |
− | + | function($input ) { 2 * $input }, | |
− | + | 1 | |
− | |||
− | |||
− | |||
− | |||
− | |||
) | ) | ||
− | </ | + | </syntaxhighlight> |
− | * | + | * Calculates the square-root of a number by iteratively improving an initial guess: |
− | < | + | <syntaxhighlight lang="xquery"> |
− | let $ | + | let $sqrt := function($input as xs:double) as xs:double { |
− | + | hof:until( | |
− | + | function($result) { abs($result * $result - $input) < 0.00001 }, | |
− | + | function($guess) { ($guess + $input div $guess) div 2 }, | |
− | + | $input | |
− | + | ) | |
− | + | } | |
− | + | return $sqrt(25) | |
− | + | </syntaxhighlight> | |
− | + | * Returns {{Code|OK}}, as the predicate is evaluated first: | |
− | + | <syntaxhighlight lang="xquery"> | |
+ | hof:until( | ||
+ | function($_) { true() }, | ||
+ | function($_) { error() }, | ||
+ | 'OK' | ||
) | ) | ||
− | </ | + | </syntaxhighlight> |
− | |||
|} | |} | ||
− | ==hof: | + | ==hof:scan-left== |
− | {| | + | |
+ | {| width='100%' | ||
|- | |- | ||
− | | | + | | width='120' | '''Signatures''' |
− | | | + | |{{Func|hof:scan-left|$seq as item()*, $start as item()*, $f as function(item()*, item()) as item()*|item()*}} |
|- | |- | ||
− | + | | '''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: |
+ | <syntaxhighlight lang="xquery"> | ||
+ | declare function hof:scan-left($seq, $acc, $f) { | ||
+ | if(empty($seq)) then $acc else ( | ||
+ | $acc, | ||
+ | hof:scan-left(tail($seq), $f($acc, head($seq)), $f) | ||
+ | ) | ||
+ | }; | ||
+ | </syntaxhighlight> | ||
|- | |- | ||
− | + | | '''Examples''' | |
− | |||
− | |||
− | |||
| | | | ||
− | * < | + | * Returns triangular numbers: |
− | + | <syntaxhighlight lang="xquery"> | |
+ | hof:scan-left(1 to 10, 0, function($a, $b) { $a + $b }) | ||
+ | </syntaxhighlight> | ||
|} | |} | ||
− | ==hof: | + | ==hof:take-while== |
− | {| | + | |
+ | {| width='100%' | ||
|- | |- | ||
− | | | + | | width='120' | '''Signatures''' |
− | | | + | |{{Func|hof:take-while|$seq as item()*, $pred as function(item()) as xs:boolean|item()*}} |
|- | |- | ||
− | + | | '''Summary''' | |
− | | | + | |The function returns items of <code>$seq</code> as long as the predicate <code>$pred</code> is satisfied. It is equivalent to: |
+ | <syntaxhighlight lang="xquery"> | ||
+ | declare function hof:take-while($seq, $pred) { | ||
+ | if(empty($seq) or not($pred(head($seq)))) then () else ( | ||
+ | head($seq), | ||
+ | hof:take-while(tail($seq), $pred) | ||
+ | ) | ||
+ | }; | ||
+ | </syntaxhighlight> | ||
|- | |- | ||
− | + | | '''Examples''' | |
| | | | ||
− | * < | + | * Computes at most 100 random integers, but stops if an integer is smaller than 10: |
− | + | <syntaxhighlight lang="xquery"> | |
− | < | + | hof:take-while( |
− | + | (1 to 100) ! random:integer(50), | |
− | + | function($x) { $x >= 10 } | |
− | + | ) | |
− | + | </syntaxhighlight> | |
− | $ | + | |} |
+ | |||
+ | ==hof:drop-while== | ||
+ | |||
+ | {{Mark|Introduced with Version 9.5.}} | ||
+ | |||
+ | {| width='100%' | ||
+ | |- | ||
+ | | width='120' | '''Signatures''' | ||
+ | |{{Func|hof:drop-while|$seq as item()*, $pred as function(item()) as xs:boolean|item()*}} | ||
+ | |- | ||
+ | | '''Summary''' | ||
+ | |The function skips all items of <code>$seq</code> until the predicate <code>$pred</code> is not satisfied anymore. It is equivalent to: | ||
+ | <syntaxhighlight lang="xquery"> | ||
+ | declare function hof:drop-while($seq, $pred) { | ||
+ | if($pred(head($seq))) then ( | ||
+ | hof:drop-while(tail($seq), $pred) | ||
+ | ) else ( | ||
+ | $seq | ||
) | ) | ||
− | } | + | }; |
− | + | </syntaxhighlight> | |
− | </ | + | |- |
− | + | | '''Examples''' | |
+ | |Returns the name of the first file that does not exist on disk: | ||
+ | <syntaxhighlight lang="xquery"> | ||
+ | hof:drop-while( | ||
+ | (1 to 1000) ! (. || '.log'), | ||
+ | file:exists#1 | ||
+ | )[1] | ||
+ | </syntaxhighlight> | ||
|} | |} | ||
+ | |||
+ | =Sorting= | ||
==hof:top-k-by== | ==hof:top-k-by== | ||
− | + | {| width='100%' | |
− | |||
− | {| | ||
|- | |- | ||
− | | | + | | width='120' | '''Signatures''' |
− | | | + | |{{Func|hof:top-k-by|$seq as item()*, $sort-key as function(item()) as item(), $k as xs:integer|item()*}} |
|- | |- | ||
− | + | | '''Summary''' | |
− | |Returns the | + | |Returns the {{Code|$k}} items in {{Code|$seq}} that are greatest when sorted by the result of {{Code|$f}} applied to the item. The function is a much more efficient implementation of the following scheme: |
− | < | + | <syntaxhighlight lang="xquery"> |
− | ( | + | (for $x in $seq |
− | + | order by $sort-key($x) descending | |
− | + | return $x | |
− | |||
)[position() <= $k] | )[position() <= $k] | ||
− | </ | + | </syntaxhighlight> |
+ | |- | ||
+ | | '''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(<x a='1' b='2' c='3'/>/@*, xs:integer#1, 2)/node-name()</code> returns {{Code|c b}} | ||
+ | |} | ||
+ | |||
+ | ==hof:top-k-with== | ||
+ | |||
+ | {| width='100%' | ||
+ | |- | ||
+ | | width='120' | '''Signatures''' | ||
+ | |{{Func|hof:top-k-with|$seq as item()*, $lt as function(item(), item()) as xs:boolean, $k as xs:integer|item()*}} | ||
|- | |- | ||
− | | | + | | '''Summary''' |
− | |'' | + | |Returns the {{Code|$k}} items in {{Code|$seq}} that are greatest when sorted in the order of the ''less-than'' predicate {{Code|$lt}}. The function is a general version of {{Code|hof:top-k-by($seq, $sort-key, $k)}}. |
|- | |- | ||
− | + | | '''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}} |
− | |||
|} | |} | ||
− | ==hof: | + | =IDs= |
+ | |||
+ | ==hof:id== | ||
+ | |||
+ | {| width='100%' | ||
+ | |- | ||
+ | | width='120' | '''Signatures''' | ||
+ | |{{Func|hof:id|$expr as item()*|item()*}} | ||
+ | |- | ||
+ | | '''Summary''' | ||
+ | |Returns its argument unchanged. This function isn’t useful on its own, but can be used as argument to other higher-order functions. | ||
+ | |- | ||
+ | | '''Examples''' | ||
+ | | | ||
+ | * {{Code|hof:id(1 to 5)}} returns {{Code|1 2 3 4 5}} | ||
+ | * With higher-order functions: | ||
+ | <syntaxhighlight lang="xquery"> | ||
+ | let $sort := sort(?, (), hof:id#1) | ||
+ | let $reverse-sort := sort(?, (), function($x) { -$x }) | ||
+ | return ( | ||
+ | $sort((1, 5, 3, 2, 4)), | ||
+ | '|', | ||
+ | $reverse-sort((1, 5, 3, 2, 4)) | ||
+ | ) | ||
+ | </syntaxhighlight> | ||
+ | returns: <code>1 2 3 4 5 | 5 4 3 2 1</code> | ||
+ | |} | ||
− | + | ==hof:const== | |
− | {| | + | {| width='100%' |
|- | |- | ||
− | | | + | | width='120' | '''Signatures''' |
− | | | + | |{{Func|hof:const|$expr as item()*, $ignored as item()*|item()*}} |
|- | |- | ||
− | + | | '''Summary''' | |
− | |Returns the | + | |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''' | |
| | | | ||
− | * < | + | * {{Code|hof:const(42, 1337)}} returns {{Code|42}}. |
− | * < | + | * With higher-order functions: |
+ | <syntaxhighlight 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) | ||
+ | ) | ||
+ | </syntaxhighlight> | ||
+ | * 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. | ||
+ | <syntaxhighlight 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') | ||
+ | ) | ||
+ | </syntaxhighlight> | ||
+ | returns {{Code|3 42}} | ||
|} | |} | ||
=Changelog= | =Changelog= | ||
− | + | ;Version 9.5 | |
+ | * Added: [[#hof:drop-while|hof:drop-while]] | ||
+ | ;Version 8.1 | ||
+ | * Added: [[#hof:scan-left|hof:scan-left]], [[#hof:take-while|hof:take-while]] | ||
+ | |||
+ | ;Version 7.2 | ||
* Added: [[#hof:top-k-by|hof:top-k-by]], [[#hof:top-k-with|hof:top-k-with]] | * Added: [[#hof:top-k-by|hof:top-k-by]], [[#hof:top-k-with|hof:top-k-with]] | ||
− | * Removed: | + | * Removed: hof:iterate |
− | |||
− | |||
+ | ;Version 7.0 | ||
* module added | * module added | ||
− | |||
− |
Revision as of 10:29, 21 August 2020
This XQuery Module adds some useful higher-order functions, additional to the Higher-Order Functions provided by the official specification.
Contents
Conventions
All functions in this module are assigned to the http://basex.org/modules/hof
namespace, which is statically bound to the hof
prefix.
Loops
hof:fold-left1
Signatures | hof:fold-left1($seq as item()+, $f 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:until
Signatures | hof:until($pred as function(item()*) as xs:boolean, $f as function(item()*) as item()*, $start as item()*) as item()*
|
Summary | Applies the predicate function $pred to $start . If the result is false , $f is invoked with the start value – or, subsequently, with the result of this function – until the predicate function returns true() .
|
Examples |
<syntaxhighlight lang="xquery"> hof:until( function($output) { $output ge 1000 }, function($input ) { 2 * $input }, 1 ) </syntaxhighlight>
<syntaxhighlight lang="xquery"> let $sqrt := function($input as xs:double) as xs:double { hof:until( function($result) { abs($result * $result - $input) < 0.00001 }, function($guess) { ($guess + $input div $guess) div 2 }, $input ) } return $sqrt(25) </syntaxhighlight>
<syntaxhighlight lang="xquery"> hof:until( function($_) { true() }, function($_) { error() }, 'OK' ) </syntaxhighlight> |
hof:scan-left
Signatures | hof:scan-left($seq as item()*, $start as item()*, $f 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:
<syntaxhighlight lang="xquery"> declare function hof:scan-left($seq, $acc, $f) { if(empty($seq)) then $acc else ( $acc, hof:scan-left(tail($seq), $f($acc, head($seq)), $f) ) }; </syntaxhighlight> |
Examples |
<syntaxhighlight lang="xquery"> hof:scan-left(1 to 10, 0, function($a, $b) { $a + $b }) </syntaxhighlight> |
hof:take-while
Signatures | hof:take-while($seq as item()*, $pred as function(item()) as xs:boolean) as item()*
|
Summary | The function returns items of $seq as long as the predicate $pred is satisfied. It is equivalent to:
<syntaxhighlight lang="xquery"> declare function hof:take-while($seq, $pred) { if(empty($seq) or not($pred(head($seq)))) then () else ( head($seq), hof:take-while(tail($seq), $pred) ) }; </syntaxhighlight> |
Examples |
<syntaxhighlight lang="xquery"> hof:take-while( (1 to 100) ! random:integer(50), function($x) { $x >= 10 } ) </syntaxhighlight> |
hof:drop-while
Signatures | hof:drop-while($seq as item()*, $pred as function(item()) as xs:boolean) as item()*
|
Summary | The function skips all items of $seq until the predicate $pred is not satisfied anymore. It is equivalent to:
<syntaxhighlight lang="xquery"> declare function hof:drop-while($seq, $pred) { if($pred(head($seq))) then ( hof:drop-while(tail($seq), $pred) ) else ( $seq ) }; </syntaxhighlight> |
Examples | Returns the name of the first file that does not exist on disk:
<syntaxhighlight lang="xquery"> hof:drop-while( (1 to 1000) ! (. || '.log'), file:exists#1 )[1] </syntaxhighlight> |
Sorting
hof:top-k-by
Signatures | hof:top-k-by($seq as item()*, $sort-key as function(item()) as item(), $k as xs:integer) as item()*
|
Summary | Returns the $k items in $seq that are greatest when sorted by the result of $f applied to the item. The function is a much more efficient implementation of the following scheme:
<syntaxhighlight lang="xquery"> (for $x in $seq order by $sort-key($x) descending return $x )[position() <= $k] </syntaxhighlight> |
Examples |
|
hof:top-k-with
Signatures | hof:top-k-with($seq as item()*, $lt as function(item(), item()) as xs:boolean, $k as xs:integer) as item()*
|
Summary | Returns the $k items in $seq that are greatest when sorted in the order of the less-than predicate $lt . The function is a general version of hof:top-k-by($seq, $sort-key, $k) .
|
Examples |
|
IDs
hof:id
Signatures | hof:id($expr as item()*) as item()*
|
Summary | Returns its argument unchanged. This function isn’t useful on its own, but can be used as argument to other higher-order functions. |
Examples |
<syntaxhighlight lang="xquery"> let $sort := sort(?, (), hof:id#1) let $reverse-sort := sort(?, (), function($x) { -$x }) return ( $sort((1, 5, 3, 2, 4)), '|', $reverse-sort((1, 5, 3, 2, 4)) )
</syntaxhighlight>
returns: |
hof:const
Signatures | hof:const($expr as item()*, $ignored 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 |
<syntaxhighlight 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) ) </syntaxhighlight>
<syntaxhighlight 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') )
</syntaxhighlight>
returns |
Changelog
- 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