[OpenSCAD] Barnsley Fern recursive

doug moen doug at moens.org
Thu Sep 13 16:20:36 EDT 2018


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 at 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 at lists.openscad.org
> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openscad.org/pipermail/discuss_lists.openscad.org/attachments/20180913/9b269dcd/attachment.html>


More information about the Discuss mailing list