digitalmars.D - Recursive vs. iterative constraints

Andrei Alexandrescu (18/18) Apr 15 2016 So the constraint on chain() is:

Alex Parrill (8/27) Apr 15 2016 The former, definitely.

Andrei Alexandrescu (2/4) Apr 16 2016 staticMap, too. -- Andrei

Jonathan M Davis via Digitalmars-d (4/20) Apr 15 2016 The first one is way cleaner IMHO.

Daniel N (11/15) Apr 16 2016 Strong preference for iterative, one key improvement of D's CTFE

John Colvin (6/25) Apr 16 2016 Very strong preference for the first. The second is so much

Daniel N (16/20) Apr 16 2016 "iterative" just clicked in my brain, it is possible to use

Atila Neves (4/23) Apr 16 2016 Definitely prefer the 1st.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

So the constraint on chain() is:

Ranges.length > 0 &&
allSatisfy!(isInputRange, staticMap!(Unqual, Ranges)) &&
!is(CommonType!(staticMap!(ElementType, staticMap!(Unqual, Ranges))) == 
void)

Noice. Now, an alternative is to express it as a recursive constraint:

(Ranges.length == 1 && isInputRange!(Unqual!(Ranges[0])))
   ||
   (Ranges.length == 2 &&
     isInputRange!(Unqual!(Ranges[0])) &&
     isInputRange!(Unqual!(Ranges[1])) &&
     !is(CommonType!(ElementType!(Ranges[0]), ElementType!(Ranges[1])) 
== void))
   || is(typeof(chain(rs[0 .. $ / 2], chain(rs[$ / 2 .. $]))))

In the latter case there's no need for additional helpers but the 
constraint is a bit more bulky.

Pros? Cons? Preferences?


Andrei

Apr 15 2016

Alex Parrill <initrd.gz gmail.com> writes:

On Saturday, 16 April 2016 at 02:42:55 UTC, Andrei Alexandrescu 
wrote:
 So the constraint on chain() is:

 Ranges.length > 0 &&
 allSatisfy!(isInputRange, staticMap!(Unqual, Ranges)) &&
 !is(CommonType!(staticMap!(ElementType, staticMap!(Unqual, 
 Ranges))) == void)

 Noice. Now, an alternative is to express it as a recursive 
 constraint:

 (Ranges.length == 1 && isInputRange!(Unqual!(Ranges[0])))
   ||
   (Ranges.length == 2 &&
     isInputRange!(Unqual!(Ranges[0])) &&
     isInputRange!(Unqual!(Ranges[1])) &&
     !is(CommonType!(ElementType!(Ranges[0]), 
 ElementType!(Ranges[1])) == void))
   || is(typeof(chain(rs[0 .. $ / 2], chain(rs[$ / 2 .. $]))))

 In the latter case there's no need for additional helpers but 
 the constraint is a bit more bulky.

 Pros? Cons? Preferences?


 Andrei

The former, definitely.

The only helper function you're getting rid of that I see is 
allSatisfy, which describes the constraint very well. The 
recursive constraint obscures what the intended constraint is 
(that the passed types are input ranges with a common type) 
behind the recursion.

Apr 15 2016

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 4/15/16 10:58 PM, Alex Parrill wrote:>
 The only helper function you're getting rid of that I see is allSatisfy,
 which describes the constraint very well.

staticMap, too. -- Andrei

Apr 16 2016

Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:

On Friday, April 15, 2016 22:42:55 Andrei Alexandrescu via Digitalmars-d 
wrote:
 So the constraint on chain() is:

 Ranges.length > 0 &&
 allSatisfy!(isInputRange, staticMap!(Unqual, Ranges)) &&
 !is(CommonType!(staticMap!(ElementType, staticMap!(Unqual, Ranges))) ==
 void)

 Noice. Now, an alternative is to express it as a recursive constraint:

 (Ranges.length == 1 && isInputRange!(Unqual!(Ranges[0])))

    (Ranges.length == 2 &&
      isInputRange!(Unqual!(Ranges[0])) &&
      isInputRange!(Unqual!(Ranges[1])) &&
      !is(CommonType!(ElementType!(Ranges[0]), ElementType!(Ranges[1]))
 == void))

    || is(typeof(chain(rs[0 .. $ / 2], chain(rs[$ / 2 .. $]))))

 In the latter case there's no need for additional helpers but the
 constraint is a bit more bulky.

 Pros? Cons? Preferences?

