Subject: Re: [xsl] Functional program for "list sum" From: David Carlisle <davidc@xxxxxxxxx> Date: Thu, 9 Jun 2005 17:33:27 +0100 |
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() > 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() > 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() < $n]) + fn:listSum3($list[position() >= $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 ________________________________________________________________________
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Functional program for "l, Mukul Gandhi | Thread | Re: [xsl] Functional program for "l, Aron Bock |
Re: [xsl] Functional program for "l, Mukul Gandhi | Date | [xsl] Process node set generated by, Mat Bergman |
Month |