On 03/28/14 20:00, H. S. Teoh wrote:
> Today I ran into an interesting situation where I have a function f that needs to return ranges of different types (but identical element types):
> 
> 	auto f(A...)(A args) {
> 		...
> 		if (someCondition)
> 			return cartesianProduct(x, y)
> 				.joiner;
> 		else
> 			return cartesianProduct(x, y)
> 				.joiner
> 				.filter!someFilter;
> 	}
> 
> This obviously can't compile, because the return types are not the same. (Note that someCondition is only known at runtime.) But abstractly speaking, it *should* work, because the element type of the returned range is identical.
> 
> So how would I implement something like this?

eg
 	auto f(A...)(A args) {
 		...
 		return cartesianProduct(x, y)
 			.joiner
 			.filter!(a=>somecondition?true:somefilter(a));
 	}

artur

On Fri, Mar 28, 2014 at 10:44:11PM +0100, Artur Skawina wrote:
> On 03/28/14 20:00, H. S. Teoh wrote:
> > Today I ran into an interesting situation where I have a function f that needs to return ranges of different types (but identical element types):
> > 
> > 	auto f(A...)(A args) {
> > 		...
> > 		if (someCondition)
> > 			return cartesianProduct(x, y)
> > 				.joiner;
> > 		else
> > 			return cartesianProduct(x, y)
> > 				.joiner
> > 				.filter!someFilter;
> > 	}
> > 
> > This obviously can't compile, because the return types are not the same.  (Note that someCondition is only known at runtime.) But abstractly speaking, it *should* work, because the element type of the returned range is identical.
> > 
> > So how would I implement something like this?
> 
> eg
>  	auto f(A...)(A args) {
>  		...
>  		return cartesianProduct(x, y)
>  			.joiner
>  			.filter!(a=>somecondition?true:somefilter(a));
>  	}
[...]

It's not that simple, though.  I guess I gave a bad example. In the actual code, someCondition decides whether or not a cartesian product is even used. So the return range needs to somehow switch between a cartesianProduct filtered by some filters, vs. an alternative algorithm filtered by some other filters.


T

-- 
Famous last words: I *think* this will work...

On Friday, 28 March 2014 at 22:12:02 UTC, H. S. Teoh wrote:
> On Fri, Mar 28, 2014 at 10:44:11PM +0100, Artur Skawina wrote:
>> eg
>>  	auto f(A...)(A args) {
>>  		...
>>  		return cartesianProduct(x, y)
>>  			.joiner
>>  			.filter!(a=>somecondition?true:somefilter(a));
>>  	}
> [...]
>
> It's not that simple, though.  I guess I gave a bad example. In the
> actual code, someCondition decides whether or not a cartesian product is
> even used. So the return range needs to somehow switch between a
> cartesianProduct filtered by some filters, vs. an alternative algorithm
> filtered by some other filters.
>
>
> T

That would have been my solution too (though maybe using a delegate, to not re-evaluate "someconditon" per-element).

If both ranges are completely incompatible, then I'd either:
- array them into submission until they reach a single type.
- return both types, but have only 1 usable (eg, a tuple(type1, type2, index)), and let the caller worry about it.

Or alternativelly, do it pass by ref style:
alias Result1 = /+Define complicated alias1 here+/
alias Result2 = /+Define complicated alias2 here+/

size_t f(A...)(ref Result1 res1, ref Result2 res2, A args) {
		...
		if (someCondition)
  {
			res1 = cartesianProduct(x, y)
				.joiner;
    return 0;
  }
		else
  {
			res2 cartesianProduct(x, y)
				.joiner
				.filter!someFilter;
  return 1;
  }
}

I think this has the "advantage" of delegating the choice of how to merge the results: Take a single fork? Use an algebraic? Caller decides.

On 03/28/14 23:10, H. S. Teoh wrote:
> On Fri, Mar 28, 2014 at 10:44:11PM +0100, Artur Skawina wrote:
>> On 03/28/14 20:00, H. S. Teoh wrote:
>>> Today I ran into an interesting situation where I have a function f that needs to return ranges of different types (but identical element types):
>>>
>>> 	auto f(A...)(A args) {
>>> 		...
>>> 		if (someCondition)
>>> 			return cartesianProduct(x, y)
>>> 				.joiner;
>>> 		else
>>> 			return cartesianProduct(x, y)
>>> 				.joiner
>>> 				.filter!someFilter;
>>> 	}
>>>
>>> This obviously can't compile, because the return types are not the same.  (Note that someCondition is only known at runtime.) But abstractly speaking, it *should* work, because the element type of the returned range is identical.
>>>
>>> So how would I implement something like this?
>>
>> eg
>>  	auto f(A...)(A args) {
>>  		...
>>  		return cartesianProduct(x, y)
>>  			.joiner
>>  			.filter!(a=>somecondition?true:somefilter(a));
>>  	}
> [...]
> 
> It's not that simple, though.  I guess I gave a bad example. In the actual code, someCondition decides whether or not a cartesian product is even used. So the return range needs to somehow switch between a cartesianProduct filtered by some filters, vs. an alternative algorithm filtered by some other filters.