The first one is way cleaner IMHO.

- Jonathan M Davis

Apr 15 2016

Daniel N <ufo orbiting.us> writes:

On Saturday, 16 April 2016 at 03:46:25 UTC, Jonathan M Davis 
wrote:
 On Friday, April 15, 2016 22:42:55 Andrei Alexandrescu via
 Pros? Cons? Preferences?

 The first one is way cleaner IMHO.

 - Jonathan M Davis

Strong preference for iterative, one key improvement of D's CTFE 
vs legacy C++ template meta programming is that you can avoid 
recursion in the normal case(only using it when it's a clear win, 
which I fail to see in this example).

Furthermore, I also fail to see what Unqual solves, 
'isInputRange' should correctly handle all qualifiers.

allSatisfy!(isInputRange, staticMap!(Unqual, Ranges))
=>
allSatisfy!(isInputRange, Ranges)

Apr 16 2016

John Colvin <john.loughran.colvin gmail.com> writes:

On Saturday, 16 April 2016 at 02:42:55 UTC, Andrei Alexandrescu 
wrote:
 So the constraint on chain() is:

 Ranges.length > 0 &&
 allSatisfy!(isInputRange, staticMap!(Unqual, Ranges)) &&
 !is(CommonType!(staticMap!(ElementType, staticMap!(Unqual, 
 Ranges))) == void)

 Noice. Now, an alternative is to express it as a recursive 
 constraint:

 (Ranges.length == 1 && isInputRange!(Unqual!(Ranges[0])))
   ||
   (Ranges.length == 2 &&
     isInputRange!(Unqual!(Ranges[0])) &&
     isInputRange!(Unqual!(Ranges[1])) &&
     !is(CommonType!(ElementType!(Ranges[0]), 
 ElementType!(Ranges[1])) == void))
   || is(typeof(chain(rs[0 .. $ / 2], chain(rs[$ / 2 .. $]))))

 In the latter case there's no need for additional helpers but 
 the constraint is a bit more bulky.

 Pros? Cons? Preferences?


 Andrei

Very strong preference for the first. The second is so much 
harder to read (not everyone is great at thinking recursively) 
and also could depend on the implementation of chain if the 
return type must be inferred from the body.

Apr 16 2016

Daniel N <ufo orbiting.us> writes:

On Saturday, 16 April 2016 at 09:27:28 UTC, John Colvin wrote:
 Very strong preference for the first. The second is so much 
 harder to read (not everyone is great at thinking recursively) 
 and also could depend on the implementation of chain if the 
 return type must be inferred from the body.

"iterative" just clicked in my brain, it is possible to use 
foreach, using assert will not actually assert, just cause the 
constraint to fail, so that another matching chain still may be 
chosen.

auto chain(Ranges...)(Ranges rs)
if(is(typeof({
   alias U = staticMap!(Unqual, Ranges);
   alias E = staticMap!(ElementType, U);
   static assert(!is(CommonType!E == void));
   foreach(Range; U)
     static assert(isInputRange!Range);
})))
{
   ...
}

Apr 16 2016

Atila Neves <atila.neves gmail.com> writes:

On Saturday, 16 April 2016 at 02:42:55 UTC, Andrei Alexandrescu 
wrote:
 So the constraint on chain() is:

 Ranges.length > 0 &&
 allSatisfy!(isInputRange, staticMap!(Unqual, Ranges)) &&
 !is(CommonType!(staticMap!(ElementType, staticMap!(Unqual, 
 Ranges))) == void)

 Noice. Now, an alternative is to express it as a recursive 
 constraint:

 (Ranges.length == 1 && isInputRange!(Unqual!(Ranges[0])))
   ||
   (Ranges.length == 2 &&
     isInputRange!(Unqual!(Ranges[0])) &&
     isInputRange!(Unqual!(Ranges[1])) &&
     !is(CommonType!(ElementType!(Ranges[0]), 
 ElementType!(Ranges[1])) == void))
   || is(typeof(chain(rs[0 .. $ / 2], chain(rs[$ / 2 .. $]))))

 In the latter case there's no need for additional helpers but 
 the constraint is a bit more bulky.

 Pros? Cons? Preferences?


 Andrei

Definitely prefer the 1st.

Atila

Apr 16 2016

D Programming

C/C++ Programming

Other

digitalmars.D - Recursive vs. iterative constraints