Difference between revisions of "Higher-Order Functions Module"

From BaseX Documentation
Jump to navigation Jump to search
m (Text replace - "| valign='top' | " to "| ")
(38 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. All functions are introduced with the <code>hof:</code> prefix, which is linked to the statically declared <code>http://basex.org/modules/hof</code> namespace.
+
This [[Module Library|XQuery Module]] adds some useful higher-order functions, additional to the [[Higher-Order Functions]] provided by the official specification.
  
=Functions=
+
=Conventions=
  
==hof:id==
+
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%'
 
|-
 
|-
| valign='top' width='90' | '''Signatures'''
+
| width='120' | '''Signatures'''
|<code><b>hof:id</b>($expr as item()*) as item()*</code>
+
|{{Func|hof:fold-left1|$seq as item()+, $f as function(item()*, item()) as item()*|item()*}}
 
|-
 
|-
 
| '''Summary'''
 
| '''Summary'''
|Returns its argument unchanged. This function isn't useful on its own, but can be used as argument to other higher-order functions.
+
|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'''
 
|
 
|
* <code>hof:id(1 to 5)</code> returns <code>1 2 3 4 5</code>
+
* {{Code|hof:fold-left1(1 to 10, function($a, $b) { $a + $b })}} returns {{Code|55}}.
* With higher-order functions:
+
* {{Code|hof:fold-left1((), function($a, $b) { $a + $b })}} throws {{Code|XPTY0004}}, because {{Code|$seq}} has to be non-empty.
<pre class="brush:xquery">
 
let $sort-by := function($f, $seq) {
 
    for $x in $seq
 
    order by $f($x)
 
    return $x
 
  }
 
let $sort := $sort-by(hof:id#1, ?),
 
    $reverse-sort := $sort-by(function($x) { -$x }, ?)
 
return (
 
  $sort((1, 5, 3, 2, 4)),
 
  '|',
 
  $reverse-sort((1, 5, 3, 2, 4))
 
)
 
</pre>
 
returns: <code>1 2 3 4 5 | 5 4 3 2 1</code>
 
 
|}
 
|}
  
==hof:const==
+
==hof:until==
{|
+
 
 +
{| width='100%'
 
|-
 
|-
| valign='top' width='90' | '''Signatures'''
+
| width='120' | '''Signatures'''
|<code><b>hof:const</b>($expr as item()*, $ignored as item()*) as item()*</code>
+
|{{Func|hof:until|$pred as function(item()*) as xs:boolean, $f as function(item()*) as item()*, $start as item()*|item()*}}
 
|-
 
|-
 
| '''Summary'''
 
| '''Summary'''
|Returns its first argument unchanged and irgores 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.
+
|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:const(42, 1337)</code> returns <code>42</code>.
+
* Doubles a numeric value until a maximum is reached:
* With higher-order functions:
 
 
<pre class="brush:xquery">
 
<pre class="brush:xquery">
let $zip-sum := function($f, $seq1, $seq2) {
+
hof:until(
    sum(map-pairs($f, $seq1, $seq2))
+
  function($output) { $output ge 1000 },
   }
+
   function($input ) { 2 * $input },
let $sum-all := $zip-sum(function($a, $b) { $a + $b }, ?, ?),
+
   1
    $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>
 
</pre>
* Another use-case: When inserting a key into a map, <code>$f</code> descides how to combine the new value with a possibly existing old one. <code>hof:const</code> here means ignoring the old value, so that's normal insertion.
+
* Calculates the square-root of a number by iteratively improving an initial guess:
 
<pre class="brush:xquery">
 
<pre class="brush:xquery">
let $insert-with := function($f, $map, $k, $v) {
+
let $sqrt := function($input as xs:double) as xs:double {
    let $old := $map($k),
+
  hof:until(
        $new := if($old) then $f($v, $old) else $v
+
    function($result) { abs($result * $result - $input) < 0.00001 },
     return map:new(($map, map{ $k := $new }))
+
     function($guess) { ($guess + $input div $guess) div 2 },
   }
+
    $input
let $map := map{ 'foo' := 1 }
+
   )
let $add := $insert-with(function($a, $b) {$a + $b}, ?, ?, ?),
+
}
    $insert := $insert-with(hof:const#2, ?, ?, ?)
+
return $sqrt(25)
return (
+
</pre>
   $add($map, 'foo', 2)('foo'),
+
* Returns {{Code|OK}}, as the predicate is evaluated first:
   $insert($map, 'foo', 42)('foo')
+
<pre class="brush:xquery">
 +
hof:until(
 +
   function($_) { true() },
 +
   function($_) { error() },
 +
  'OK'
 
)
 
)
 
</pre>
 
</pre>
returns <code>3 42</code>
 
 
|}
 
|}
  
==hof:fold-left1==
+
==hof:scan-left==
{|
+
 
 +
{| width='100%'
 
|-
 
|-
| valign='top' width='90' | '''Signatures'''
+
| width='120' | '''Signatures'''
|<code><b>hof:fold-left1</b>($f as function(item()*, item()) as item()*, $seq as item()+) as item()*</code>
+
|{{Func|hof:scan-left|$seq as item()*, $start as item()*, $f as function(item()*, item()) as item()*|item()*}}
 
|-
 
|-
 
| '''Summary'''
 
| '''Summary'''
|Works the same as [[Higher-Order_Functions#fn:fold-left($f, $seed, $seq)|fn:fold-left($f, $seed, $seq)]], but doesn't need a seed, because the sequence must be non-empty.
+
|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">
| '''Errors'''
+
declare function hof:scan-left($seq, $acc, $f) {
|''XPTY0004'' if <code>$seq</code> is empty
+
  if(empty($seq)) then $acc else (
 +
    $acc,
 +
    hof:scan-left(tail($seq), $f($acc, head($seq)), $f)
 +
  )
 +
};
 +
</pre>
 
|-
 
|-
 
| '''Examples'''
 
| '''Examples'''
 
|
 
|
* <code>hof:fold-left1(function($a, $b) { $a + $b }, 1 to 10)</code> returns <code>55</code>.
+
* Returns triangular numbers:
* <code>hof:fold-left1(function($a, $b) { $a + $b }, ())</code> throws <code>XPTY0004</code>, because <code>$seq</code> has to be non-empty.
+
<pre class="brush:xquery">
 +
hof:scan-left(1 to 10, 0, function($a, $b) { $a + $b })
 +
</pre>
 
|}
 
|}
  
==hof:until==
+
==hof:take-while==
{|
+
 
 +
{| width='100%'
 
|-
 
|-
| valign='top' width='90' | '''Signatures'''
+
| width='120' | '''Signatures'''
|<code><b>hof:until</b>($pred as function(item()*) as xs:boolean, $f as function(item()*) as item()*, $start as item()*) as item()*</code>
+
|{{Func|hof:take-while|$seq as item()*, $pred as function(item()) as xs:boolean|item()*}}
 
|-
 
|-
 
| '''Summary'''
 
| '''Summary'''
|Applies the function <code>$f</code> to the initial value <code>$start</code> until the predicate <code>$pred</code> applied to the result returns <code>true()</code>.
+
|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">
 +
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)
 +
  )
 +
};
 +
</pre>
 
|-
 
|-
 
| '''Examples'''
 
| '''Examples'''
 
|
 
|
* <code>hof:until(function($x) { $x ge 1000 }, function($y) { 2 * $y }, 1)</code> returns <code>1024</code>.
+
* Computes at most 100 random integers, but stops if an integer is smaller than 10:
* Calculating the square-root of a number by iteratively improving an initial guess:
 
 
<pre class="brush:xquery">
 
<pre class="brush:xquery">
let $sqrt := function($x as xs:double) as xs:double {
+
hof:take-while(
   hof:until(
+
   (1 to 100) ! random:integer(50),
    function($res) { abs($res * $res - $x) < 0.00001 },
+
  function($x) { $x >= 10 }
    function($guess) { ($guess + $x div $guess) div 2 },
+
)
    $x
 
  )
 
}
 
return $sqrt(25)
 
 
</pre>
 
</pre>
returns <code>5.000000000053722</code>.
 
 
|}
 
|}
 +
 +
=Sorting=
  
 
==hof:top-k-by==
 
==hof:top-k-by==
  
{{Mark|Introduced with Version 7.2:}}
+
{| width='100%'
 
 
{|
 
 
|-
 
|-
| valign='top' width='90' | '''Signatures'''
+
| width='120' | '''Signatures'''
|<code><b>hof:top-k-by</b>($seq as item()*, $sort-key as function(item()) as item(), $k as xs:integer) as item()*</code>
+
|{{Func|hof:top-k-by|$seq as item()*, $sort-key as function(item()) as item(), $k as xs:integer|item()*}}
 
|-
 
|-
 
| '''Summary'''
 
| '''Summary'''
|Returns the <code>$k</code> items in <code>$seq</code> that are greatest when sorted by the result of <code>$f</code> 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">
 
<pre class="brush: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>
 
</pre>
 
|-
 
|-
| '''Errors'''
+
| '''Examples'''
|''XPTY0004'' if <code>$sort-key</code> doesn't return exactly one item
+
|
 +
* {{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'''
 
| '''Examples'''
 
|
 
|
* <code>hof:top-k-by(1 to 1000, hof:id#1, 5)</code> returns <code>1000 999 998 997 996</code>
+
* {{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-by(1 to 1000, function($x) { -$x }, 3)</code> returns <code>1 2 3</code>
+
* {{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-by(<x a='1' b='2' c='3'/>/@*, xs:integer#1, 2)/node-name()</code> returns <code>c b</code>
 
 
|}
 
|}
  
==hof:top-k-with==
+
=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:
 +
<pre class="brush: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))
 +
)
 +
</pre>
 +
returns: <code>1 2 3 4 5 | 5 4 3 2 1</code>
 +
|}
  
{{Mark|Introduced with Version 7.2:}}
+
==hof:const==
  
{|
+
{| width='100%'
 
|-
 
|-
| valign='top' width='90' | '''Signatures'''
+
| width='120' | '''Signatures'''
|<code><b>hof:top-k-with</b>($seq as item()*, $lt as function(item(), item()) as xs:boolean, $k as xs:integer) as item()*</code>
+
|{{Func|hof:const|$expr as item()*, $ignored as item()*|item()*}}
 
|-
 
|-
 
| '''Summary'''
 
| '''Summary'''
|Returns the <code>$k</code> items in <code>$seq</code> that are greatest when sorted in the order of the ''less-than'' predicate <code>$lt</code>. The function is a general version of <code>hof:top-k-by($seq, $sort-key, $k)</code>.
+
|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'''
 
| '''Examples'''
 
|
 
|
* <code>hof:top-k-with(1 to 1000, function($a, $b) { $a lt $b }, 5)</code> returns <code>1000 999 998 997 996</code>
+
* {{Code|hof:const(42, 1337)}} returns {{Code|42}}.
* <code>hof:top-k-with(-5 to 5, function($a, $b) { abs($a) gt abs($b) }, 5)</code> returns <code>0 1 -1 2 -2</code>
+
* With higher-order functions:
 +
<pre class="brush: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 class="brush: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=
 
=Changelog=
  
===Version 7.2===
+
;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: [[#hof:iterate|hof:iterate]]
+
* Removed: hof:iterate
  
===Version 7.0===
+
;Version 7.0
  
 
* module added
 
* module added
 
[[Category:XQuery]]
 

Revision as of 12:50, 12 December 2017

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:
hof:until(
  function($output) { $output ge 1000 },
  function($input ) { 2 * $input },
  1
)
  • Calculates the square-root of a number by iteratively improving an initial guess:
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)
  • Returns OK, as the predicate is evaluated first:
hof:until(
  function($_) { true() },
  function($_) { error() },
  'OK'
)

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:
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)
  )
};
Examples
  • Returns triangular numbers:
hof:scan-left(1 to 10, 0, function($a, $b) { $a + $b })

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:
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)
  )
};
Examples
  • Computes at most 100 random integers, but stops if an integer is smaller than 10:
hof:take-while(
  (1 to 100) ! random:integer(50),
  function($x) { $x >= 10 }
)

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:
(for $x in $seq
 order by $sort-key($x) descending
 return $x
)[position() <= $k]
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:
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))
)

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:
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)
)
  • 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.
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 3 42

Changelog

Version 8.1
Version 7.2
Version 7.0
  • module added