List processing

The function  sum  that computes the sum of the elements of a list can be defined as follows:

sum []      =  0

sum (n:ns)  =  n + sum ns

The function  product  that computes the product of the elements of a list can be defined as follows:

product []      =  1

product (n:ns)  =  n  *  product ns

There is something common and general in the above two function definitions -- they define the same operation over a list, but provide different arguments to this operation. The arguments to the general list operation are displayed in bold above.

They are a function  f (+ and * in the described cases)   that takes two arguments and an initial value (0 and 1 in the described cases) to use as a second argument when applying this function to the first element of the list. Therefore, we can define this general operation on lists as a function:

foldl f z [] = z

foldl f z (x:xs) = foldl f (f z x) xs

foldl processes a list from left to right. Its dual function, which processes a list from right to left is foldr:

foldr f z [] = z

foldr f z (x:xs) = f x (foldr f z xs)

We can define many functions just by feeding foldl (or foldr) with appropriate functions and null elements:

sum = foldl add 0

product = foldl multiply 1

sometrue = foldl or false

alltrue = foldl and true

maximum = foldl1 max

minimum = foldl1 min

where foldl1 is defined as foldl which operates on non-empty lists, and min(a1, a2) is the lesser, while max(a1, a2) is the bigger of a couple of values.

append as bs = foldr (:) bs as

map f = foldl ((:).f ) [ ]

where (:) is the function, which adds an element to a list. Here's the corresponding XSLT implementation of foldl, foldr, and some of their useful applications:

foldl:

<xsl:template name = "foldl" >              <xsl:param name = "pFunc" select = "/.." />              <xsl:param name = "pA0" />              <xsl:param name = "pList" select = "/.." />              <xsl:choose>                  <xsl:when test = "not($pList)" >                      <xsl:copy-of select = "$pA0" />                  </xsl:when>                  <xsl:otherwise>                      <xsl:variable name = "vFunResult" >                          <xsl:apply-templates select = "$pFunc[1]" >                              <xsl:with-param name = "arg0" select = "$pFunc[position() > 1]" />                              <xsl:with-param name = "arg1" select = "$pA0" />                              <xsl:with-param name = "arg2" select = "$pList[1]" />                          </xsl:apply-templates>                      </xsl:variable>                      <xsl:call-template name = "foldl" >                          <xsl:with-param name = "pFunc" select = "$pFunc" />                          <xsl:with-param name = "pList" select = "$pList[position() > 1]" />                          <xsl:with-param name = "pA0" select = "$vFunResult" />                      </xsl:call-template>                  </xsl:otherwise>              </xsl:choose>          </xsl:template>

foldr:

<xsl:template name = "foldr" >          <xsl:param name = "pFunc" select = "/.." />          <xsl:param name = "pA0" />          <xsl:param name = "pList" select = "/.." />          <xsl:choose>              <xsl:when test = "not($pList)" >                  <xsl:copy-of select = "$pA0" />              </xsl:when>              <xsl:otherwise>                  <xsl:variable name = "vFunResult" >                      <xsl:apply-templates select = "$pFunc[1]" >                          <xsl:with-param name = "arg0"                                           select = "$pFunc[position() > 1]" />                          <xsl:with-param name = "arg1" select = "$pList[last()]" />                          <xsl:with-param name = "arg2" select = "$pA0" />                      </xsl:apply-templates>                  </xsl:variable>                  <xsl:call-template name = "foldl" >                      <xsl:with-param name = "pFunc" select = "$pFunc" />                      <xsl:with-param name = "pList"                                       select = "$pList[position() &lt; last()]" />                      <xsl:with-param name = "pA0" select = "$vFunResult" />                  </xsl:call-template>              </xsl:otherwise>          </xsl:choose>      </xsl:template>

sum:

<xsl:stylesheet version = "1.0"         xmlns:xsl="http://www.w3.org/1999/XSL/Transform"        xmlns:sum-fold-func="sum-fold-func"        exclude-result-prefixes = "xsl sum-fold-func" >          <xsl:import href = "foldl.xsl" />          <sum-fold-func:sum-fold-func/>          <xsl:template name = "sum" >              <xsl:param name = "pList" select = "/.." />              <xsl:variable name = "sum-fold-func:vFoldFun"                             select = "document('')/*/sum-fold-func:*[1]" />              <xsl:call-template name = "foldl" >                  <xsl:with-param name = "pFunc"                                   select = "$sum-fold-func:vFoldFun" />                  <xsl:with-param name = "pList" select = "$pList" />                  <xsl:with-param name = "pA0" select = "0" />              </xsl:call-template>          </xsl:template>          <xsl:template name = "add"                         match = "*[namespace-uri() = 'sum-fold-func']" >              <xsl:param name = "arg1" select = "0" />              <xsl:param name = "arg2" select = "0" />              <xsl:value-of select = "$arg1 + $arg2" />          </xsl:template>      </xsl:stylesheet>

