> Wouldn't there be certain problems with implementing DVC
> for this task? The position of every Item depends on all
> previous Items after all.

No, there's usually no problem with this. Look how the DVC version of 
foldl() is implemented in FXSL:


<xsl:stylesheet version="2.0"
 xmlns:f="http://fxsl.sf.net/"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 exclude-result-prefixes="f">

    <xsl:import href="func-apply.xsl"/>
    <xsl:import href="func-drop.xsl"/>

    <xsl:function name="f:foldl">
      <xsl:param name="pFunc" as="element()"/>
      <xsl:param name="pA0"/>
      <xsl:param name="pList" as="item()*"/>

      <xsl:sequence select=
       "if(empty($pList))
          then
             $pA0
          else
             for $vcntList in count($pList) return
               if($vcntList = 1)
                  then
                     f:apply($pFunc, $pA0, $pList[1])
                  else
                     for $vHalfLen in ($vcntList idiv 2) return
                       f:foldl($pFunc,
                             f:foldl($pFunc, $pA0, $pList[position() le 
$vHalfLen]),
                             f:drop($vHalfLen, $pList)
                             )"/>

    </xsl:function>

</xsl:stylesheet>


Something similar is done in FXSL 1.x (For XSLT 1.0).

> Tail recursion would seem like a
> better approach to me, but I not sure there are any XSLT
> processors to date that can optimize it away.

Some do (Net XslCompiledTransform, Saxon6.5, JD are all very good at 
optimizing TR), some don't, and all 3 XSLT 2.0 processors have some 
difficulties -- see more on this here:

   http://dnovatchev.spaces.live.com/Blog/cns!44B0A32C2CCF7488!345.entry

Cheers,
Dimitre Novatchev



<p.lepin@c...> wrote in message 
news:1170317666.788134.59100@v......
> On Feb 1, 3:50 am, "Dimitre Novatchev"
> <dimit...@tpg.com.au> wrote:
>> > Note that on large documents it is likely to barf
>> > all over the stack and die horrible death. So I would
>> > strongly advise against deploying it in production
>>
>> Not necessarily.
>
> I was talking specifically about the implementation I
> provided.
>
>> One can use a DVC (Divide and Conquer) approach, which
>> requires as little as Log2(N) maximum stack depth.
>
> Wouldn't there be certain problems with implementing DVC
> for this task? The position of every Item depends on all
> previous Items after all. Tail recursion would seem like a
> better approach to me, but I not sure there are any XSLT
> processors to date that can optimize it away. (Are there,
> by the way?)
>
> --
> Pavel Lepin
>