Difference between revisions of "Higher-Order Functions"

From BaseX Documentation
Jump to navigation Jump to search
m (Text replace - "| width='90' | '''Signatures'''" to "| width='120' | '''Signatures'''")
(correct new signature)
Line 286: Line 286:
 
| '''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($f, 0, 1 to 5)</code> for example would be evaluated as:
+
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)

Revision as of 00:50, 12 July 2013

This page talks about higher-order functions introduced with XQuery 3.0. The BaseX-specific hof module containing some more very usful functions can be found at Higher-Order Functions Module.

Version 7.7: In the upcoming version of the XQuery Functions and Operators specification, some functions will be modified! Function arguments are now placed last in the function signature. Details are found below.

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, making 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'll 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 behaviour and abstract them into a library function.

Higher-Order Functions on 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

Updated with Version 7.7: the function has been renamed, and the arguments have been swapped.

Signatures fn:for-each($seq as item()*, $fun as function(item()) as item()*)) as item()*
Old signature: fn:map($fun as function(item()) as item()*, $seq as item()*) as item()*
Summary Applies the function item $fun to every element of the sequence $seq and returns all of the results as a sequence.
Examples
  • Squaring all numbers from 1 to 10:
    fn:for-each(1 to 10, math:pow(?, 2))
    

    Result: 1 4 9 16 25 36 49 64 81 100

  • Applying a list of functions to a string:
    let $fs := (
      fn:upper-case#1,
      fn:substring(?, 4),
      fn:string-length#1
    )
    return fn:for-each($fs, function($f) { $f('foobar') })
    

    Result: FOOBAR bar 6

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

Updated with Version 7.7: the arguments have been swapped.

Signatures fn:filter($seq as item()*, $pred as function(item()) as xs:boolean)) as item()*
fn:filter($pred as function(item()) as xs:boolean, $seq as item()*) as item()*
Summary Applies the boolean predicate $pred to all elements of the sequence $seq, returning those for which it returns true().
Examples
  • All even integers until 10:
    fn:filter(1 to 10, function($x) { $x mod 2 eq 0 })
    

    Result: 2 4 6 8 10

  • Strings that start with an upper-case letter:
    let $first-upper := function($str) {
      let $first := fn:substring($str, 1, 1)
      return $first eq fn:upper-case($first)
    }
    return fn:filter(('FooBar', 'foo', 'BAR'), $first-upper)
    

    Result: FooBar BAR

  • Inefficient prime number generator:
    let $is-prime := function($x) {
      $x gt 1 and (every $y in 2 to ($x - 1) satisfies $x mod $y ne 0)
    }
    return filter(1 to 20, $is-prime)
    

    Result: 2 3 5 7 11 13 17 19

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
declare function local:filter(
  $seq as item()*,
  $pred as function(item()) as xs:boolean
) as item()* {
  $seq[$pred(.)]
};

fn:for-each-pair

Updated with Version 7.7: the function has been renamed, and the arguments have been swapped.

Signatures fn:for-each-pair($seq1 as item()*, $seq2 as item()*, $fun as function(item(), item()) as item()*) as item()*
Old signature: fn:map-pairs($fun as function(item(), item()) as item()*, $seq1 as item()*, $seq2 as item()*) as item()*
Summary zips the elements from the two sequences $seq1 and $seq2 together with the function $f. It stops after the shorter sequence ends.
Examples
  • Adding one to the numbers at odd positions:
    fn:for-each-pair(
      fn:for-each(1 to 10, function($x) { $x mod 2 }),
      (1, 1, 1, 1, 1),
      function($a, $b) { $a + $b }
    )
    

    Result: 2 1 2 1 2

  • Line numbering:
    let $number-lines := function($str) {
      fn:string-join(
        fn:for-each-pair(
          1 to 1000,
          tokenize($str, '\r?\n|\r'),
          concat(?, ': ', ?)
        ),
        '&#xa;'
      )
    }
    return $number-lines('hello world,
    how are you?')
    

    Result:

    1: hello world,
    2: how are you?
    
  • Checking if a sequence is sorted:
    let $is-sorted := function($seq) {
      every $b in
        fn:for-each-pair(
          $seq,
          fn:tail($seq),
          function($a, $b) { $a le $b }
        )
      satisfies $b
    }
    return (
      $is-sorted(1 to 10),
      $is-sorted((1, 2, 42, 4, 5))
    )
    
    Result: true false
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 with 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 flavours. They differ in the direction in which they traverse the sequence:

fn:fold-left

Updated with Version 7.7: the $seq and $fun arguments have been swapped.

Signatures fn:fold-left($seq as item()*, $seed as item()*, $fun as function(item()*, item()) as item()*) as item()*
Old signature: fn:fold-left($fun as function(item()*, item()) as item()*, $seed as item()*, $seq as item()*) as item()*
Summary The left fold traverses the sequence from the left.

The query fn:fold-left(1 to 5, 0, $f) for example would be evaluated as:

$f($f($f($f($f(0, 1), 2), 3), 4), 5)
Examples
  • Product of a sequence of integers:
    let $product := fn:fold-left(?, 1,
      function($result, $i) { $result * $i }
    )
    return $product(1 to 5)
    

    Result: 120

  • Illustrating the evaluation order:
    fn:fold-left(1 to 5, '$seed',
      concat('$f(', ?, ', ', ?, ')')
    )
    

    Result: $f($f($f($f($f($seed, 1), 2), 3), 4), 5)

  • Building a decimal number from digits:
    let $from-digits := fold-left(?, 0,
      function($n, $d) { 10 * $n + $d }
    )
    return (
      $from-digits(1 to 5),
      $from-digits((4, 2))
    )
    

    Result: 12345 42

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()*,
  $fun as function(item()*, item()) as item()*
) as item()* {
  if(empty($seq)) then $seed
  else local:fold-left(
    fn:tail($seq),
    $fun($seed, fn:head($seq)),
    $fun
  ) 
};

fn:fold-right

Updated with Version 7.7: the $seq and $fun arguments have been swapped.

Signatures fn:fold-right($seq as item()*, $seed as item()*, $fun as function(item(), item()*) as item()*
Old signature: fn:fold-right($fun as function(item(), item()*) as item()*, $seed as item()*, $seq as item()*) as item()*
Summary The right fold fn:fold-right($seq, $seed, $fun) traverses the from the right.

The query fn:fold-right(1 to 5, 0, $f) for example would be evaluated as:

$f(1, $f(2, $f(3, $f(4, $f(5, 0)))))
Examples
  • Product of a sequence of integers:
    let $product := fn:fold-right(?, 1,
      function($i, $result) { $result * $i }
    )
    return $product(1 to 5)
    

    Result: 120

  • Illustrating the evaluation order:
    fn:fold-right(1 to 5, '$seed',
      concat('$f(', ?, ', ', ?, ')')
    )
    

    Result: $f(1, $f(2, $f(3, $f(4, $f(5, $seed)))))

  • Reversing a sequence of items:
    let $reverse := fn:fold-right(?, (),
      function($item, $rev) {
        $rev, $item
      }
    )
    return $reverse(1 to 10)
    

    Result: 10 9 8 7 6 5 4 3 2 1

XQuery 1.0
declare function local:fold-right(
  $seq as item()*,
  $seed as item()*,
  $fun as function(item(), item()*) as item()*
) as item()* {
  if(empty($seq)) then $seed
  else $fun(
    fn:head($seq),
    local:fold-right(tail($seq), $seed, $fun)
  )
};

Note that the order of the arguments of $fun are inverted compared to that in fn:fold-left(...).