product:

<xsl:stylesheet version = "1.0"         xmlns:xsl="http://www.w3.org/1999/XSL/Transform"        xmlns:prod-fold-func="prod-fold-func"        exclude-result-prefixes = "xsl prod-fold-func" >          <xsl:import href = "foldl.xsl" />          <prod-fold-func:prod-fold-func/>          <xsl:template name = "product" >              <xsl:param name = "pList" select = "/.." />              <xsl:variable name = "prod-fold-func:vFoldFun"                             select = "document('')/*/prod-fold-func:*[1]" />              <xsl:call-template name = "foldl" >                  <xsl:with-param name = "pFunc"                                   select = "$prod-fold-func:vFoldFun" />                  <xsl:with-param name = "pList" select = "$pList" />                  <xsl:with-param name = "pA0" select = "1" />              </xsl:call-template>          </xsl:template>          <xsl:template name = "multiply"                         match = "*[namespace-uri() = 'prod-fold-func']" >              <xsl:param name = "arg1" select = "0" />              <xsl:param name = "arg2" select = "0" />              <xsl:value-of select = "$arg1 * $arg2" />          </xsl:template>      </xsl:stylesheet>

sometrue:

<xsl:stylesheet version = "1.0"        xmlns:xsl="http://www.w3.org/1999/XSL/Transform"        xmlns:someTrue-Or="someTrue-Or">          <xsl:import href = "foldr.xsl" />          <someTrue-Or:someTrue-Or/>          <xsl:variable name = "vOr"                         select = "document('')/*/someTrue-Or:*[1]" />          <xsl:template name = "someTrue" >              <xsl:param name = "pList" select = "/.." />              <xsl:call-template name = "foldr" >                  <xsl:with-param name = "pFunc" select = "$vOr" />                  <xsl:with-param name = "pA0" select = "''" />                  <xsl:with-param name = "pList" select = "$pList" />              </xsl:call-template>          </xsl:template>          <xsl:template name = "Or"                         match = "*[namespace-uri()='someTrue-Or']" >              <xsl:param name = "arg1" />              <xsl:param name = "arg2" />              <xsl:if test = "$arg1/node() or string($arg2)" >1</xsl:if>          </xsl:template>      </xsl:stylesheet>

alltrue:

<xsl:stylesheet version = "1.0"        xmlns:xsl="http://www.w3.org/1999/XSL/Transform"        xmlns:allTrue-And="allTrue-And">          <xsl:import href = "foldr.xsl" />          <allTrue-And:allTrue-And/>          <xsl:template name = "allTrue" >              <xsl:param name = "pList" select = "/.." />              <xsl:variable name = "vAnd"                            select = "document('')/*/allTrue-And:*[1]" />              <xsl:call-template name = "foldr" >                  <xsl:with-param name = "pFunc" select = "$vAnd" />                  <xsl:with-param name = "pA0" select = "1" />                  <xsl:with-param name = "pList" select = "$pList" />              </xsl:call-template>          </xsl:template>          <xsl:template name = "And"                         match = "*[namespace-uri()='allTrue-And']" >              <xsl:param name = "arg1" />              <xsl:param name = "arg2" />              <xsl:if test = "$arg1/node() and string($arg2)" >1</xsl:if>          </xsl:template>      </xsl:stylesheet>

minimum / maximum:

