The Functional Programming Language XSLT - A proof through examples

Tree processing

The same generalised functions exist not only for lists, but also for trees. A tree is defined as a set of node (root) having a labelX, and a set of sub-trees:

treeof X   ::  node X  [ (treeof X) ]

This effectively defines a datatype of ordered labeled trees, saying that a tree of Xs is a node, with a label which is an X, and a list of subtrees which are also trees of Xs [1]. 

Then we can define foldl-tree as follows:

foldl-tree  f  g  a  ( node, label, subtrees)  = 

            f  label  ( foldl-tree_  f  g  a  subtrees )

foldl-tree_  f  g  a  ( subtree  restSubtrees ) = 

             g (foldl-tree f g a  subtree) ( foldl-tree_  f  g  a   restSubtrees )

 

Probably, a better name for the above function would be fold-top-bottom.

As in the case of the list folding, the tree-folding function can produce a variety of useful functions on trees:

sumtree           =  foldl-tree  add  add  0

producttree       =  foldl-tree  multiply  multiply  1

tree-labels-list  =  foldl-tree  (:)  append  [ ]

maptree  f        =  foldl-tree  (makeNode . f) (:) [ ]

Bellow is the corresponding XSLT implementation:

foldl-tree:

<xsl:stylesheet version = "1.0"     xmlns:xsl="http://www.w3.org/1999/XSL/Transform">          <xsl:template name = "foldl-tree" >              <xsl:param name = "pFuncNode" select = "/.." />              <xsl:param name = "pFuncSubtrees" select = "/.." />              <xsl:param name = "pA0" />              <xsl:param name = "pNode" select = "/.." />              <xsl:choose>                  <xsl:when test = "not($pNode)" >                      <xsl:copy-of select = "$pA0" />                  </xsl:when>                  <xsl:otherwise>                      <xsl:variable name = "vSubtrees" select = "$pNode/*" />                      <xsl:variable name = "vSubTreeResult" >                          <xsl:call-template name = "foldl-tree_" >                              <xsl:with-param name = "pFuncNode"                                              select = "$pFuncNode" />                              <xsl:with-param name = "pFuncSubtrees"                                              select = "$pFuncSubtrees" />                              <xsl:with-param name = "pA0" select = "$pA0" />                              <xsl:with-param name = "pSubTrees"                                              select = "$vSubtrees" />                          </xsl:call-template>                      </xsl:variable>                      <xsl:apply-templates select = "$pFuncNode[1]" >                          <xsl:with-param name = "arg0"                                   select = "$pFuncNode[position() > 1]" />                          <xsl:with-param name = "arg1"                                          select = "$pNode/@tree-nodeLabel" />                          <xsl:with-param name = "arg2"                                          select = "$vSubTreeResult" />                      </xsl:apply-templates>                  </xsl:otherwise>              </xsl:choose>          </xsl:template>          <xsl:template name = "foldl-tree_" >              <xsl:param name = "pFuncNode" select = "/.." />              <xsl:param name = "pFuncSubtrees" select = "/.." />              <xsl:param name = "pA0" />              <xsl:param name = "pSubTrees" select = "/.." />              <xsl:choose>                  <xsl:when test = "not($pSubTrees)" >                      <xsl:copy-of select = "$pA0" />                  </xsl:when>                  <xsl:otherwise>                      <xsl:variable name = "vSubTree1Result" >                          <xsl:call-template name = "foldl-tree" >                              <xsl:with-param name = "pFuncNode"                                              select = "$pFuncNode" />                              <xsl:with-param name = "pFuncSubtrees"                                              select = "$pFuncSubtrees" />                              <xsl:with-param name = "pA0" select = "$pA0" />                              <xsl:with-param name = "pNode"                                               select = "$pSubTrees[1]" />                          </xsl:call-template>                      </xsl:variable>                      <xsl:variable name = "vRestSubtreesResult" >                          <xsl:call-template name = "foldl-tree_" >                              <xsl:with-param name = "pFuncNode"                                               select = "$pFuncNode" />                              <xsl:with-param name = "pFuncSubtrees"                                               select = "$pFuncSubtrees" />                              <xsl:with-param name = "pA0" select = "$pA0" />                              <xsl:with-param name = "pSubTrees"                                    select = "$pSubTrees[position() > 1]" />                          </xsl:call-template>                      </xsl:variable>                      <xsl:apply-templates select = "$pFuncSubtrees" >                          <xsl:with-param name = "arg0"                                 select = "$pFuncSubtrees[position() > 1]" />                          <xsl:with-param name = "arg1"                                           select = "$vSubTree1Result" />                          <xsl:with-param name = "arg2"                                           select = "$vRestSubtreesResult" />                      </xsl:apply-templates>                  </xsl:otherwise>              </xsl:choose>          </xsl:template>      </xsl:stylesheet>

sumTree:

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

producttree:

