Re: [xsl] Functional program for "list sum"

[David Carlisle <davidc@xxxxxxxxx>]

  Hello Dimitre,
    Can I hope to get response from you ..


It's not clear what respnse you wanted from Dimitre (I already pointed
out the lines generating the error message that you quoted)

But anyway here are three classic functional definitions of a list
accumulator like sum:


<?xml version="1.0"?> 
 <xsl:stylesheet
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"; 
                
 xmlns:xs="http://www.w3.org/2001/XMLSchema";
                 xmlns:fn="http://whatever";
                 version="2.0">
  
  <xsl:output method="text" /> 
 
  <xsl:template match="/">
1:     <xsl:value-of select="fn:listSum1((1,2,3,4,5))" />
2:     <xsl:value-of select="fn:listSum2((1,2,3,4,5))" />
3:     <xsl:value-of select="fn:listSum3((1,2,3,4,5))" />
  </xsl:template>
  
 <xsl:function name="fn:listSum1" as="xs:integer">
 <xsl:param name="list" as="xs:integer*" />
     <xsl:sequence
 select="
 if (empty($list)) then 0 else $list[1] + fn:listSum1($list[position() &gt; 1])"
 />
 </xsl:function>

 <xsl:function name="fn:listSum2" as="xs:integer">
 <xsl:param name="list" as="xs:integer*" />
     <xsl:sequence
 select="fn:listSum2b(0,$list)"/>
 </xsl:function>
 
<xsl:function name="fn:listSum2b" as="xs:integer">
 <xsl:param name="sum" as="xs:integer" />
 <xsl:param name="list" as="xs:integer*" />
     <xsl:sequence
 select="
 if (empty($list)) then $sum  else fn:listSum2b($sum +  $list[1] , $list[position() &gt; 1])"
 />
 </xsl:function>

 <xsl:function name="fn:listSum3" as="xs:integer">
 <xsl:param name="list" as="xs:integer*" />
<xsl:variable name="n" select="1 + count($list) idiv 2"/>
   <xsl:sequence
 select="
 if (empty($list)) then 0 else(
 if ($n = 1) then $list else
 fn:listSum3($list[position() &lt; $n]) + fn:listSum3($list[position() &gt;= $n]))"
 />
 </xsl:function>
 
 </xsl:stylesheet>

$ saxon8 fsum.xsl  fsum.xsl

1:     15
2:     15
3:     15


The first one is the most direct recursive definition.
This has the disadvantage that the intermediate results are built up
using the processor's  function calling stack and unless it is very smart
it will have to stack up the entire local state of each invocation of
the function, so this can get expensive and the list is restricted to
the depth of stack spported by your processor.

The second one is a tail recursive version of the first, instead of
building up the value on the processor's stack you have an explict
(first) argument in which the sum is accumulated. The value returned by
any recursive call to a function is not used in any expression (other
than a conditional) and is simply past on as the result of the function
because the call is in this form ("tail recursive") The processor
doesn't need to save any local state (as it knows (or could know) that
the local state of the function is never used, which means basically
that recursion can be implemented as a loop.


The third is using divide and conquer which is a more general method of
reducing the exposure to the function call stack (not all functions can
be written in tail recursive form). Here the sum of a list is
essentiall coded as the sum of the first half of the list plus the sum
of the second.

Given a functional library (like FXSL) You wouldn't need to specify the
recursions explictly you would just express that you wanted to fold the
binary function "+" over the list. If you look at the above definitions
you would work equally well for any function they just need to be
parameterised to take the binary function to use "+"  and the value to
start with "0". That parameterised version is essentially all fold is.


David



________________________________________________________________________
This e-mail has been scanned for all viruses by Star. The
service is powered by MessageLabs. For more information on a proactive
anti-virus service working around the clock, around the globe, visit:
http://www.star.net.uk
________________________________________________________________________