Difference between revisions of "Higher-Order Functions"
(28 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
− | This page | + | This page present some ''higher-order functions'' of the XQuery specification. The BaseX-specific [[Higher-Order Functions Module]] contains some additional useful functions. |
− | |||
− | |||
=Function Items= | =Function Items= | ||
− | Probably the most important new feature in XQuery 3.0 are ''function items'', i. e. items that act as functions, but can also be passed to and from other functions and expressions | + | Probably the most important new feature in XQuery 3.0 are ''function items'', i. e., items that act as functions, but can also be passed to and from other functions and expressions. This feature makes functions ''first-class citizens'' of the language. The [[XQuery_3.0#Function_Items|XQuery 3.0]] page goes into details on how function items can be obtained. |
− | |||
− | The [[XQuery_3.0#Function_Items|XQuery 3.0]] page goes into details on how function items can be obtained. | ||
== Function Types == | == Function Types == | ||
− | Like every XQuery item, function items have a ''sequence type''. It can be | + | Like every XQuery item, function items have a ''sequence type''. It can be used to specify the ''arity'' (number of arguments the function takes) and the argument and result types. |
− | used to specify the ''arity'' (number of arguments the function takes) and | ||
− | the argument and result types. | ||
− | The most general function type is <code>function(*)</code>. It's the type of all | + | The most general function type is <code>function(*)</code>. It's the type of all function items. The following query for example goes through a list of XQuery items and, if it is a function item, prints its arity: |
− | function items. The following query for example goes through a list of XQuery | ||
− | items and, if it is a function item, prints its arity: | ||
<pre class="brush:xquery"> | <pre class="brush:xquery"> | ||
Line 26: | Line 18: | ||
''Result:'' <code>3 1</code> | ''Result:'' <code>3 1</code> | ||
− | The notation for specifying argument and return types is quite intuitive, as it | + | The notation for specifying argument and return types is quite intuitive, as it closely resembles the function declaration. The XQuery function |
− | closely resembles the function declaration. The XQuery function | ||
<pre class="brush:xquery"> | <pre class="brush:xquery"> | ||
Line 38: | Line 29: | ||
</pre> | </pre> | ||
− | for example has the type <code>function(xs:string, xs:integer) as xs:string</code>. It isn't possible to specify only the argument and not the result | + | for example has the type <code>function(xs:string, xs:integer) as xs:string</code>. It isn't possible to specify only the argument and not the result type or the other way round. A good place-holder to use when no restriction is wanted is <code>item()*</code>, as it matches any XQuery value. |
− | type or the other way round. A good place-holder to use when no restriction | ||
− | is wanted is <code>item()*</code>, as it matches any XQuery value. | ||
Function types can also be nested. As an example we take <code>local:on-sequences</code>, which takes a function defined on single items and makes it work on sequences as well: | Function types can also be nested. As an example we take <code>local:on-sequences</code>, which takes a function defined on single items and makes it work on sequences as well: | ||
Line 51: | Line 40: | ||
}; | }; | ||
</pre> | </pre> | ||
− | We | + | |
+ | We willl see later how <code>fn:for-each(...)</code> works. The type of <code>local:on-sequences(...)</code> on the other hand is easily constructed, if a bit long: | ||
<code>function(function(item()) as item()*) as function(item()*) as item()*</code>. | <code>function(function(item()) as item()*) as function(item()*) as item()*</code>. | ||
Line 59: | Line 49: | ||
A ''higher-order function'' is a function that takes other functions as arguments and/or returns them as results. <code>fn:for-each</code> and <code>local:on-sequences</code> from the last chapter are nice examples. | A ''higher-order function'' is a function that takes other functions as arguments and/or returns them as results. <code>fn:for-each</code> and <code>local:on-sequences</code> from the last chapter are nice examples. | ||
− | With the help of higher-order functions, one can extract common patterns of | + | With the help of higher-order functions, one can extract common patterns of ''behavior'' and abstract them into a library function. |
− | '' | ||
− | == | + | == Sequences == |
− | Some usage patterns on sequences are so common that the higher-order functions | + | Some usage patterns on sequences are so common that the higher-order functions describing them are in the XQuery standard libraries. They are listed here, together with their possible XQuery implementation and some motivating examples. |
− | describing them are in the XQuery standard libraries. They are listed here, together | ||
− | with their possible XQuery implementation and some motivating examples. | ||
===fn:for-each=== | ===fn:for-each=== | ||
− | |||
− | |||
{| | {| | ||
|- | |- | ||
− | | width=' | + | | width='120' | '''Signatures''' |
− | |{{Func|fn:for-each|$seq as item()*, $ | + | |{{Func|fn:for-each|$seq as item()*, $function as function(item()) as item()*)|item()*}} |
|- | |- | ||
| '''Summary''' | | '''Summary''' | ||
− | |Applies the | + | |Applies the specified <code>$function</code> to every item of <code>$seq</code> and returns all results as a single sequence. |
|- | |- | ||
| '''Examples''' | | '''Examples''' | ||
| | | | ||
− | <ul><li> | + | <ul><li>Square all numbers from 1 to 10: |
<pre class="brush:xquery"> | <pre class="brush:xquery"> | ||
fn:for-each(1 to 10, math:pow(?, 2)) | fn:for-each(1 to 10, math:pow(?, 2)) | ||
Line 88: | Line 73: | ||
''Result:'' <code>1 4 9 16 25 36 49 64 81 100</code> | ''Result:'' <code>1 4 9 16 25 36 49 64 81 100</code> | ||
</li> | </li> | ||
− | <li> | + | <li>Apply a list of functions to a string: |
<pre class="brush:xquery"> | <pre class="brush:xquery"> | ||
let $fs := ( | let $fs := ( | ||
Line 98: | Line 83: | ||
</pre> | </pre> | ||
''Result:'' <code>FOOBAR bar 6</code> | ''Result:'' <code>FOOBAR bar 6</code> | ||
+ | </li> | ||
+ | <li>Process each item of a sequence with the arrow operator: | ||
+ | <pre class="brush:xquery"> | ||
+ | ("one", "two", "three") => fn:for-each(fn:upper-case(?)) | ||
+ | </pre> | ||
+ | ''Result:'' <code>ONE TWO THREE</code> | ||
</li></ul> | </li></ul> | ||
|- | |- | ||
| '''XQuery 1.0''' | | '''XQuery 1.0''' | ||
− | |<pre class="brush:xquery"> | + | |At the core, for-each is nothing else than a simple FLWOR expression: |
+ | <pre class="brush:xquery"> | ||
declare function local:for-each( | declare function local:for-each( | ||
$seq as item()*, | $seq as item()*, | ||
Line 113: | Line 105: | ||
===fn:filter=== | ===fn:filter=== | ||
− | |||
− | |||
{| | {| | ||
|- | |- | ||
− | | width=' | + | | width='120' | '''Signatures''' |
− | |{{Func|fn:filter|$seq as item()*, $pred as function(item()) as xs:boolean)|item()*}} | + | |{{Func|fn:filter|$seq as item()*, $pred as function(item()) as xs:boolean)|item()*}} |
|- | |- | ||
| '''Summary''' | | '''Summary''' | ||
Line 165: | Line 155: | ||
|- | |- | ||
| '''XQuery 1.0''' | | '''XQuery 1.0''' | ||
− | |<pre class="brush:xquery"> | + | |At the core, for-each is nothing else than a filter expression: |
+ | <pre class="brush:xquery"> | ||
declare function local:filter( | declare function local:filter( | ||
$seq as item()*, | $seq as item()*, | ||
Line 176: | Line 167: | ||
===fn:for-each-pair=== | ===fn:for-each-pair=== | ||
− | |||
− | |||
{| | {| | ||
|- | |- | ||
− | | width=' | + | | width='120' | '''Signatures''' |
− | |{{Func|fn:for-each-pair|$seq1 as item()*, $seq2 as item()*, $ | + | |{{Func|fn:for-each-pair|$seq1 as item()*, $seq2 as item()*, $function as function(item(), item()) as item()*|item()*}} |
|- | |- | ||
| '''Summary''' | | '''Summary''' | ||
− | | | + | |Applies the specified {{Code|$function}} to the successive pairs of items of <code>$seq1</code> and <code>$seq2</code>. Evaluation is stopped if one sequence yields no more items. |
|- | |- | ||
| '''Examples''' | | '''Examples''' | ||
Line 200: | Line 189: | ||
<li>Line numbering: | <li>Line numbering: | ||
<pre class="brush:xquery"> | <pre class="brush:xquery"> | ||
− | let $number- | + | let $number-words := function($str) { |
fn:string-join( | fn:string-join( | ||
fn:for-each-pair( | fn:for-each-pair( | ||
− | 1 to | + | 1 to 1000000000, |
− | tokenize($str, ' | + | tokenize($str, ' +'), |
concat(?, ': ', ?) | concat(?, ': ', ?) | ||
), | ), | ||
− | '& | + | '
' |
) | ) | ||
} | } | ||
− | return $number- | + | return $number-words('how are you?') |
− | how are you?') | ||
</pre> | </pre> | ||
''Result:'' | ''Result:'' | ||
− | <pre> | + | <pre class="brush:xquery"> |
− | 1: | + | 1: how |
− | 2: | + | 2: are |
+ | 3: you? | ||
</pre> | </pre> | ||
</li> | </li> | ||
Line 252: | Line 241: | ||
== Folds == | == Folds == | ||
− | A ''fold'', also called ''reduce'' or ''accumulate'' in other languages, is a very | + | A ''fold'', also called ''reduce'' or ''accumulate'' in other languages, is a very basic higher-order function on sequences. It starts from a seed value and incrementally builds up a result, consuming one element from the sequence at a time and combining it with the aggregate of a user-defined function. |
− | basic higher-order function on sequences. It starts from a seed value and incrementally | ||
− | builds up a result, consuming one element from the sequence at a time and combining it with | ||
− | the aggregate | ||
− | Folds are one solution to the problem of not having ''state'' in functional programs. | + | Folds are one solution to the problem of not having ''state'' in functional programs. Solving a problem in ''imperative'' programming languages often means repeatedly updating the value of variables, which isn't allowed in functional languages. |
− | Solving a problem in ''imperative'' programming languages often means repeatedly updating | ||
− | the value of variables, which isn't allowed in functional languages. | ||
Calculating the ''product'' of a sequence of integers for example is easy in <code>Java</code>: | Calculating the ''product'' of a sequence of integers for example is easy in <code>Java</code>: | ||
+ | |||
<pre class="brush:java"> | <pre class="brush:java"> | ||
public int product(int[] seq) { | public int product(int[] seq) { | ||
Line 271: | Line 256: | ||
} | } | ||
</pre> | </pre> | ||
+ | |||
Nice and efficient implementations using folds will be given below. | Nice and efficient implementations using folds will be given below. | ||
− | The ''linear'' folds on sequences come in two | + | The ''linear'' folds on sequences come in two flavors. They differ in the direction in which they traverse the sequence: |
===fn:fold-left=== | ===fn:fold-left=== | ||
− | |||
− | |||
{| | {| | ||
|- | |- | ||
− | | width=' | + | | width='120' | '''Signatures''' |
− | |{{Func|fn:fold-left|$seq as item()*, $seed as item()*, $ | + | |{{Func|fn:fold-left|$seq as item()*, $seed as item()*, $function as function(item()*, item()) as item()*|item()*}} |
|- | |- | ||
| '''Summary''' | | '''Summary''' | ||
|The ''left fold'' traverses the sequence from the left. | |The ''left fold'' traverses the sequence from the left. | ||
− | The query <code>fn:fold-left( | + | The query <code>fn:fold-left(1 to 5, 0, $f)</code> for example would be evaluated as: |
<pre class="brush:xquery"> | <pre class="brush:xquery"> | ||
$f($f($f($f($f(0, 1), 2), 3), 4), 5) | $f($f($f($f($f(0, 1), 2), 3), 4), 5) | ||
Line 294: | Line 278: | ||
|<ul><li>Product of a sequence of integers: | |<ul><li>Product of a sequence of integers: | ||
<pre class="brush:xquery"> | <pre class="brush:xquery"> | ||
− | + | fn:fold-left(1 to 5, 1, | |
− | function($result, $ | + | function($result, $curr) { $result * $curr } |
) | ) | ||
− | |||
</pre> | </pre> | ||
''Result:'' <code>120</code> | ''Result:'' <code>120</code> | ||
Line 328: | Line 311: | ||
$seq as item()*, | $seq as item()*, | ||
$seed as item()*, | $seed as item()*, | ||
− | $ | + | $function as function(item()*, item()) as item()* |
) as item()* { | ) as item()* { | ||
if(empty($seq)) then $seed | if(empty($seq)) then $seed | ||
else local:fold-left( | else local:fold-left( | ||
fn:tail($seq), | fn:tail($seq), | ||
− | $ | + | $function($seed, fn:head($seq)), |
− | $ | + | $function |
) | ) | ||
}; | }; | ||
Line 341: | Line 324: | ||
===fn:fold-right=== | ===fn:fold-right=== | ||
− | |||
− | |||
{| | {| | ||
|- | |- | ||
− | | width=' | + | | width='120' | '''Signatures''' |
− | |{{Func|fn:fold-right|$seq as item()*, $seed as item()*, $ | + | |{{Func|fn:fold-right|$seq as item()*, $seed as item()*, $function as function(item(), item()*) as item()*|item()*}} |
|- | |- | ||
| '''Summary''' | | '''Summary''' | ||
− | |The ''right fold'' <code>fn:fold-right($seq, $seed, $fun)</code> traverses the from the right. | + | |The ''right fold'' <code>fn:fold-right($seq, $seed, $fun)</code> traverses the sequence from the right. |
The query <code>fn:fold-right(1 to 5, 0, $f)</code> for example would be evaluated as: | The query <code>fn:fold-right(1 to 5, 0, $f)</code> for example would be evaluated as: | ||
<pre class="brush:xquery"> | <pre class="brush:xquery"> | ||
Line 359: | Line 340: | ||
|<ul><li>Product of a sequence of integers: | |<ul><li>Product of a sequence of integers: | ||
<pre class="brush:xquery"> | <pre class="brush:xquery"> | ||
− | + | fn:fold-right(1 to 5, 1, | |
− | function($ | + | function($curr, $result) { $result * $curr } |
) | ) | ||
− | |||
</pre> | </pre> | ||
''Result:'' <code>120</code> | ''Result:'' <code>120</code> | ||
Line 372: | Line 352: | ||
) | ) | ||
</pre> | </pre> | ||
− | ''Result:'' <code>$ | + | ''Result:'' <code>$f(1, $f(2, $f(3, $f(4, $f(5, $seed)))))</code> |
</li> | </li> | ||
<li>Reversing a sequence of items: | <li>Reversing a sequence of items: | ||
<pre class="brush:xquery"> | <pre class="brush:xquery"> | ||
− | let $reverse := fn:fold-right( | + | let $reverse := fn:fold-right(?, (), |
function($item, $rev) { | function($item, $rev) { | ||
$rev, $item | $rev, $item | ||
− | } | + | } |
− | |||
− | |||
) | ) | ||
return $reverse(1 to 10) | return $reverse(1 to 10) | ||
Line 391: | Line 369: | ||
|<pre class="brush:xquery"> | |<pre class="brush:xquery"> | ||
declare function local:fold-right( | declare function local:fold-right( | ||
+ | $seq as item()*, | ||
$seed as item()*, | $seed as item()*, | ||
− | $ | + | $function as function(item(), item()*) as item()* |
− | |||
) as item()* { | ) as item()* { | ||
if(empty($seq)) then $seed | if(empty($seq)) then $seed | ||
− | else $ | + | else $function( |
fn:head($seq), | fn:head($seq), | ||
− | local:fold-right(tail($seq), $seed, $ | + | local:fold-right(tail($seq), $seed, $function) |
) | ) | ||
}; | }; | ||
Line 404: | Line 382: | ||
Note that the order of the arguments of <code>$fun</code> are inverted compared to that in <code>fn:fold-left(...)</code>. | Note that the order of the arguments of <code>$fun</code> are inverted compared to that in <code>fn:fold-left(...)</code>. | ||
|} | |} | ||
− | |||
− |
Revision as of 14:44, 12 December 2017
This page present some higher-order functions of the XQuery specification. The BaseX-specific Higher-Order Functions Module contains some additional useful functions.
Contents
Function Items
Probably the most important new feature in XQuery 3.0 are function items, i. e., items that act as functions, but can also be passed to and from other functions and expressions. This feature makes functions first-class citizens of the language. The XQuery 3.0 page goes into details on how function items can be obtained.
Function Types
Like every XQuery item, function items have a sequence type. It can be used to specify the arity (number of arguments the function takes) and the argument and result types.
The most general function type is function(*)
. It's the type of all function items. The following query for example goes through a list of XQuery items and, if it is a function item, prints its arity:
for $item in (1, 'foo', fn:concat#3, function($a) { 42 * $a }) where $item instance of function(*) return fn:function-arity($item)
Result: 3 1
The notation for specifying argument and return types is quite intuitive, as it closely resembles the function declaration. The XQuery function
declare function local:char-at( $str as xs:string, $pos as xs:integer ) as xs:string { fn:substring($str, $pos, 1) };
for example has the type function(xs:string, xs:integer) as xs:string
. It isn't possible to specify only the argument and not the result type or the other way round. A good place-holder to use when no restriction is wanted is item()*
, as it matches any XQuery value.
Function types can also be nested. As an example we take local:on-sequences
, which takes a function defined on single items and makes it work on sequences as well:
declare function local:on-sequences( $fun as function(item()) as item()* ) as function(item()*) as item()* { fn:for-each($fun, ?) };
We willl see later how fn:for-each(...)
works. The type of local:on-sequences(...)
on the other hand is easily constructed, if a bit long:
function(function(item()) as item()*) as function(item()*) as item()*
.
Higher-Order Functions
A higher-order function is a function that takes other functions as arguments and/or returns them as results. fn:for-each
and local:on-sequences
from the last chapter are nice examples.
With the help of higher-order functions, one can extract common patterns of behavior and abstract them into a library function.
Sequences
Some usage patterns on sequences are so common that the higher-order functions describing them are in the XQuery standard libraries. They are listed here, together with their possible XQuery implementation and some motivating examples.
fn:for-each
Signatures | fn:for-each($seq as item()*, $function as function(item()) as item()*)) as item()*
|
Summary | Applies the specified $function to every item of $seq and returns all results as a single sequence.
|
Examples |
|
XQuery 1.0 | At the core, for-each is nothing else than a simple FLWOR expression:
declare function local:for-each( $seq as item()*, $fun as function(item()) as item()* ) as item()* { for $s in $seq return $fun($s) }; |
fn:filter
Signatures | fn:filter($seq as item()*, $pred as function(item()) as xs:boolean)) as item()*
|
Summary | Applies the boolean predicate $pred to all elements of the sequence $seq , returning those for which it returns true() .
|
Examples |
|
Note | fn:filter can be easily implemented with fn:for-each :
declare function local:filter($seq, $pred) { for-each( $seq, function($x) { if($pred($x)) then $x else () } ) }; |
XQuery 1.0 | At the core, for-each is nothing else than a filter expression:
declare function local:filter( $seq as item()*, $pred as function(item()) as xs:boolean ) as item()* { $seq[$pred(.)] }; |
fn:for-each-pair
Signatures | fn:for-each-pair($seq1 as item()*, $seq2 as item()*, $function as function(item(), item()) as item()*) as item()*
|
Summary | Applies the specified $function to the successive pairs of items of $seq1 and $seq2 . Evaluation is stopped if one sequence yields no more items.
|
Examples |
|
XQuery 1.0 | declare function local:for-each-pair( $seq1 as item()*, $seq2 as item()*, $fun as function(item(), item()) as item()* ) as item()* { for $pos in 1 to min((count($seq1), count($seq2))) return $fun($seq1[$pos], $seq2[$pos]) }; |
Folds
A fold, also called reduce or accumulate in other languages, is a very basic higher-order function on sequences. It starts from a seed value and incrementally builds up a result, consuming one element from the sequence at a time and combining it with the aggregate of a user-defined function.
Folds are one solution to the problem of not having state in functional programs. Solving a problem in imperative programming languages often means repeatedly updating the value of variables, which isn't allowed in functional languages.
Calculating the product of a sequence of integers for example is easy in Java
:
public int product(int[] seq) { int result = 1; for(int i : seq) { result = result * i; } return result; }
Nice and efficient implementations using folds will be given below.
The linear folds on sequences come in two flavors. They differ in the direction in which they traverse the sequence:
fn:fold-left
Signatures | fn:fold-left($seq as item()*, $seed as item()*, $function as function(item()*, item()) as item()*) as item()*
|
Summary | The left fold traverses the sequence from the left.
The query $f($f($f($f($f(0, 1), 2), 3), 4), 5) |
Examples |
|
XQuery 1.0 | As folds are more general than FLWOR expressions, the implementation isn't as concise as the former ones:
declare function local:fold-left( $seq as item()*, $seed as item()*, $function as function(item()*, item()) as item()* ) as item()* { if(empty($seq)) then $seed else local:fold-left( fn:tail($seq), $function($seed, fn:head($seq)), $function ) }; |
fn:fold-right
Signatures | fn:fold-right($seq as item()*, $seed as item()*, $function as function(item(), item()*) as item()*) as item()*
|
Summary | The right fold fn:fold-right($seq, $seed, $fun) traverses the sequence from the right.
The query $f(1, $f(2, $f(3, $f(4, $f(5, 0))))) |
Examples |
|
XQuery 1.0 | declare function local:fold-right( $seq as item()*, $seed as item()*, $function as function(item(), item()*) as item()* ) as item()* { if(empty($seq)) then $seed else $function( fn:head($seq), local:fold-right(tail($seq), $seed, $function) ) }; Note that the order of the arguments of |