<xsl:stylesheet version = "1.0"     xmlns:xsl="http://www.w3.org/1999/XSL/Transform"     xmlns:mult-tree="mult-tree"      exclude-result-prefixes = "xsl mult-tree" >          <xsl:import href = "foldl-tree.xsl" />          <mult-tree:mult-tree/>          <xsl:template name = "productTree" >              <xsl:param name = "pTree" />              <xsl:variable name = "vMult"                      select = "document('')/*/mult-tree:*[1]" />              <xsl:call-template name = "foldl-tree" >                  <xsl:with-param name = "pFuncNode" select = "$vMult" />                  <xsl:with-param name = "pFuncSubtrees" select = "$vMult" />                  <xsl:with-param name = "pA0" select = "1" />                  <xsl:with-param name = "pNode" select = "$pTree" />              </xsl:call-template>          </xsl:template>          <xsl:template match = "*[namespace-uri()='mult-tree']" >              <xsl:param name = "arg1" />              <xsl:param name = "arg2" />              <xsl:value-of select = "$arg1 * $arg2" />          </xsl:template>      </xsl:stylesheet>

tree-labels-list:

<xsl:stylesheet version = "1.0"      xmlns:xsl="http://www.w3.org/1999/XSL/Transform"     xmlns:mult-tree="mult-tree"     exclude-result-prefixes = "xsl mult-tree" >          <xsl:import href = "foldl-tree.xsl" />          <mult-tree:mult-tree/>          <xsl:template name = "productTree" >              <xsl:param name = "pTree" />              <xsl:variable name = "vMult" select = "document('')/*/mult-tree:*[1]" />              <xsl:call-template name = "foldl-tree" >                  <xsl:with-param name = "pFuncNode" select = "$vMult" />                  <xsl:with-param name = "pFuncSubtrees" select = "$vMult" />                  <xsl:with-param name = "pA0" select = "1" />                  <xsl:with-param name = "pNode" select = "$pTree" />              </xsl:call-template>          </xsl:template>          <xsl:template match = "*[namespace-uri()='mult-tree']" >              <xsl:param name = "arg1" />              <xsl:param name = "arg2" />              <xsl:value-of select = "$arg1 * $arg2" />          </xsl:template>      </xsl:stylesheet>

mapTree:

<xsl:stylesheet version = "1.0"      xmlns:xsl="http://www.w3.org/1999/XSL/Transform"     xmlns:tree-labels-append="tree-labels-append"     xmlns:tree-labels-cons="tree-labels-cons"      exclude-result-prefixes = "xsl msxsl mapTree-cons mapTree-makeNode-f">          <xsl:import href = "foldl-tree.xsl" />          <mapTree-cons:mapTree-cons/>          <mapTree-makeNode-f:mapTree-makeNode-f/>          <xsl:template name = "mapTree" >              <xsl:param name = "pTree" />              <xsl:param name = "pFun" />              <xsl:variable name = "vmakeNode"                     select = "document('')/*/mapTree-makeNode-f:*[1]" />              <xsl:variable name = "vCons"                     select = "document('')/*/mapTree-cons:*[1]" />              <xsl:variable name = "vFuncNode" >                  <mapTree-makeNode-f:mapTree-makeNode-f/>                  <xsl:copy-of select = "$pFun" />              </xsl:variable>              <xsl:call-template name = "foldl-tree" >                  <xsl:with-param name = "pFuncNode"                         select = "msxsl:node-set($vFuncNode)/*" />                  <xsl:with-param name = "pFuncSubtrees" select = "$vCons" />                  <xsl:with-param name = "pA0" select = "/.." />                  <xsl:with-param name = "pNode" select = "$pTree" />              </xsl:call-template>          </xsl:template>          <xsl:template match = "*[namespace-uri()='mapTree-cons']" >              <xsl:param name = "arg1" />              <xsl:param name = "arg2" />              <xsl:copy-of select = "$arg1" />              <xsl:copy-of select = "$arg2" />          </xsl:template>          <xsl:template match = "*[namespace-uri()='mapTree-makeNode-f']" >              <xsl:param name = "arg0" /> <!-- must contain pFun -->              <xsl:param name = "arg1" /> <!-- must contain the node -->              <xsl:param name = "arg2" /> <!-- must contan pA0 -->              <xsl:variable name = "vFun1Result" >                  <xsl:apply-templates select = "$arg0[1]" >                      <xsl:with-param name = "arg1" select = "$arg1" />                  </xsl:apply-templates>              </xsl:variable>              <xsl:element name = "{name($arg1/..)}" >                  <xsl:apply-templates select = "$arg1" mode = "copy" >                      <xsl:with-param name = "pContents"                          select = "msxsl:node-set($vFun1Result)" />                  </xsl:apply-templates>                  <xsl:copy-of select = "$arg1/../node()[not(self::*)]" />                  <xsl:copy-of select = "$arg2" />              </xsl:element>          </xsl:template>          <xsl:template match = "node()" mode = "copy" >              <xsl:param name = "pContents" />              <xsl:copy>                  <xsl:copy-of select = "$pContents" />              </xsl:copy>          </xsl:template>          <xsl:template match = "@*" mode = "copy" >              <xsl:param name = "pContents" />              <xsl:attribute name = "{name()}" >                  <xsl:copy-of select = "$pContents" />              </xsl:attribute>          </xsl:template>      </xsl:stylesheet>