Challenge: Motivating examples for ...

[Steven Schveighoffer]

On 4/24/20 5:26 PM, Walter Bright wrote:
> On 4/22/2020 5:04 AM, Manu wrote:
>> [...]
> 
> The examples in the DIP are, frankly, too trivial to make a case for the 
> ... feature.
> 
> So here's the challenge to everyone: a small (5?) collection of 
> non-trivial motivating examples that show how it is done in D today, and 
> how it is done with ...., and how much better the ... is.

I have a couple: std.meta.NoDuplicates, and std.meta.Filter

template NewFilter(alias pred, T...)
{
     import std.meta : AliasSeq;
     static if(T.length == 1)
     {
         static if(pred!T)
             alias NewFilter = AliasSeq!(T);
         else
             alias NewFilter = AliasSeq!();
     }
     else
     {
         alias NewFilter = NewFilter!(pred, T)...;
     }
}

Original implementation here: 
https://github.com/dlang/phobos/blob/9844c34196c6f34743bfb4878d78cba804a57bf9/std/meta.d#L878-L898

Note that I've cut down the template instantiations from N *lg(N) 
instantiations of Filter to N instantiations of NewFilter, and only one 
level of recursion. Not only that, but...

If you have:

Filter!(Pred, SomeLongTuple);
NewFilter!(Pred, SomeLongTuple);

then

Filter!(Pred, SomeLongTuple[1 .. $]);

is going to produce a large amount of different instantiations (because 
of the divide and conquer recursion). Mostly only the leaves will be reused.

But

NewFilter!(PRed, SomeLongTuple[1 .. $]);

will generate ONE more instantiation, because all the rest will have 
been done from the first time.

Note that I have tested this in the proposed branch, with a few 
workarounds for syntax (Manu is working on this). And it passes the same 
unittests for Filter.

Now, for NoDuplicates, I have a personal interest in seeing this one be 
fixed:

template staticIota(size_t N)
{
     import std.meta : AliasSeq;
     string buildIota()
     {
         import std.range : iota;
         import std.format : format;
         return format("alias staticIota = AliasSeq!(%(%d,%));", iota(N));
     }
     mixin(buildIota());
}

template NewNoDuplicates(T...)
{
     import std.meta : AliasSeq;
     template getAlias(size_t idx) {
         alias list = T[0 .. idx];
         alias item = T[idx];
         import std.algorithm: canFind;
         static if([__traits(isSame, list, item)...].canFind(true))
             alias getAlias = AliasSeq!();
         else
             alias getAlias = AliasSeq!(T[idx]);
     }
     alias idxList = staticIota!(T.length)[1 .. $];
     alias NewNoDuplicates = AliasSeq!(T[0], getAlias!(idxList)...);
}

Original implementation here:
https://github.com/dlang/phobos/blob/9844c34196c6f34743bfb4878d78cba804a57bf9/std/meta.d#L405-L505

(yes, that's 100 lines, but includes docs and unittests)

Comparison of instantiations is laughable. I'm instantiating one 
template per element, plus the original NewNoDuplicates, vs. whatever 
happens in std.meta (there are several helper templates).

I believe the complexity of the original filter is N * N * lg(N), where 
as mine is N * N. If we had first-class type manipulation in CTFE, then 
we could get it down to N lg(N) by sorting the list. Also, I can 
probably avoid canFind and whatever it imports if I wanted to just 
search with a simple loop function for any true values in a local CTFE 
function.

I also tested this in the new branch, and it works, but again there are 
some bugs in the implementation Manu is working on, so the compilable 
version doesn't look as pretty.

Note, I think staticIota is going to be super-important if we get this 
... (or whatever) change in, because you can do a lot of things now with 
a tuple of indexes. The above is crude, and probably can be improved, 
but note how we don't need all the vagaries of iota, because we can just 
use ... expressions to make whatever sequence we need out of 0 .. N.

That's why I think something like AliasSeq!(0 .. N) handled by the 
compiler would be tremendously useful.

-Steve