XPath/XQuery fold-right function

Summary

Processes the supplied sequence from right to left, applying the supplied function repeatedly to each item in turn, together with an accumulated result value.

Signature

fn:fold-right(
$seq as item()*,
$zero as item()*,
$f as function(item(), item()*) as item()*
) as item()*

Properties

This function is deterministic, context-independent, focus-independent, higher-order, and special-streaming-rules.

Rules

The effect of the function is equivalent to the following implementation in XQuery:

declare function fn:fold-right(
        $seq as item()*, 
        $zero as item()*, 
        $f as function(item(), item()*) as item()*) 
        as item()* {
  if (fn:empty($seq))
  then $zero
  else $f(fn:head($seq), fn:fold-right(fn:tail($seq), $zero, $f))
};

or its equivalent in XSLT:

<xsl:function name="fn:fold-right" as="item()*">
  <xsl:param name="seq" as="item()*"/>
  <xsl:param name="zero" as="item()*"/>
  <xsl:param name="f" as="function(item(), item()*) as item()*"/>
  <xsl:choose>
    <xsl:when test="fn:empty($seq)">
      <xsl:sequence select="$zero"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:sequence select="$f(fn:head($seq), fn:fold-right(fn:tail($seq), $zero, $f))"/>
    </xsl:otherwise>
  </xsl:choose>
</xsl:function>

Examples

The expression fn:fold-right(1 to 5, 0, function($a, $b) { $a + $b }) returns 15.

The expression fn:fold-right(1 to 5, "", fn:concat(?, ".", ?)) returns "1.2.3.4.5.".

The expression fn:fold-right(1 to 5, "$zero", concat("$f(", ?, ", ", ?, ")")) returns "$f(1, $f(2, $f(3, $f(4, $f(5, $zero)))))".

Error Conditions

As a consequence of the function signature and the function calling rules, a type error occurs if the supplied function $f cannot be applied to two arguments, where the first argument is any item in the sequence $seq, and the second is either the value of $zero or the result of a previous application of $f.

Notes

This operation is often referred to in the functional programming literature as "folding" or "reducing" a sequence. It takes a function that operates on a pair of values, and applies it repeatedly, with the next item in the sequence as the first argument, and the result of processing the remainder of the sequence as the second argument. The accumulated result is initially set to the value of the $zero argument, which is conventionally a value (such as zero in the case of addition, one in the case of multiplication, or a zero-length string in the case of string concatenation) that causes the function to return the value of the other argument unchanged.

In cases where the function performs an associative operation on its two arguments (such as addition or multiplication), fn:fold-right produces the same result as fn:fold-left.