D is statically typed -- there is no way for one function to return
different types that are selected by a runtime condition.
The fact that the produced elements have the same type is irrelevant.

You can wrap the range in a common one. When the above approach isn't enough, there's always the next level:

   struct DynRange(R, F...) {
      R r;
      /*immutable*/ size_t n;

      static _ugh() { string r; foreach (N, _; F) r~="typeof(F["~N.stringof~"](r)) f"~N.stringof~";"; return r; }
      union U { mixin(_ugh()); }
      U u;

      this(R r, size_t n) {
         this.r = r; this.n = n;
         foreach (N, _; typeof(F)) if (N==n) u.tupleof[N] = F[N](r);
      }

      auto ref front() @property { foreach (N, _; typeof(F)) if (N==n) return u.tupleof[N].front; assert(0); }
      bool empty() @property     { foreach (N, _; typeof(F)) if (N==n) return u.tupleof[N].empty; assert(0); }
      void popFront()            { foreach (N, _; typeof(F)) if (N==n) u.tupleof[N].popFront(); }

   }

   import std.array;

   auto f(R)(R r, bool somecondition) {
      import std.algorithm, std.conv;
      return DynRange!(R,
            map!"a*a",
            r=>filter!"a%2"((map!(a=>to!string(a^^a).length)(r)))
         )(r, somecondition);
   }

   void main() {
      import std.stdio;

      auto r = [1,2,3,4,5].f(false);
      writeln(r);
      r = [1,2,3,4,5].f(true);
      writeln(r);
   }

[Optimizing DynRange is left as an exercise for the reader. ;) In practice,
 when used with just two chains, the gain would be minimal anyway. Adding
 a level of indirection for the range primitives would prevent inlining.]

artur

On Sat, Mar 29, 2014 at 01:37:42AM +0100, Artur Skawina wrote: [...]
> D is statically typed -- there is no way for one function to return
> different types that are selected by a runtime condition.
> The fact that the produced elements have the same type is irrelevant.
> 
> You can wrap the range in a common one. When the above approach isn't enough, there's always the next level:
> 
>    struct DynRange(R, F...) {
>       R r;
>       /*immutable*/ size_t n;
> 
>       static _ugh() { string r; foreach (N, _; F) r~="typeof(F["~N.stringof~"](r)) f"~N.stringof~";"; return r; }
>       union U { mixin(_ugh()); }
>       U u;

Heh, I thought of using a union as well. :P


[...]
> [Optimizing DynRange is left as an exercise for the reader. ;) In practice, when used with just two chains, the gain would be minimal anyway. Adding a level of indirection for the range primitives would prevent inlining.]
[...]

