Difference between revisions of "Higher-Order Functions Module"

From BaseX Documentation
Jump to navigation Jump to search
(5 intermediate revisions by the same user not shown)
Line 31: Line 31:
 
|-
 
|-
 
| '''Summary'''
 
| '''Summary'''
|Applies the function {{Code|$f}} to the initial value {{Code|$start}} until the predicate {{Code|$pred}} applied to the result returns {{Code|true()}}.
+
|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'''
 
|
 
|
* {{Code|hof:until(function($x) { $x ge 1000 }, function($y) { 2 * $y }, 1)}} returns {{Code|1024}}.
+
* Doubles a numeric value until a maximum is reached:
* Calculating the square-root of a number by iteratively improving an initial guess:
+
<syntaxhighlight lang="xquery">
<pre class="brush:xquery">
+
hof:until(
let $sqrt := function($x as xs:double) as xs:double {
+
  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($res) { abs($res * $res - $x) < 0.00001 },
+
     function($result) { abs($result * $result - $input) < 0.00001 },
     function($guess) { ($guess + $x div $guess) div 2 },
+
     function($guess) { ($guess + $input div $guess) div 2 },
     $x
+
     $input
 
   )
 
   )
 
}
 
}
 
return $sqrt(25)
 
return $sqrt(25)
</pre>
+
</syntaxhighlight>
returns {{Code|5.000000000053722}}.
+
* Returns {{Code|OK}}, as the predicate is evaluated first:
 
+
<syntaxhighlight lang="xquery">
* The evaluation of the predicate is pre-fixed, thus every cycle starts with the evaluation of the predicate first.
+
hof:until(
<pre class="brush:xquery">
+
  function($_) { true() },
declare function local:pred($res) { true() };
+
  function($_) { error() },
declare function local:loop($val) { $val + 1 };
+
  'OK'
 
+
)
hof:until(local:pred#1, local:loop#1, 0)
+
</syntaxhighlight>
</pre>
 
returns {{Code|0}}.
 
 
 
 
|}
 
|}
  
Line 69: 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:
<pre class="brush:xquery">
+
<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 76: Line 80:
 
   )
 
   )
 
};
 
};
</pre>
+
</syntaxhighlight>
 
|-
 
|-
 
| '''Examples'''
 
| '''Examples'''
 
|
 
|
 
* Returns triangular numbers:
 
* Returns triangular numbers:
<pre class="brush:xquery">
+
<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 })
</pre>
+
</syntaxhighlight>
 
|}
 
|}
  
Line 95: 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:
<pre class="brush:xquery">
+
<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 102: Line 106:
 
   )
 
   )
 
};
 
};
</pre>
+
</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:
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
hof:take-while(
 
hof:take-while(
 
   (1 to 100) ! random:integer(50),
 
   (1 to 100) ! random:integer(50),
 
   function($x) { $x >= 10 }
 
   function($x) { $x >= 10 }
 
)
 
)
</pre>
+
</syntaxhighlight>
 
|}
 
|}
  
Line 126: Line 130:
 
| '''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:
<pre class="brush:xquery">
+
<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]
</pre>
+
</syntaxhighlight>
 
|-
 
|-
 
| '''Examples'''
 
| '''Examples'''
Line 172: Line 176:
 
* {{Code|hof:id(1 to 5)}} returns {{Code|1 2 3 4 5}}
 
* {{Code|hof:id(1 to 5)}} returns {{Code|1 2 3 4 5}}
 
* With higher-order functions:
 
* With higher-order functions:
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
let $sort := sort(?, hof:id#1)
+
let $sort := sort(?, (), hof:id#1)
let $reverse-sort := sort(?, function($x) { -$x })
+
let $reverse-sort := sort(?, (), function($x) { -$x })
 
return (
 
return (
 
   $sort((1, 5, 3, 2, 4)),
 
   $sort((1, 5, 3, 2, 4)),
Line 180: Line 184:
 
   $reverse-sort((1, 5, 3, 2, 4))
 
   $reverse-sort((1, 5, 3, 2, 4))
 
)
 
)
</pre>
+
</syntaxhighlight>
 
returns: <code>1 2 3 4 5 | 5 4 3 2 1</code>
 
returns: <code>1 2 3 4 5 | 5 4 3 2 1</code>
 
|}
 
|}
Line 198: Line 202:
 
* {{Code|hof:const(42, 1337)}} returns {{Code|42}}.
 
* {{Code|hof:const(42, 1337)}} returns {{Code|42}}.
 
* With higher-order functions:
 
* With higher-order functions:
<pre class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
let $zip-sum := function($f, $seq1, $seq2) {
 
let $zip-sum := function($f, $seq1, $seq2) {
 
   sum(for-each-pair($seq1, $seq2, $f))
 
   sum(for-each-pair($seq1, $seq2, $f))
Line 208: Line 212:
 
   $sum-left((1, 1, 1, 1, 1), 1 to 5)
 
   $sum-left((1, 1, 1, 1, 1), 1 to 5)
 
)
 
)
</pre>
+
</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.
 
* 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 class="brush:xquery">
+
<syntaxhighlight lang="xquery">
 
let $insert-with := function($f, $map, $k, $v) {
 
let $insert-with := function($f, $map, $k, $v) {
 
   let $old := $map($k)
 
   let $old := $map($k)
Line 223: Line 227:
 
   $ins($map, 'foo', 42)('foo')
 
   $ins($map, 'foo', 42)('foo')
 
)
 
)
</pre>
+
</syntaxhighlight>
 
returns {{Code|3 42}}
 
returns {{Code|3 42}}
 
|}
 
|}

Revision as of 14:40, 27 February 2020

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

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: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

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
  • 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

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
  • Returns triangular numbers:

<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
  • 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>

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

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
  • 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

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
  • 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

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
  • 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 8.1
Version 7.2
Version 7.0
  • module added