<xsl:stylesheet version = "1.0"         xmlns:xsl="http://www.w3.org/1999/XSL/Transform"        xmlns:msxsl="urn:schemas-microsoft-com:xslt"        xmlns:minimum-fold-func="minimum-fold-func"        xmlns:minimum-pick-smaller="minimum-pick-smaller"        xmlns:minimum-own-compare="minimum-own-compare"        exclude-result-prefixes = "xsl minimum-fold-func         minimum-own-compare minimum-pick-smaller" >          <xsl:import href = "foldl.xsl" />          <minimum-fold-func:minimum-fold-func/>          <minimum-pick-smaller:minimum-pick-smaller/>          <minimum-own-compare:minimum-own-compare/>          <xsl:template name = "minimum" >              <xsl:param name = "pList" select = "/.." />              <xsl:param name = "pCMPFun" select = "/.." />              <xsl:variable name = "vdfCMPFun"                             select = "document('')/*/minimum-own-compare:*[1]" />              <xsl:variable name = "vFoldFun"                             select = "document('')/*/minimum-pick-smaller:*[1]" />              <xsl:if test = "$pList" >                  <xsl:variable name = "vCMPFun"                                 select = "$pCMPFun | $vdfCMPFun[not($pCMPFun)]" />                  <xsl:variable name = "vFuncList" >                      <xsl:copy-of select = "$vFoldFun" /> <!-- Pick Smaller -->                      <xsl:copy-of select = "$vCMPFun" /> <!-- Compare -->                  </xsl:variable>                  <xsl:call-template name = "foldl" >                      <xsl:with-param name = "pFunc"                                       select = "msxsl:node-set($vFuncList)/*" />                      <xsl:with-param name = "pList" select = "$pList" />                      <xsl:with-param name = "pA0" select = "$pList[1]" />                  </xsl:call-template>              </xsl:if>          </xsl:template>          <xsl:template name = "pickSmaller"                         match = "*[namespace-uri() = 'minimum-pick-smaller']" >              <xsl:param name = "arg0" />              <xsl:param name = "arg1" />              <xsl:param name = "arg2" />              <xsl:variable name = "vIsSmaller" >                  <xsl:apply-templates select = "$arg0" >                      <xsl:with-param name = "arg1" select = "$arg1" />                      <xsl:with-param name = "arg2" select = "$arg2" />                  </xsl:apply-templates>              </xsl:variable>              <xsl:choose>                  <xsl:when test = "$vIsSmaller = 1" >                      <xsl:copy-of select = "$arg1" />                  </xsl:when>                  <xsl:otherwise>                      <xsl:copy-of select = "$arg2" />                  </xsl:otherwise>              </xsl:choose>          </xsl:template>          <xsl:template name = "isSmallerDefault"                         match = "*[namespace-uri() = 'minimum-own-compare']" >              <xsl:param name = "arg1" />              <xsl:param name = "arg2" />              <xsl:choose>                  <xsl:when test = "$arg1 &lt; $arg2" >1</xsl:when>                  <xsl:otherwise>0</xsl:otherwise>              </xsl:choose>          </xsl:template>      </xsl:stylesheet>

append:

<xsl:stylesheet version = "1.0"         xmlns:xsl="http://www.w3.org/1999/XSL/Transform"        xmlns:append-foldr-func="append-foldr-func"        exclude-result-prefixes = "xsl append-foldr-func" >          <xsl:import href = "foldr.xsl" />          <append-foldr-func:append-foldr-func/>          <xsl:template name = "append" >              <xsl:param name = "pList1" select = "/.." />              <xsl:param name = "pList2" select = "/.." />              <xsl:variable name = "vFoldrFun"                             select = "document('')/*/append-foldr-func:*[1]" />              <xsl:call-template name = "foldr" >                  <xsl:with-param name = "pFunc" select = "$vFoldrFun" />                  <xsl:with-param name = "pList" select = "$pList1" />                  <xsl:with-param name = "pA0" select = "$pList2" />              </xsl:call-template>          </xsl:template>          <xsl:template name = "appendL"                         match = "*[namespace-uri() = 'append-foldr-func']" >              <xsl:param name = "arg1" select = "/.." />              <xsl:param name = "arg2" select = "/.." />              <xsl:copy-of select = "$arg1" />              <xsl:copy-of select = "$arg2" />          </xsl:template>      </xsl:stylesheet>

map:

