Set Intersection and Set Difference on Compile-Time lists

[H. S. Teoh via Digitalmars-d-learn]

On Tue, Apr 25, 2017 at 05:43:34PM +0000, David Sanders via Digitalmars-d-learn wrote:
[...]
> Order is not important. (float, int) is a subset of (int, int, float).
> (int, int, float) is not the same thing as (int, float). Duplicates in
> the list are considered to be distinct set members.
> 
> The lists are not assumed to be sorted, but the first step could be to
> sort the lists. This would lead to the question of how do I sort
> compile-time lists of types?
[...]

You can probably save yourself a lot of headache by taking up my
suggestion to implement operations on types as strings, and then using a
mixin to turn them back into types afterwards. You can use .stringof to
get the string representation of each item in the list, which can then
be sorted in CTFE using std.algorithm, and you can even use
std.algorithm to do set operations on the list to save yourself the
trouble of reimplement those algorithms.

Here's a working proof of concept:

--------
alias List(T...) = T;

// Convert a type list into an array of strings (type names).
template ToString(T...)
{
    static if (T.length == 0)
        enum ToString = [];
    else
        enum ToString = [T[0].stringof] ~ ToString!(T[1 .. $]);
}

unittest
{
    import std.algorithm.comparison : equal;
    import std.algorithm.sorting : sort;

    static assert(ToString!(int, int, float) == ["int", "int", "float"]);
    static assert(ToString!(int, double, float).sort()
        .equal(["double", "float", "int"]));
}

// Convert an array of strings back to a type list.
template ToTypes(string[] typenames)
{
    import std.array : array;
    import std.algorithm.iteration : joiner;

    mixin("alias ToTypes = List!(" ~ typenames.joiner(",").array ~ ");");
}

unittest
{
    pragma(msg, ToTypes!(["int", "double", "float"]));
    static assert(is(ToTypes!(["int", "double", "float"]) ==
        List!(int, double, float)));
}

// Computes the intersection of two type lists.
template IntersectionOf(A...)
{
    template With(B...)
    {
        // We need .array because Phobos likes packaging things up
        // inside wrappers, but ToTypes only understands built-in
        // arrays.
        import std.array : array;
        import std.algorithm.sorting : sort;
        import std.algorithm.setops : setIntersection;

        // Turn the lists into string arrays, use CTFE to compute set
        // operations, then turn it back to a type list.
        alias With = ToTypes!(
            setIntersection(ToString!A.sort(),
                            ToString!B.sort())
            .array);
    }
}

unittest
{
    // Here's how to use all of this to do what you want.
    static assert(is(
        IntersectionOf!(int, int, float).With!(float, byte, int) ==
        List!(float, int)));
}
--------

Implementing other set operations should be essentially the same thing
as the above, just substitute setIntersection with setDifference,
nWayUnion, etc..


T

-- 
They pretend to pay us, and we pretend to work. -- Russian saying