More on "Component Programming"

H. S. Teoh hsteoh at quickfur.ath.cx
Tue May 28 10:22:27 PDT 2013


On Tue, May 28, 2013 at 11:37:06AM +0200, bearophile wrote:
> Timothee Cour:
> 
> >python uses itertools.product which is lexicographic_depth.  Like you
> >say, no-one can agrees what the order should be, so let's leave it up
> >to user through a template. Sounds like a no-brainer to me.  There
> >are use cases for each order I mentioned.
> 
> Different cases enjoy different orderings, so giving it a
> compile-time enum is OK. But I prefer the order of 9878 to be the
> default one, because it's the most commonly needed by me, and it's
> what I expect when I port Python code to D.
[...]

OK, I'm looking at the code to see how this could be implemented, and it
seems to require some complications:

If both ranges are infinite, then the ordering needs to be Andrei's
suggested ordering (incremental 2D square). It *can* have other
orderings too, like diagonals, but that requires bidirectional ranges,
not just forward ranges.

If only one range is infinite, then it is allowed to be an input range,
but that constrains it to a specific ordering (namely, finite range
first, then increment infinite range). If the infinite range is more
than an input range, then of course other orderings are possible, but
explicitly supporting those cases seems to be a lot of work for very
little added value.

If both ranges are finite, then many different orderings are possible,
but again it depends on the nature of the ranges. If one of them is an
input range, then the other must be a forward range, and the order is
constrained.

The biggest problem here is, what should be the default ordering for the
template? There is no single ordering that will work for every case.

Furthermore, how many different kinds of orderings should be supported?
There are a lot of possibilities, even just in the finite case (if the
ranges are both bidirectional, for example -- who's to say we should
exclude a Peano-curve traversal of the cartesian product, or everything
in between?). Even restricting ourselves to the simplest orderings,
there's the question of how to efficiently implement something like
Andrei's 2D traversal when you have two finite ranges of different
lengths.

Currently, I'm inclined to say, the library gets to decide on the
ordering based on its inputs. I'd rather the template require minimal
functionality from its input ranges and automatically decide on which
ordering is best. I'd just follow bearophile's suggestion for the finite
case -- the ordering in issue 9878 is certainly the most useful, and
most likely expected (most uses of cartesian products would expect an
ordering analogous to binary enumeration, I think). While adding an enum
to specify the exact ordering is certainly possible, I'm not sure if
it's adding enough value to justify the complications in the
implementation.


T

-- 
Gone Chopin. Bach in a minuet.


More information about the Digitalmars-d mailing list