# Generic structural recursion

H. S. Teoh hsteoh at quickfur.ath.cx
Wed Jan 26 18:22:18 UTC 2022

```Got stuck on this metaprogramming problem, and can't seem to find a way
to make it work, just wondering if any of you guys can come up with a
clean solution:

I have a bunch of nested structs of the form:

struct S { double data; }
struct T { S s1, s2; }
struct U { S s, T ts; }
struct V { T t, U u; }
... // etc.

and a bunch of functions that operate on structs of this form via
structural recursion, of the following form (the exact number of
parameters of type X differs across functions):

--------
X interpolate(X)(ref X result, double idx, X data1, X data2) {
foreach (field; FieldNameTuple!X) {
alias Type = typeof(__traits(getMember, X, field));
if (is(Type == double))
__traits(getMember, result, field) =
(1.0-idx)*__traits(getMember, data1, field)
+ idx*__traits(getMember, data2, field);
else if (is(Type == struct)) {
interpolate(
__traits(getMember, result, field), idx,
__traits(getMember, data1, field),
__traits(getMember, data2, field));
} else if (is(Type == U[n], U, size_t n)) {
foreach (i; 0 .. n) {
interpolate(
__traits(getMember, result, field)[i], idx,
__traits(getMember, data1, field)[i],
__traits(getMember, data2, field)[i]);
}
}
}
}
--------

IOW, given some number of structs of type X, each function recurses down
the nested structs and invokes some operation (in this case an
interpolation function) on the corresponding double fields of each
argument.

As you can see above, there's a LOT of boilerplate needed for each
function. Whenever I want to change the recursion (e.g., support dynamic
arrays, or exclude certain types from the recursion) I have to modify
every function by hand -- a tedious and error-prone process.  I'd like
to factor out the code that recurses down the nested structs into a
separate template function, say call it structuralRecurse, and have each
of the operations simply call structuralRecurse with some delegate or
function literal that would be invoked on each set of corresponding
double fields.

But so far, I've not been able to do this in its full generality, i.e.,
something of the form:

------
void structuralRecurse(alias fun, T, size_t n)(T t0, T t1, ... T tn) {
// invoke fun(t0.x.y.z, t1.x.y.z, ...); for each double field in T
}
------

Even using a giant string mixin so far hasn't been obvious, because of
the recursive descent required. And I'd like if possible to avoid using
giant string mixins for obvious reasons.

Anybody has any ideas?

T

--
If it breaks, you get to keep both pieces. -- Software disclaimer notice
```