Hi Guiseppe,
unfortunately the example won’t be tail-call optimized as your last statement is not the function call itself but a sequence construction that happens to contain the function call.
Your function must be of the form:
f(x) => s(x) if your termination condition is met (i.e. no more books) f(x) => f(g(x))
Your function is defined (more or less) as something like:
f(x) => s(x) if your termination condition is met (i.e. no more books) f(x) => something + f(g(x))
So you have to get that something (i.e. the sequence concatenation) part inside your g-function, here’s what I think you might want:
Cross-posted as gist for better readability https://gist.github.com/micheee/ef75c9f30449c2de3406182ff2fdce50 https://gist.github.com/micheee/ef75c9f30449c2de3406182ff2fdce50
declare variable $bookstore := <bookstore>{ for $i in 1 to 300000 return element book { element name { "Book " || $i }, element price { 1 }, element author { "Author "|| $i } } } </bookstore>;
(:~ Rolling total of prices @param $prices, accumulates the book prices. $prices[$n] contains the sum of prices for $book[position() <= $n] @param $books sequence of books not yet added to $prices :) declare function local:sum($prices, $books) { let $book := head($books) (: Get first book in sequence :) let $prices := if(count($prices) = 0) (: if empty, initialize prices with first price :) then ($book/price ) else ( (: add the current rolling total to the list of rolling totals :) (: that’s the concatenation part :) $prices, element price { $prices[count($prices)] + $book/price } ) return ( if(count($books) > 1) then local:sum($prices, tail($books)) (: here's the tail call :) else $prices ) };
<prices> { local:sum((), $bookstore/book) } </prices>
You can check if your query is tail-call optimized using the query info panel:
- mark as tail call: local:sum(if(empty($prices_2)) then (hea...
Hope this helps!
Best from Konstanz
Michael
Am 18.02.2019 um 19:12 schrieb Giuseppe G. A. Celano celano@informatik.uni-leipzig.de:
Hi Jonathan,
Thanks for that. However, it returns the same stack overflow error as the other script, when <book/> are 38000. Encreasing the JVM size does not help either.
E-mail: celano@informatik.uni-leipzig.de mailto:celano@informatik.uni-leipzig.de Web site 1: http://asv.informatik.uni-leipzig.de/en/staff/Giuseppe_Celano http://asv.informatik.uni-leipzig.de/en/staff/Giuseppe_Celano Web site 2: https://sites.google.com/site/giuseppegacelano/ https://sites.google.com/site/giuseppegacelano/
On Feb 18, 2019, at 4:51 PM, Jonathan Robie <jonathan.robie@gmail.com mailto:jonathan.robie@gmail.com> wrote:
To make it tail-recursive, make the recursive call the last operation in the function.
https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call
The else() clause is what keeps it from being tail recursive. Something like this should work:
declare variable $bookstore := <bookstore>
<book> <name>story</name> <price>50.00</price> <author>smith</author> </book> <book> <name>history</name> <price>150.00</price> <author>kelly</author> </book> <book> <name>epic</name> <price>300.00</price> <author>jones</author> </book> </bookstore>;
declare function local:sum($books, $sum) { let $sum := $sum + $books[1]/price return ( <price>{ $sum }</price>, $books[2] ! local:sum(tail($books), $sum) ) };
<prices> { local:sum($bookstore/book, 0) } </prices>
Jonathan
On Mon, Feb 18, 2019 at 10:24 AM Giuseppe G. A. Celano <celano@informatik.uni-leipzig.de mailto:celano@informatik.uni-leipzig.de> wrote: I am writing a recursive function which is similar to the one here:
https://stackoverflow.com/questions/27702718/to-add-values-in-cumulative-for... https://stackoverflow.com/questions/27702718/to-add-values-in-cumulative-format
Interestingly, local:sum() works if there are not many <book/>. However with 38000 book element I get the error "Stack Overflow: Try tail recursion".
Any idea?
Ciao, Giuseppe