Set Intersection and Set Difference on Compile-Time lists

[David Sanders via Digitalmars-d-learn]

On Tuesday, 25 April 2017 at 17:18:25 UTC, H. S. Teoh wrote:
> On Tue, Apr 25, 2017 at 05:08:36PM +0000, David Sanders via 
> Digitalmars-d-learn wrote:
>> I have two compile-time lists of types. How do I find their 
>> set intersection (to determine if one is a subset of the 
>> other) and their set difference? See the block comments below:
>
> What's your definition of set intersection / set difference? Is 
> order
> important?  For example, is (float, int) a subset of (int, int, 
> float),
> or do you only consider (int, float) to be a subset of (int, 
> int,
> float)?  Also, is (int, int, float) the same thing as (int, 
> float) or
> are duplicates in the list considered to be distinct set 
> members?
>
> If order is not important, can the lists be assumed to be 
> sorted?
>
> If order is not important and the lists are not sorted, you may 
> run into trouble with this kind of code, because you'd need to 
> implement O(n^2) algorithms for computing subsets / set 
> differences, and given the way templates are currently 
> implemented, this may quickly exhaust available memory in the 
> compiler.
>
> Given what you're trying to achieve, you *may* have better luck 
> implementing your type arithmetic using string manipulations, 
> and then a mixin at the end to turn it back into a type list.
>
>
> --T

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?

Thanks,
Dave