Yeah. :(  One idea I had was to use function pointers for .empty, .front, .popFront, but that also prevents inlining. But it seems inevitable that something like this has to be done if runtime polymorphism is needed.

Another (very ugly) approach might be to use compile-time branches in
the caller:

	auto polymorphicRange(size_t i, R...)(R ranges)
	{
		static if (i==0)
			return ranges[0];
		else static if (i==1)
			return ranges[1];
		else ... // etc
	}

	void processRange(R)(R range) { ... }

	void unfortunateConsumer(size_t i)
	{
		auto RangeA = ...;
		auto RangeB = ...;
		...

		if (i==0)
			processRange(polymorphicRange!0(RangeA, RangeB));
		else if (i==1)
			processRange(polymorphicRange!1(RangeA, RangeB));
		else
			...
	}

This way, you get the advantage of inlining in processRange, but then you have to suffer from the very ugly boilerplate and the template bloat. And it doesn't generalize well to multiple nested polymorphic ranges (unfortunateConsumer will basically have to enumerate all possible combinations and instantiate each of them separately). :-(

Some days you win, most days you lose...


T

-- 
WINDOWS = Will Install Needless Data On Whole System -- CompuMan

On 03/29/2014 01:37 AM, Artur Skawina wrote:
> You can wrap the range in a common one. When the above approach isn't
> enough, there's always the next level:

(Note that your code does not actually compile.)

On 03/29/14 16:31, Timon Gehr wrote:
> On 03/29/2014 01:37 AM, Artur Skawina wrote:
>> You can wrap the range in a common one. When the above approach isn't enough, there's always the next level:
> 
> (Note that your code does not actually compile.)

Of course it compiles -- with the compiler version I happen to use...

The compiler situation is one of the main reasons I gave up on D
about a year ago. Every release introduces a new dialect. This may
not be such a big problem for trivial toy programs, but for anything
else it means that the only practical approach is locking the toolchain
down and never looking forward.
Sometimes this means that the examples I post won't work -- I don't
have any newer D compiler to check with, sorry.

The reason I'm still around here is that while D has tons of problems, there is no better alternative available, for now.

I decided to revisit that DynRange implementation today, to see just how concise and readable it could be made, while still resulting in absolutely optimal codegen. The result was this:

   struct DynRange(R, F...) {
      size_t n;
      union { mixin(fmtStmts!(q{ typeof(F[$d](R.init)) r$d; }, F)); }

      this(R r, size_t n) {
         this.n = n;
         mixin(fmtSwitch!("n", q{ $d: r$d = F[$d](r); break; }, F));
      }

      mixin switchDispatch!("n", q{ $d: return r$d.$member $args; }, F);
   }

   // [1]

artur


[1] // The generic helpers used:

   template evalExpMap(string C, string F, A...) {
      enum evalExpMap = {
         import std.array, std.conv;
         string s, l, t;
         static if (is(typeof(A))) alias B = typeof(A);
                else               alias B = A;
         foreach (I, _; B) {
            auto r = replace(replace(F, "$s", A[I].stringof),
                                        "$d", to!string(I));
            l ~= (I?", ":"") ~ r;
            s ~=               r ~ ";\n";
            t ~=               r ~ " ";
         }
         return replace(replace(replace(C, "$...;", s), "$...,", l), "$...", t);
      }();
   }
   template fmtStmts(string FMT, A...) { alias fmtStmts = evalExpMap!("$...", FMT, A); }
   template fmtSwitch(string EXP, string FMT, A...) {
      alias fmtSwitch = evalExpMap!("switch ("~EXP~") { $... default: assert(0); }", "case "~FMT, A);
   }

   // fmtDispatch: A helper that keeps all the @property boilerplate in one place.
   mixin template switchDispatch(string EXPR, string CODE, T...) {
      template opDispatch(string M) {
         import std.array;
         enum C = replace(CODE, "$member", M);
         @property auto ref opDispatch()()
          if (is(typeof(function { mixin(fmtSwitch!(EXPR, replace(C, "$args", ""), T)); }))) {
            mixin(fmtSwitch!(EXPR, replace(C, "$args", ""), T));
         }
         @property auto ref opDispatch(A...)(A a)
          if (is(typeof(function { mixin(fmtSwitch!(EXPR, replace(C, "$args", "=a"), T)); }))) {
            mixin(fmtSwitch!(EXPR, replace(C, "$args", "=a"), T));
         }
         auto ref opDispatch(A...)(A a)
          if (is(typeof(function { mixin(fmtSwitch!(EXPR, replace(C, "$args", "(a)"), T)); }))) {
            mixin(fmtSwitch!(EXPR, replace(C, "$args", "(a)"), T));
         }
      }
   }

On 03/29/2014 06:19 PM, Artur Skawina wrote:
> Of course it compiles -- with the compiler version I happen to use...
>
> The compiler situation is one of the main reasons I gave up on D
> about a year ago. Every release introduces a new dialect. This may
> not be such a big problem for trivial toy programs, but for anything
> else it means that the only practical approach is locking the toolchain
> down and never looking forward.
> Sometimes this means that the examples I post won't work -- I don't
> have any newer D compiler to check with, sorry.

I'm stuck with 2.060 myself, but there's always http://dpaste.dzfl.pl/.

On 03/29/14 18:30, Timon Gehr wrote:
> 
> I'm stuck with 2.060 myself, but there's always http://dpaste.dzfl.pl/.

For the examples, I used a gdc that claims __VERSION__==2062L.

(for /real/ code I'm still using a 2.057 based one...)

artur

> On 03/28/2014 08:00 PM, H. S. Teoh wrote:
> >Today I ran into an interesting situation where I have a function f that needs to return ranges of different types (but identical element types):
> >
> >	auto f(A...)(A args) {
> >		...
> >		if (someCondition)
> >			return cartesianProduct(x, y)
> >				.joiner;
> >		else
> >			return cartesianProduct(x, y)
> >				.joiner
> >				.filter!someFilter;
> >	}
> >
> >This obviously can't compile, because the return types are not the same.  (Note that someCondition is only known at runtime.) But abstractly speaking, it *should* work, because the element type of the returned range is identical.
> >
> >So how would I implement something like this?
[...]

Well, eventually I settled on using inputRangeObject() from std.range. While not the most performant (f would have to return InputRangeObject interface, which adds indirection), it was simplest to use and didn't require excessively ugly code. If this part of the code turns out to be a bottleneck, I'll rethink this decision, but for now it works nicely. :)


T

-- 
The easy way is the wrong way, and the hard way is the stupid way. Pick one.