Difference between revisions of "Higher-Order Functions Module"
(20 intermediate revisions by 2 users not shown) | |||
Line 3: | Line 3: | ||
=Conventions= | =Conventions= | ||
− | All functions in this module are assigned to the | + | 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== | ||
Line 89: | Line 15: | ||
|- | |- | ||
| '''Summary''' | | '''Summary''' | ||
− | |Works the same as [[Higher-Order Functions#fn:fold-left|fn:fold-left]], but | + | |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''' | | '''Examples''' | ||
Line 105: | Line 31: | ||
|- | |- | ||
| '''Summary''' | | '''Summary''' | ||
− | |Applies the function {{Code|$ | + | |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''' | | '''Examples''' | ||
| | | | ||
− | * | + | * Doubles a numeric value until a maximum is reached: |
− | * | + | <syntaxhighlight lang="xquery"> |
− | < | + | hof:until( |
− | let $sqrt := function($ | + | 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 $sqrt := function($input as xs:double) as xs:double { | ||
hof:until( | hof:until( | ||
− | function($ | + | function($result) { abs($result * $result - $input) < 0.00001 }, |
− | function($guess) { ($guess + $ | + | function($guess) { ($guess + $input div $guess) div 2 }, |
− | $ | + | $input |
) | ) | ||
} | } | ||
return $sqrt(25) | 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:scan-left== | ==hof:scan-left== | ||
− | |||
− | |||
{| width='100%' | {| width='100%' | ||
Line 135: | Line 73: | ||
| '''Summary''' | | '''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: | |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) { | declare function hof:scan-left($seq, $acc, $f) { | ||
if(empty($seq)) then $acc else ( | if(empty($seq)) then $acc else ( | ||
Line 142: | Line 80: | ||
) | ) | ||
}; | }; | ||
− | </ | + | </syntaxhighlight> |
|- | |- | ||
| '''Examples''' | | '''Examples''' | ||
| | | | ||
* Returns triangular numbers: | * Returns triangular numbers: | ||
− | < | + | <syntaxhighlight lang="xquery"> |
hof:scan-left(1 to 10, 0, function($a, $b) { $a + $b }) | hof:scan-left(1 to 10, 0, function($a, $b) { $a + $b }) | ||
− | </ | + | </syntaxhighlight> |
|} | |} | ||
==hof:take-while== | ==hof:take-while== | ||
− | |||
− | |||
{| width='100%' | {| width='100%' | ||
Line 163: | Line 99: | ||
| '''Summary''' | | '''Summary''' | ||
|The function returns items of <code>$seq</code> as long as the predicate <code>$pred</code> is satisfied. It is equivalent to: | |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) { | declare function hof:take-while($seq, $pred) { | ||
if(empty($seq) or not($pred(head($seq)))) then () else ( | if(empty($seq) or not($pred(head($seq)))) then () else ( | ||
Line 170: | Line 106: | ||
) | ) | ||
}; | }; | ||
− | </ | + | </syntaxhighlight> |
|- | |- | ||
| '''Examples''' | | '''Examples''' | ||
| | | | ||
* Computes at most 100 random integers, but stops if an integer is smaller than 10: | * Computes at most 100 random integers, but stops if an integer is smaller than 10: | ||
− | < | + | <syntaxhighlight lang="xquery"> |
hof:take-while( | hof:take-while( | ||
− | + | (1 to 100) ! random:integer(50), | |
− | |||
function($x) { $x >= 10 } | 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== | ||
Line 193: | Line 161: | ||
| '''Summary''' | | '''Summary''' | ||
|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: | |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 | (for $x in $seq | ||
order by $sort-key($x) descending | order by $sort-key($x) descending | ||
return $x | return $x | ||
)[position() <= $k] | )[position() <= $k] | ||
− | </ | + | </syntaxhighlight> |
|- | |- | ||
| '''Examples''' | | '''Examples''' | ||
Line 221: | Line 189: | ||
* {{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(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}} | * {{Code|hof:top-k-with(-5 to 5, function($a, $b) { abs($a) gt abs($b) }, 5)}} returns {{Code|0 1 -1 2 -2}} | ||
+ | |} | ||
+ | |||
+ | =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 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 | ;Version 8.1 | ||
− | |||
* Added: [[#hof:scan-left|hof:scan-left]], [[#hof:take-while|hof:take-while]] | * Added: [[#hof:scan-left|hof:scan-left]], [[#hof:take-while|hof:take-while]] | ||
;Version 7.2 | ;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: hof:iterate | * Removed: hof:iterate | ||
;Version 7.0 | ;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