More on "Component Programming"

[Diggory]

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.