Hi Graydon,
On 2021-06-04 at 18:35, Graydon Saunders wrote:
In ~150 ms, I get
Error: Stack Overflow: Try tail recursion?
so I have written the function wrong. What's the more useful pattern for this case?
As the helpful error message suggests, the recursion in your algorithm your algorithm is so deep (one level per item in the `$before` and `$after` lists) that it runs out of stack space. Since BaseX implements "tail-call optimization", you can avoid that problem by rewriting your function so that all recursive calls are in a "tail position" within the function body, as roughly described on Wikipedia [1]. In BaseX tail calls can be inside (at least) nested layers of the `then` and `else` branches of `if`, the results of a `switch` or `typeswitch` and in the `return` of a FLWOR expression in which each clause is statically known to produce either 0 or 1 result/binding.
In your case you can gather all results in an additional, accumulating parameter of the function and return everything at once at the end:
declare function local:subtractSentences( $before as xs:string*, $after as xs:string*, $out as xs:string* ) as xs:string* { let $thisBefore as xs:string? := head($before) let $thisAfter as xs:string? := head($after) return if (empty($thisBefore) or empty($thisAfter)) then ( ($out, $after) ) else ( let $new-output := if(not(ends-with($thisAfter, $thisBefore))) then $thisAfter else replace($thisAfter, $thisBefore, '') return local:subtractSentences( tail($before), tail($after), ($out, $new-output) ) ) };
Here the only recursive call is in tail position inside the function body because the only expressions surrounding it are two FLWOR expressions with only `let` and `return` clauses and an `else`. It therefore does not consume unlimited stack space any more.
You can also check compilation output in the "Info" panel of the BaseX GUI to see if a function call was identified as a tail call. I see the following line:
- mark as tail call: local:subtractSentences(tail($before_0), tail($after_1), ($out_2, (if(ends-with($thisAfter_4, $thisB...
Hope that helps!
Cheers, Leo