Jeni's Musings

I did wonder about that, but I can’t for the life of me make the template version do any better. Here’s what I’ve been trying: maybe someone else can get Saxon to recognise the tail recursion…

<xsl:template name="my:LevenshteinDistanceB" as="xs:integer">
  <xsl:param name="string1" as="xs:string" select="''" />
  <xsl:param name="string2" as="xs:string" select="''" />
  <xsl:param name="chars1" as="xs:integer*" 
    select="string-to-codepoints($string1)" />
  <xsl:param name="chars2" as="xs:integer*" 
    select="string-to-codepoints($string2)" />
  <xsl:param name="i1" as="xs:integer" select="1" />
  <xsl:param name="i2" as="xs:integer" select="1" />
  <xsl:param name="lastRow" as="xs:integer+" 
    select="for $p in (0 to string-length($string1)) return $p" />
  <xsl:param name="thisRow" as="xs:integer+" select="1" />
  <xsl:choose>
    <xsl:when test="count($chars1) = 0 or $i2 > count($chars2)">
      <xsl:sequence select="$lastRow[last()]" />
    </xsl:when>
    <xsl:otherwise>
      <xsl:variable name="cost" 
        select="min(($lastRow[$i1 + 1] + 1,
                     $thisRow[last()] + 1,
                     $lastRow[$i1] +
                       (if ($chars1[$i1] eq $chars2[$i2]) then 0 else 1)))" />
      <xsl:variable name="nextRow" as="xs:boolean" 
        select="$i1 = count($chars1)" />
      <xsl:call-template name="my:LevenshteinDistanceB">
        <xsl:with-param name="chars1" select="$chars1" />
        <xsl:with-param name="chars2" select="$chars2" />
        <xsl:with-param name="i1" 
          select="if ($nextRow) then 1 else ($i1 + 1)" />
        <xsl:with-param name="i2" 
          select="if ($nextRow) then ($i2 + 1) else $i2" />
        <xsl:with-param name="lastRow" 
          select="if ($nextRow) then ($thisRow, $cost) else $lastRow" />
        <xsl:with-param name="thisRow" 
          select="if ($nextRow) then $i2 + 1 else ($thisRow, $cost)" />
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

Actually, this version made me think of another time when templates are nicer than functions: when you have lots of parameters, it’s helpful to be able to pass them by name rather than position.