 | Posted by hsteoh@quickfur.ath.cx |  Permalink Reply |
|
hsteoh@quickfur.ath.cx 
| https://issues.dlang.org/show_bug.cgi?id=11306
--- Comment #3 from hsteoh@quickfur.ath.cx ---
Here are some thoughts I had about how to approach this. This is probably still incomplete, but I want to put this here so that it doesn't get lost.
If all n argument ranges are finite forward ranges, then we basically have unconstrained cartesianProduct evaluation order, so we can potential have n! different orderings for the output. These can probably be specified as a compile-time array of indices (basically some permutation of [0, 1, 2, ... (n-1)]).
If one of the argument ranges is a non-forward input range (and there cannot be more than one such argument, otherwise it's not possible to compute the cartesian product), then this range must always iterate the slowest, because otherwise it's not possible to compute the cartesian product (some combinations will be missed since we can't rewind the input range). So in this case, assuming the remaining arguments are all finite forward ranges, then the user may specify (n-1)! possible orderings of the output.
In either case, the implementation is not that difficult: cartesianProduct.Result.popFront just traverses the ranges in a different order than the argument order, as specified by the compile-time array of indices (a permutation of [0, 1, 2, ... (n-2)]).
In essence, this amounts to permuting the argument ranges such that lexicographic ordering corresponds with the ordering the user desires, with .front permuting the elements of the tuple back into argument order. Non-forward input ranges will always be pushed to the front of the permuted arguments.
If there are any infinite ranges, they probably should also be pushed to the front of the permuted arguments (and if there are both infinite arguments and non-forward input ranges, then the latter must be among the infinite arguments, and will always be pushed to the front of the arguments, otherwise it is impossible to evaluate the cartesian product -- it is impossible to compute the cartesian product of a finite non-forward input range with an infinite range). All infinite ranges, except possibly for one, must be at least forward ranges. Infinite ranges do not allow arbitrary reorderings, because there are only limited traversal schedules that will cover all elements in the cartesian product. While there is still some amount of flexibility here (esp. if you have random access infinite ranges), this could lead to an explosion of complexity in the implementation -- how will the user specify a certain ordering, for example -- so I'm inclined to just say that the user cannot specify the iteration ordering for infinite ranges.
So in summary, computing a cartesian product of n finite forward ranges with m
infinite ranges with a non-forward input range (there cannot be more than 1 of
the latter) amounts to:
- permuting the ranges to form the sequence (I,J1,J2,J3,...,K1,K2,K3...) where
I = non-forward input range, J1..Jm = infinite ranges, and K1..Kn = finite
forward ranges.
- Evaluating the cartesian product using the current ordering (i.e.,
lexicographic on K1..Kn, n-dimensional generalization of Andrei's
expanding-square schedule for J1..Jm, over each element of I)
- Permuting the resulting tuple back to argument order in .front.
- The user will be able to specify the ordering of K1..Kn in terms of which
ones should iterate faster than which others, but the evaluation order of
(I,J1..Jm) will be dictated by the implementation.
So far, the above steps are relatively easy to implement, except for the n-dimensional generalization of Andrei's expanding square schedule for infinite forward ranges. The only approach I can currently think of is equivalent to the "old" variadic cartesianProduct implementation, which expands an exponential number of templates -- clearly infeasible beyond the most trivial cases.
Having said that, though, I have trouble imagining what use cases there are for generating n-order cartesian products of infinite ranges for large n -- it will take forever to get to the combination you want, for example, and you might as well use more direct methods of construction to get it!
--
|
