www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Set Intersection and Set Difference on Compile-Time lists

reply David Sanders <insideoutclub gmail.com> writes:
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:

import std.variant;

alias Zero = void;

struct One{}

struct Difference(T, U) {
     static if (is(U == Zero)) alias type = T;
     else static if(is(T == U)) alias type = Zero;
     else static if (is(T _ == VariantN!V, V...)) {
         static if(is(U __ == VariantN!W, W...)) {
             /* if W[1..$] is a subset of V[1..$] alias type = 
Algebraic!(setDifference(V[1..$], W[1..$])) */
         } else {
             /* if U is subset of V[1..$] alias type = 
Algebraic!(setDifference(V[1..$], U)) */
         }
     } else static if(is(U _ == VariantN!V, V...)) {
         /* if V[1..$] is a single element set containing T alias 
type = Zero */
     }

     unittest
     {
         static assert (is(Zero == Difference!(Zero, Zero).type));
         static assert (is(One == Difference!(One, Zero).type));
         static assert (!is(Difference!(Zero, One).type));
         static assert (is(Algebraic!(One) == 
Difference!(Algebraic!(One, One), Algebraic!(One)).type));
     }
}

void main() {
     alias type = Difference!(One, Zero).type;
}
Apr 25 2017
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
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
Apr 25 2017
parent reply David Sanders <insideoutclub gmail.com> writes:
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
Apr 25 2017
parent "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
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
Apr 25 2017