On 09/13/2018 07:37 PM, Ronaldo Persiano wrote: > However, I don't see any way to write a tail recursion solution > to generate a list without resorting to /concat/. > True, but that still makes it an issue with how concat works and not with the tail-recursion elimination which *is* running as a loop. There is probably a way to prevent all that copying as by definition there is no modification of existing vectors. > So, tail recursion will be generally less competitive than > iterations for list generations. > Yes, I guess that's a fair point looking from user perspective. ciao, Torsten.

Ronaldo: "This approach would benefit from a better implementation of concat." Torsten: "There is probably a way to prevent all that copying as by definition there is no modification of existing vectors." Pretty much every functional language has an operation that appends an element onto the head of a list in constant time. In Lisp, this operation is called "cons". The result is internally represented as a linked list that can be traversed from front to back in linear time, same as an array, but indexing into the middle of the linked list requires linear time instead of constant time. So we could consider adding a 'cons(element, list)' operation that returns a new list in constant time. Internally, there would be two list representations: the existing representation as a C++ std::vector, and a new representation (a linked list node or "cons" node) that contains the first element and a list containing the remaining elements. But both representations are just lists from the user's perspective: they print the same and support the same set of operations. If you google "functional data structures", you will see that cleverer and more complicated solutions exist. An alternative is to replace std::vector with a general purpose functional list data structure. And that might speed up `concat` in Ronaldo's program. By contrast, with my solution, `concat` behaves the same as before, and returns a flat list represented as a std::vector. So existing code needs to be changed to use `cons` in order to get a performance benefit. But, maybe my solution is easier to implement? I was thinking that Value::type() would return VECTOR for a linked list, and Value::toVector() would internally modify a linked list to a vector, modifying the Value to the new representation, before returning a vector. But some operations would be modified to detect a linked list and operate efficiently on it without converting it to a vector. The idea is to limit the amount of code that needs to be changed. On 13 September 2018 at 15:11, Torsten Paul <Torsten.Paul@gmx.de> wrote: > On 09/13/2018 07:37 PM, Ronaldo Persiano wrote: > >> However, I don't see any way to write a tail recursion solution >> to generate a list without resorting to /concat/. >> > > > True, but that still makes it an issue with how concat works and > not with the tail-recursion elimination which *is* running as a > loop. > There is probably a way to prevent all that copying as by > definition there is no modification of existing vectors. > > > So, tail recursion will be generally less competitive than > > iterations for list generations. > > > Yes, I guess that's a fair point looking from user perspective. > > > ciao, > Torsten. > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >