Barnsley Fern recursive

classic Classic list List threaded Threaded
22 messages Options
12
tp3
Reply | Threaded
Open this post in threaded view
|

Re: Barnsley Fern recursive

tp3
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
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
-- Torsten
Reply | Threaded
Open this post in threaded view
|

Re: Barnsley Fern recursive

doug.moen
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 <[hidden email]> 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
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
12