The Functional Programming Language XSLT - A proof through examples

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 = "foldr" >                      <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>