Jeni's Musings

Here’s the XQuery implementation of the dynamic programming version. (I’ve used the same style as you, in particular omitting variable declarations where they’re unnecessary.)

declare function local:levB($arg1 as xs:string, 
                            $arg2 as xs:string) as xs:decimal
{
  local:levB(string-to-codepoints($arg1), 
             string-to-codepoints($arg2),
             1, 1,
             for $p in (0 to string-length($arg1)) return $p,
             1)
}

declare function local:levB($chars1 as xs:integer*,
                            $chars2 as xs:integer*,
                            $i1 as xs:integer,
                            $i2 as xs:integer,
                            $lastRow as xs:integer+,
                            $thisRow as xs:integer+)
  as xs:decimal
{
  if ($i1 > count($chars1)) then
    if ($i2 = count($chars2)) then $thisRow[last()] else
    local:levB($chars1, $chars2, 
               1, $i2 + 1, $thisRow, $i2 + 1) else
  local:levB($chars1, $chars2, $i1 + 1, $i2, $lastRow,
    ($thisRow,
     min((
       $lastRow[$i1 + 1] + 1,
       $thisRow[last()] + 1,
       $lastRow[$i1] + 
         (if ($chars1[$i1] = $chars2[$i2]) then 0 else 1)
     ))
    )
  )
};

Unsurprisingly, it gives exactly the same “infinite recursion” error with Saxon when comparing strings over 20 characters in length.

I’ll leave XSLT vs. XQuery debates for another time…