Implementing Divide and Conquer (Was: Re: Re: Re: look

Tom Myers <tommy at cs dot colgate dot edu> wrote

> and probably Dimitre has already answered (I'm on digest) but
> here's one version, based on the idea that
>    dC(5,"foo") = <X><X><X><X><X>foo</X></X></X></X></X> via
>    dC(0,A) = A
>    dC(2*N,A) = dC(N,dC(N,A))
>    dC(2*N+1,A) = dC(N, dC(N, cons("X",A) ) )
> so I expect stack depth to be O(log(N)), time to be O(N^2),
> max space to be O(N), space allocation to be O(N^2)...rather
> like the tail-recursive except for O(log(N)) instead of O(1)
> stack space, and of course not needing anything special in
> the engine.
> ------------------------------
> 
> <xsl:template name="divConq">
>    <xsl:param name="N" select="10"/>
>    <xsl:param name="A" select="/.."/>
>    <xsl:param name="Ndiv2" select="($N - $N mod 2) div 2"/>
>    <xsl:choose>
>      <xsl:when test="not($N)"><xsl:copy-of select="$A"/></xsl:when>
>      <xsl:otherwise>     
>         <xsl:variable name="onebase"> 
>           <xsl:choose>
>             <xsl:when test="$N mod 2">
>               <X><xsl:copy-of select="$A"/></X>
>             </xsl:when>
>             <xsl:otherwise>
>               <xsl:copy-of select="$A"/>
>             </xsl:otherwise>
>           </xsl:choose>
>         </xsl:variable>
>         <xsl:variable name="halfway">
>           <xsl:call-template name="divConq">
>             <xsl:with-param name="N" select="$Ndiv2"/>
>             <xsl:with-param name="A" select="$onebase"/>
>           </xsl:call-template>
>        </xsl:variable>
>        <xsl:call-template name="divConq">
>           <xsl:with-param name="N" select="$Ndiv2"/>
>           <xsl:with-param name="A" select="$halfway"/>
>        </xsl:call-template>
>     </xsl:otherwise>
>    </xsl:choose>
> </xsl:template>
> ----------------------------------------
> 
> hope that makes sense...

Hi Tom,

It makes sence and it works. 

The good news is that you're seemingly avoiding the problem-specific re-combinatiion
of the partial results (I'm still not convince that this can be generally done for
any problem -- see the examples in my previous post).

The bad news is that your solution cannot be executed in parallel -- at least not
with a language that doesn't have lazy evaluation. It is interesting if somebody can
check whether ghc will parallelize your dvc definition.

Cheers,
Dimitre Novatchev.

__________________________________________________
Do You Yahoo!?
Find a job, post your resume.
http://careers.yahoo.com

 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list