<xsl:stylesheet version = "1.0"         xmlns:xsl="http://www.w3.org/1999/XSL/Transform"        xmlns:msxsl="urn:schemas-microsoft-com:xslt"        xmlns:map-foldl-func="map-foldl-func"        exclude-result-prefixes = "xsl map-foldl-func" >          <xsl:import href = "foldl.xsl" />          <map-foldl-func:map-foldl-func/>          <xsl:template name = "map" >              <xsl:param name = "pFun" select = "/.." />              <xsl:param name = "pList1" select = "/.." />              <xsl:param name = "pList0" select = "/.." />              <xsl:variable name = "vFoldlFun"                             select = "document('')/*/map-foldl-func:*[1]" />              <xsl:variable name = "vFuncComposition" >                  <xsl:copy-of select = "$vFoldlFun" />                  <xsl:copy-of select = "$pFun" />              </xsl:variable>              <xsl:variable name = "vFComposition"                             select = "msxsl:node-set($vFuncComposition)/*" />              <xsl:call-template name = "foldl" >                  <xsl:with-param name = "pFunc" select = "$vFComposition" />                  <xsl:with-param name = "pList" select = "$pList1" />                  <xsl:with-param name = "pA0" select = "/.." />              </xsl:call-template>          </xsl:template>          <xsl:template name = "mapL"                         match = "*[namespace-uri() = 'map-foldl-func']" >              <xsl:param name = "arg0" select = "/.." />              <xsl:param name = "arg1" select = "/.." />              <xsl:param name = "arg2" select = "/.." />              <!-- $arg1 must be A0 -->              <xsl:copy-of select = "$arg1" />              <xsl:variable name = "vFun1Result" >                  <xsl:apply-templates select = "$arg0[1]" >                      <xsl:with-param name = "arg1" select = "$arg2[1]" />                  </xsl:apply-templates>              </xsl:variable>              <xsl:apply-templates select = "$arg2" mode = "copy" >                  <xsl:with-param name = "pContents"                                   select = "msxsl:node-set($vFun1Result)" />              </xsl:apply-templates>          </xsl:template>          <xsl:template match = "*" mode = "copy" >              <xsl:param name = "pContents" />              <xsl:copy>                  <xsl:copy-of select = "$pContents" />              </xsl:copy>          </xsl:template>      </xsl:stylesheet>

doubleall

<xsl:stylesheet version = "1.0"         xmlns:xsl="http://www.w3.org/1999/XSL/Transform"        exclude-result-prefixes = "xsl doubleall" >          <xsl:import href = "map.xsl" />          <doubleall:doubleall/>          <xsl:template name = "doubleall" >              <xsl:param name = "pList" select = "/.." />              <xsl:variable name = "vFunDouble"                             select = "document('')/*/doubleall:*[1]" />              <xsl:call-template name = "map" >                  <xsl:with-param name = "pFun" select = "$vFunDouble" />                  <xsl:with-param name = "pList1" select = "$pList" />              </xsl:call-template>          </xsl:template>          <xsl:template name = "double"                         match = "*[namespace-uri() = 'doubleall']" >              <xsl:param name = "arg1" />              <xsl:value-of select = "2 * $arg1" />          </xsl:template>      </xsl:stylesheet>

sumproducts.
This is a demonstration of the power of using map -- we will produce the sum of the products of all children of any /sales/sale element from the xml document as specified bellow:

xml document:

<sales>          <sale>              <price>3.5</price>              <quantity>2</quantity>              <Discount>0.75</Discount>              <Discount>0.80</Discount>              <Discount>0.90</Discount>          </sale>          <sale>              <price>3.5</price>              <quantity>2</quantity>              <Discount>0.75</Discount>              <Discount>0.80</Discount>              <Discount>0.90</Discount>          </sale>      </sales>

stylesheet:

<xsl:stylesheet version = "1.0"         xmlns:xsl="http://www.w3.org/1999/XSL/Transform"        xmlns:msxsl="urn:schemas-microsoft-com:xslt"        xmlns:test-map-product="test-map-product"        exclude-result-prefixes = "xsl test-map-product" >          <xsl:import href = "sum.xsl" />          <xsl:import href = "map.xsl" />          <xsl:import href = "product.xsl" />          <test-map-product:test-map-product/>          <xsl:output method = "text" />          <xsl:template match = "/" >              <!-- Get: map product /sales/sale -->              <xsl:variable name = "vSalesTotals" >                  <xsl:variable name = "vTestMap"                                 select = "document('')/*/test-map-product:*[1]" />                  <xsl:call-template name = "map" >                      <xsl:with-param name = "pFun" select = "$vTestMap" />                      <xsl:with-param name = "pList1" select = "/sales/sale" />                  </xsl:call-template>              </xsl:variable>              <!-- Get sum map product /sales/sale -->              <xsl:call-template name = "sum" >                  <xsl:with-param name = "pList"                                   select = "msxsl:node-set($vSalesTotals)/*" />              </xsl:call-template>          </xsl:template>          <xsl:template name = "makeproduct"                         match = "*[namespace-uri() = 'test-map-product']" >              <xsl:param name = "arg1" />              <xsl:call-template name = "product" >                  <xsl:with-param name = "pList" select = "$arg1/*" />              </xsl:call-template>          </xsl:template>      </xsl:stylesheet>

Result:

7.5600000000000005