Page 5 of 11

 

Previous Page Table Of ContentsNext Page
Table of Contents

  Introduction
 Starting point
 Major FP design patterns/functions in XSLT
 List processing
 Tree processing
 Lazy evaluation
 Advanced XSLT FP applications
 Square root
 Numerical differentiation
 Numerical integration
 Summary


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>

Page 5 of 11

 

Previous Page Table Of ContentsNext Page

SourceForge.net Logo