Revision as of 15:41, 9 March 2023

This XQuery Module adds some useful higher-order functions, additional to the Higher-Order Functions provided by the official specification.

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

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:fold-left1(1 to 10, function($a, $b) { $a + $b })` returns `55`. `hof:fold-left1((), function($a, $b) { $a + $b })` throws `XPTY0004`, because `$seq` has to be non-empty.

hof:until

Signature

hof:until(
  $predicate  as function(item()*) as xs:boolean,
  $action     as function(item()*) as item()*,
  $zero       as item()*
) as item()*

Summary Applies the predicate function $predicate to $zero. If the result is false, $action is invoked with the start value – or, subsequently, with the result of this function – until the predicate function returns 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 $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 OK, as the predicate is evaluated first:

<syntaxhighlight lang="xquery"> hof:until(

 function($_) { true() },
 function($_) { error() },
 'OK'

) </syntaxhighlight>

hof:scan-left

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:

<syntaxhighlight 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)
 )

}; </syntaxhighlight>

Examples

Returns triangular numbers:

<syntaxhighlight lang="xquery"> hof:scan-left(1 to 10, 0, function($a, $b) { $a + $b }) </syntaxhighlight>

hof:take-while

Signature

hof:take-while(
  $input      as item()*,
  $predicate  as function(item())
) as item()*

Summary

The function returns items of $input as long as the $predicate is satisfied. It is equivalent to:

<syntaxhighlight lang="xquery"> declare function hof:take-while($input, $predicate) {

 if(empty($input) or not($predicate(head($input)))) then () else (
   head($input),
   hof:take-while(tail($input), $predicate)
 )

}; </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

Signature

hof:drop-while(
  $input      as item()*
  $predicate  as function(item()*) as xs:boolean
) as item()*

Summary

The function skips all items of $input until the $predicate is not satisfied anymore. It is equivalent to:

<syntaxhighlight lang="xquery"> declare function hof:drop-while($input, $predicate) {

 if($predicate(head($input))) then (
   hof:drop-while(tail($input), $predicate)
 ) else (
   $input
 )

}; </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

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:

<syntaxhighlight lang="xquery"> (for $item in $input

order by $key($item) descending
return $item

)[position() <= $k] </syntaxhighlight>

Examples

hof:top-k-by(1 to 1000, hof:id#1, 5) returns 1000 999 998 997 996
hof:top-k-by(1 to 1000, function($x) { -$x }, 3) returns 1 2 3
hof:top-k-by(<x a='1' b='2' c='3'/>/@*, xs:integer#1, 2)/node-name() returns c b

hof:top-k-with

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	`hof:top-k-with(1 to 1000, function($a, $b) { $a lt $b }, 5)` returns `1000 999 998 997 996` `hof:top-k-with(-5 to 5, function($a, $b) { abs($a) gt abs($b) }, 5)` returns `0 1 -1 2 -2`

IDs

hof:id

Signature

hof:id(
  $input  as item()*
) as item()*

Summary Returns its argument unchanged. This function isn’t useful on its own, but can be used as an argument to other higher-order functions.

Examples

hof:id(1 to 5) returns 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: 1 2 3 4 5 | 5 4 3 2 1

hof:const

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

hof:const(42, 1337) returns 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, $f decides how to combine the new value with a possibly existing old one. 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 3 42

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

@@ Line 13: / Line 13: @@
 | width='120' | '''Signature'''
 |<pre>hof:fold-left1(
-   $seq     as item()+
+   $input   as item()+,
-   $f       as function(item()*
+   $action  as function(item()*, item()) as item()*
-  item())  as item()*
 ) as item()*</pre>
 |- valign="top"
@@ Line 33: / Line 32: @@
 | width='120' | '''Signature'''
 |<pre>hof:until(
-   $pred   as function(item()*)
+   $predicate  as function(item()*) as xs:boolean,
-   $f      as function(item()*)
+   $action     as function(item()*) as item()*,
-   $start  as item()*
+   $zero       as item()*
 ) as item()*</pre>
 |- valign="top"
 | '''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()}}.
+|Applies the predicate function {{Code|$predicate}} to {{Code|$zero}}. If the result is {{Code|false}}, {{Code|$action}} is invoked with the start value – or, subsequently, with the result of this function – until the predicate function returns {{Code|true()}}.
 |- valign="top"
 | '''Examples'''
@@ Line 78: / Line 77: @@
 | width='120' | '''Signature'''
 |<pre>hof:scan-left(
-   $seq     as item()*
+   $input   as item()*,
-   $start   as item()*
+   $zero    as item()*,
-   $f       as function(item()*
+   $action  as function(item()*, item()) as item()*
-  item())  as item()*
 ) as item()*</pre>
 |- valign="top"
@@ Line 87: / Line 85: @@
 |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($input, $acc, $action) {
-   if(empty($seq)) then $acc else (
+   if(empty($input)) then $acc else (
      $acc,
-     hof:scan-left(tail($seq), $f($acc, head($seq)), $f)
+     hof:scan-left(tail($input), $action($acc, head($input)), $action)
    )
 };
@@ Line 109: / Line 107: @@
 | width='120' | '''Signature'''
 |<pre>hof:take-while(
-   $seq   as item()*
+   $input      as item()*,
-   $pred  as function(item())
+   $predicate  as function(item())
 ) as item()*</pre>
 |- valign="top"
 | '''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>$input</code> as long as the <code>$predicate</code> is satisfied. It is equivalent to:
 <syntaxhighlight lang="xquery">
-declare function hof:take-while($seq, $pred) {
+declare function hof:take-while($input, $predicate) {
-   if(empty($seq) or not($pred(head($seq)))) then () else (
+   if(empty($input) or not($predicate(head($input)))) then () else (
-     head($seq),
+     head($input),
-     hof:take-while(tail($seq), $pred)
+     hof:take-while(tail($input), $predicate)
    )
 };
@@ Line 141: / Line 139: @@
 | width='120' | '''Signature'''
 |<pre>hof:drop-while(
-   $seq   as item()*
+   $input      as item()*
-   $pred  as function(item())
+   $predicate  as function(item()*) as xs:boolean
 ) as item()*</pre>
 |- valign="top"
 | '''Summary'''
-|The function skips all items of <code>$seq</code> until the predicate <code>$pred</code> is not satisfied anymore. It is equivalent to:
+|The function skips all items of <code>$input</code> until the <code>$predicate</code> is not satisfied anymore. It is equivalent to:
 <syntaxhighlight lang="xquery">
-declare function hof:drop-while($seq, $pred) {
+declare function hof:drop-while($input, $predicate) {
-   if($pred(head($seq))) then (
+   if($predicate(head($input))) then (
-     hof:drop-while(tail($seq), $pred)
+     hof:drop-while(tail($input), $predicate)
    ) else (
-     $seq
+     $input
    )
 };
@@ Line 175: / Line 173: @@
 | width='120' | '''Signature'''
 |<pre>hof:top-k-by(
-   $seq       as item()*
+   $input  as item()*
-   $sort-key  as function(item())
+   $key    as function(item()) as item()
-   $k         as xs:integer
+   $k      as xs:integer
 ) as item()*</pre>
 |- valign="top"
 | '''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|$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:
 <syntaxhighlight lang="xquery">
-(for $x in $seq
+(for $item in $input
-  order by $sort-key($x) descending
+  order by $key($item) descending
-  return $x
+  return $item
 )[position() <= $k]
 </syntaxhighlight>
@@ Line 202: / Line 200: @@
 | width='120' | '''Signature'''
 |<pre>hof:top-k-with(
-   $seq     as item()*
+   $input       as item()*
-   $lt      as function(item()
+   $comparator  as function(item(), item()) as xs:boolean
-  item())  as xs:boolean
+   $k           as xs:integer
-   $k       as xs:integer
 ) as item()*</pre>
 |- valign="top"
 | '''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)}}.
+|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'''
@@ Line 225: / Line 222: @@
 | width='120' | '''Signature'''
 |<pre>hof:id(
-   $expr  as item()*
+   $input  as item()*
 ) as item()*</pre>
 |- valign="top"
 | '''Summary'''
-|Returns its argument unchanged. This function isn’t useful on its own, but can be used as argument to other higher-order functions.
+|Returns its argument unchanged. This function isn’t useful on its own, but can be used as an argument to other higher-order functions.
 |- valign="top"
 | '''Examples'''
@@ Line 253: / Line 250: @@
 | width='120' | '''Signature'''
 |<pre>hof:const(
-   $expr     as item()*
+   $input   as item()*,
-   $ignored  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.
+|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'''

Difference between revisions of "Higher-Order Functions Module"

Revision as of 15:41, 9 March 2023

Contents

Conventions

Loops

hof:fold-left1

hof:until

hof:scan-left

hof:take-while

hof:drop-while

Sorting

hof:top-k-by

hof:top-k-with

IDs

hof:id

hof:const

Changelog

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Navigation

Tools