Hi Michael - that's a very nice solution! Thanks for sharing!
On Tue, Feb 19, 2019 at 6:14 AM Michael Seiferle ms@basex.org wrote:
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
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 Web site 1: http://asv.informatik.uni-leipzig.de/en/staff/Giuseppe_Celano Web site 2: https://sites.google.com/site/giuseppegacelano/
On Feb 18, 2019, at 4:51 PM, Jonathan Robie 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
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> 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...
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