fn:fold-left

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

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

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

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

or its equivalent in XSLT:

<xsl:function name="fn:fold-left" 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="fn:fold-left(fn:tail($seq), $f($zero, fn:head($seq)), $f)"/>
    </xsl:otherwise>
  </xsl:choose>
</xsl:function>
         

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 either the value of $zero or the result of a previous application of $f, and the second is any single item from the sequence $seq.

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 an accumulated result as the first argument, and the next item in 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.

The expression fn:fold-left(1 to 5, 0, function($a, $b) { $a + $b }) returns 15. (This returns the sum of the items in the sequence).

The expression fn:fold-left((2,3,5,7), 1, function($a, $b) { $a * $b }) returns 210. (This returns the product of the items in the sequence).

The expression fn:fold-left((true(), false(), false()), false(), function($a, $b) { $a or $b }) returns true(). (This returns true if any item in the sequence has an effective boolean value of true).

The expression fn:fold-left((true(), false(), false()), false(), function($a, $b) { $a and $b }) returns false(). (This returns true only if every item in the sequence has an effective boolean value of true).

The expression fn:fold-left(1 to 5, (), function($a, $b) {($b, $a)}) returns (5,4,3,2,1). (This reverses the order of the items in a sequence).

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

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

The expression fn:fold-left(1 to 5, map{}, function($map, $n) {map:put($map, $n, $n*2)}) returns map{1:2, 2:4, 3:6, 4:8, 5:10}.