On Tuesday, 28 May 2013 at 17:24:13 UTC, H. S. Teoh wrote:
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
I don't think the ordering should change just because the input
type is changed, that would be very confusing, especially when
code is just passing on ranges it's received from somewhere else.
The default should be the simplest ordering (across then down)
and other orderings must be explicitly asked for. When an
incompatible ordering (including using an infinite range for the
"across" range with the default ordering) is being used it should
show a helpful error message suggesting a compatible ordering.
There could also be an ordering constant "dontCare" which simply
picks any ordering compatible with the nature of the input
ranges. I don't think this should be the default because the
common case is that you do care what the ordering is, you should
have to explicitly say that you don't care.
It's also worth mentioning that the rules are more complicated
than have been suggested - using an infinite range with the
default ordering is fine as long as a finite range is used for
the range that is being iterated over more quickly.
