discuss@lists.openscad.org

OpenSCAD general discussion Mailing-list

View all threads

Simulating iteration

JB
Jordan Brown
Sun, Feb 13, 2022 6:15 PM

It occurred to me that with the (development snapshot only) ability to
pass around functions, it would be possible to hide recursion in a
utility function and yield something that looks sort of like iteration.

Here's how you might use it:

sum = function(total, x) total + x;

echo(iterate([1,2,3], sum, 0));

You want to iterate across an iterable (list, range, object),
accumulating some sort of result.

You define a function that accepts the previous result and an entry in
the list, and returns the new result.  The arguments to iterate() are
the iterable, the function, and the initial value for the result.

I've discussed it above in terms of summing numeric values, but it
doesn't care what your function does.  It could concatenate strings, or
find a maximum, or build a list.

Here's the implementation of iterate.

// iterable is the thing to be iterated across - a list,
// range, or object.
// f is the function to process an entry.
// init is the initial value for the result.
// i is used internally to recurse across the iterable.
//
// f is called for each item in the iterable, as f(init, item).
// init is the currently accumulated value, and item is the
// entry from the iterable.  f should return the new value
// for the result.
function iterate(iterable, f, init, i=0) =
    let(iterable = is_list(iterable) ? iterable : [ for (x = iterable) x ])
    i >= len(iterable)
    ?
        init
    :
        iterate(iterable, f, f(init, iterable[i]), i+1);

sum = function (total, x) echo(x) 0;
fm = fontmetrics();
echo(iterate(fm, sum, 0));

Note:  Although it works on objects, what it passes to the function is
the name, rather than the value.  I'm not sure which is more useful, and
maybe it should pass the iterable, the index (or name), and the value so
that your function can use whichever ones are useful to it.

I thought somebody might find this interesting.

It occurred to me that with the (development snapshot only) ability to pass around functions, it would be possible to hide recursion in a utility function and yield something that looks sort of like iteration. Here's how you might use it: sum = function(total, x) total + x; echo(iterate([1,2,3], sum, 0)); You want to iterate across an iterable (list, range, object), accumulating some sort of result. You define a function that accepts the previous result and an entry in the list, and returns the new result.  The arguments to iterate() are the iterable, the function, and the initial value for the result. I've discussed it above in terms of summing numeric values, but it doesn't care what your function does.  It could concatenate strings, or find a maximum, or build a list. Here's the implementation of iterate. // iterable is the thing to be iterated across - a list, // range, or object. // f is the function to process an entry. // init is the initial value for the result. // i is used internally to recurse across the iterable. // // f is called for each item in the iterable, as f(init, item). // init is the currently accumulated value, and item is the // entry from the iterable. f should return the new value // for the result. function iterate(iterable, f, init, i=0) = let(iterable = is_list(iterable) ? iterable : [ for (x = iterable) x ]) i >= len(iterable) ? init : iterate(iterable, f, f(init, iterable[i]), i+1); sum = function (total, x) echo(x) 0; fm = fontmetrics(); echo(iterate(fm, sum, 0)); Note:  Although it works on objects, what it passes to the function is the name, rather than the value.  I'm not sure which is more useful, and maybe it should pass the iterable, the index (or name), and the value so that your function can use whichever ones are useful to it. I thought somebody might find this interesting.
TP
Torsten Paul
Sun, Feb 13, 2022 8:25 PM

On 13.02.22 19:15, Jordan Brown wrote:

It occurred to me that with the (development snapshot only)
ability to pass around functions

That is very much included in the release 2021.01. The dev
snapshot has some fixes, but none of those are critical for
most use cases.

it would be possible to hide recursion in a
utility function and yield something that looks sort of like iteration.

I believe the generic name for that used in other languages
is fold() or accumulate()

https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29

https://github.com/thehans/funcutils#numeric-operations

ciao,
Torsten.

On 13.02.22 19:15, Jordan Brown wrote: > It occurred to me that with the (development snapshot only) > ability to pass around functions That is very much included in the release 2021.01. The dev snapshot has some fixes, but none of those are critical for most use cases. > it would be possible to hide recursion in a > utility function and yield something that looks sort of like iteration. I believe the generic name for that used in other languages is fold() or accumulate() https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29 https://github.com/thehans/funcutils#numeric-operations ciao, Torsten.