It may be possible to use some purely functional data structures in
OpenSCAD. Unlike the 2-3 tree, these data structures are designed to be
efficient in a language with only immutable objects.

https://en.wikipedia.org/wiki/Purely_functional_data_structure

OpenSCAD is missing some language features needed by some functional data
structures, but maybe this is a starting point.

On 30 January 2018 at 18:22, Ronaldo Persiano rcmpersiano@gmail.com wrote:

variables can point to the same immutable list object. There is no need for
OpenSCAD to make copies of lists, since there are no operations for mutating
a list. AFAIK; I haven't read all the code in the interpreter.

The 2-3 tree implementation should only replace the nodes on the insertion
or removal path which should individually take a fixed amount of time.  I
don't understand how it will take O( N^2 ) time and would really like to
understand.  (Even if OpenSCAD is copying the lists every time, it seems
like it should be at worst O(N (log N)^2).)

--
Sent from: http://forum.openscad.org/

Under my initial hyphotesis that copies are made, an insertion or deletion
from a 2-3 tree with N element would be O(N). And to build a tree from
scratch the time would be O(N^2). It is hard to get good time estimates
with the OpenSCAD system but I got worst than linear time building trees by
insertion of 2500-30000 elements.

To minimize stack overflows I have used the tail recursive versions:

function treeinsert(tree,value)=
(0==len(tree))?
[value]  :
(treeinsertiterate(tree,value))[1] ;

function treeinsertlisti(tr,list,i)=
(i==0)?
treeinsert(tr,list[0]) :
treeinsertlisti(treeinsert(tr,list[i]),list,i-1)  ;

BTW, your insertion code does not deal well with some sequences having
repeated values.

ECHO: foo = [40, 57, 65, 14, 65, 80, 82, 65]

ECHO: bar = [[14, 40], 57, [65], 80, [65]]

2018-01-30 21:59 GMT-02:00 NateTG nate-openscadforum@pedantic.org:

from a 2-3 tree with N element would be O(N). And to build a tree from
scratch the time would be O(N^2).

Those are both totally plausible to me.  I may have misunderstood this:

Where I thought the claim was that a single insertion was O(N^2).

Building a tree from N elements is expected to take O(N log N) time - which
is worse than linear.

Thanks for that info.  I still don't really understand the "this tail
recurses" thing.

--
Sent from: http://forum.openscad.org/

​
​Yes, I mixed things up.​

I still don't really understand the "this tail

<goog_634797904>
​
https://en.wikibooks.org/wiki/OpenSCAD_User_Manual/User-Defined_Functions_and_Modules#Recursive_functions

​
http://forum.openscad.org/Tail-recursion-td17040.html
http://forum.openscad.org/Tail-recursion-td17040.html

​

and returns stack up and grow the stack, but a tail return
can avoid putting a redundant return on the stack.

Another way to think about it is a recursive call can be
a goto, and not grow the stack.

--

Best Regards.
This is unedited.
This message came out of me
via a suboptimal keyboard.

I understand what tail recursion is. I'm just not confident about when or how
it gets applied in OpenSCAD.

It would be nice if that were true, but the nature of OpenSCAD means that
things can easily get stack constrained. even when they are working
properly.  For example, Ronaldo didn't modify the tree insertion function
for some aesthetic reason but rather because stack overflows were a
practical issue.

--
Sent from: http://forum.openscad.org/

"I understand what tail recursion is. I'm just not confident about when or
how
it gets applied in OpenSCAD."

The tail recursion optimization is only applied in two very specific
circumstances. It is not implemented in a general way.

The first case:

function f(x) = shouldExit ? result : f(...);

Note that there is a tail recursive function call after the :

The second case:

function f(x) = keepGoing ? f(...) : result;

Note that there is a tail recursive function call between ? and :

The body of the function must match one of the two patterns. If you change
these patterns in any way (eg, add a 'let' to define local variables), then
the pattern no longer matches, and tail recursion optimization is not
applied.

On 31 January 2018 at 13:22, NateTG nate-openscadforum@pedantic.org wrote:

Not always it is easy to write a tail recursion qualified to elimination.
And  sometimes it is possible to avoid the recursion at all using a C-like
for enabled in a snapshot version. The treeinsertlist(() function, for
instance, may be rewritten iteractively as:

function treeinsertlist(tree,list) =
[for(i=len(list), tr=tree; i>=0; i=i-1, tr = treeinsert(tr,list[i]) )
if(i==0) tr ][0];

I am not an advocate of this form that is not easily grasped, but a complex
tail recursion elimination form may be also hard to read.

2018-01-31 16:33 GMT-02:00 doug moen doug@moens.org:

Do you have any pointers to documentation about how to implement tail
recursion or how it's implemented in some language?

I was searching for that some time ago and there's lots of discussion
about how to use tail recursion but not so much about how to actually
implement it.

ciao,
Torsten.