I'm trying to do algebra with types ala http://chris-taylor.github.io/blog/2013/02/10/the-algebra-of-algebraic-data-types/

Below you will find my attempts at "adding" types in D. I've outlined the parts I'm having trouble with using block comments.

1) How do I figure out whether a type is an instantiation of std.variant.Algebraic?
2) If the type is Algebraic, how do I capture its AllowedTypes?

Thanks,
Dave

import std.variant;

alias Zero = void;

struct One{};

struct Sum(T, U) {
    static if (is(T == Zero)) {
        static if (is(U == Zero)) {
            alias type = Zero;
        }
        else {
            alias type = U;
        }
    } else static if (is(U == Zero)) {
        alias type = T;
    } else static if (/* T is Algebraic */) {
        static if (/* U is Algebraic */) {
            alias type = Algebraic!/* Concatenate T.AllowedTypes with U.AllowedTypes */
        } else {
            alias type = Algebraic!/* Concatenate T.AllowedTypes with U */
        }
    } else static if (/* U is Algebraic */) {
        alias type = Alegebraic!/* Concatenate T with U.AllowedTypes */
    } else {
        alias type = Algebraic!(T, U);
    }	
}

void main() {
    static assert (is(Zero == Sum!(Zero, Zero).type));
    static assert (is(One == Sum!(Zero, One).type));
    static assert (is(One == Sum!(One, Zero).type));
    static assert (is(Algebraic!(One, One) == Sum!(One, One).type));
    static assert (is(Algebraic!(One, One, One) == Sum!(Sum!(One, One).type, One).type));
}

On Fri, Apr 21, 2017 at 04:16:30PM +0000, David Sanders via Digitalmars-d-learn wrote:
> I'm trying to do algebra with types ala http://chris-taylor.github.io/blog/2013/02/10/the-algebra-of-algebraic-data-types/
> 
> Below you will find my attempts at "adding" types in D. I've outlined the parts I'm having trouble with using block comments.
> 
> 1) How do I figure out whether a type is an instantiation of
> std.variant.Algebraic?
> 2) If the type is Algebraic, how do I capture its AllowedTypes?
[...]

static if (is(T : Algebraic!(U...), U))
{
	// U now refers to the argument to Algbraic.
}


--T

On Friday, 21 April 2017 at 16:31:37 UTC, H. S. Teoh wrote:
> On Fri, Apr 21, 2017 at 04:16:30PM +0000, David Sanders via Digitalmars-d-learn wrote:
>> I'm trying to do algebra with types ala http://chris-taylor.github.io/blog/2013/02/10/the-algebra-of-algebraic-data-types/
>> 
>> Below you will find my attempts at "adding" types in D. I've outlined the parts I'm having trouble with using block comments.
>> 
>> 1) How do I figure out whether a type is an instantiation of
>> std.variant.Algebraic?
>> 2) If the type is Algebraic, how do I capture its AllowedTypes?
> [...]
>
> static if (is(T : Algebraic!(U...), U))
> {
> 	// U now refers to the argument to Algbraic.
> }
>
>
> --T

There's also a private `isAlgebraic` template[1]. Is there any reason why we couldn't just make this public?

1. https://github.com/dlang/phobos/blob/master/std/variant.d#L2236

On Friday, 21 April 2017 at 17:33:22 UTC, Meta wrote:
> On Friday, 21 April 2017 at 16:31:37 UTC, H. S. Teoh wrote:
>> On Fri, Apr 21, 2017 at 04:16:30PM +0000, David Sanders via Digitalmars-d-learn wrote:
>>> I'm trying to do algebra with types ala http://chris-taylor.github.io/blog/2013/02/10/the-algebra-of-algebraic-data-types/
>>> 
>>> Below you will find my attempts at "adding" types in D. I've outlined the parts I'm having trouble with using block comments.
>>> 
>>> 1) How do I figure out whether a type is an instantiation of
>>> std.variant.Algebraic?
>>> 2) If the type is Algebraic, how do I capture its AllowedTypes?
>> [...]
>>
>> static if (is(T : Algebraic!(U...), U))
>> {
>> 	// U now refers to the argument to Algbraic.
>> }
>>
>>
>> --T
>
> There's also a private `isAlgebraic` template[1]. Is there any reason why we couldn't just make this public?
>
> 1. https://github.com/dlang/phobos/blob/master/std/variant.d#L2236

Thank-you for your input. With your help, I was able to figure out number whether a type is an instantiation of std.variant.Algebraic.

Now, I need help on concatenating Template Sequence Parameters. See the block comments below.

Thanks,
Dave

import std.stdio;
import std.variant;

alias Zero = void;

struct One{};

struct Sum(T, U) {
	static if (is(T == Zero)) {
		static if (is(U == Zero)) {
			alias type = Zero;
		}
		else {
			alias type = U;
		}
	} else static if (is(U == Zero)) {
		alias type = T;
	} else static if (is(T _ == VariantN!V, V...)) {
		static if(is(U _ == VariantN!W, W...)) {
			alias type = Algebraic!/* Concatenate V[1..$] with U[1..$] */
		} else {
			alias type = Algebraic!/* Concatenate V[1..$] with U */
		}
	} else static if(is(U _ == VariantN!V, V...)) {
		alias type = Algebraic!/* Concatenate T with V[1..$] */
	} else {
		alias type = Algebraic!(T, U);
	}	
}

void main() {
	static assert (is(Zero == Sum!(Zero, Zero).type));
	static assert (is(One == Sum!(Zero, One).type));
	static assert (is(One == Sum!(One, Zero).type));
	static assert (is(Algebraic!(One, One) == Sum!(One, One).type));
	static assert (is(Algebraic!(One, One, One) == Sum!(Sum!(One, One).type, One).type));
}

On Fri, Apr 21, 2017 at 06:54:38PM +0000, David Sanders via Digitalmars-d-learn wrote: [...]
> Now, I need help on concatenating Template Sequence Parameters. See the block comments below.
[...]
> 	} else static if (is(T _ == VariantN!V, V...)) {
> 		static if(is(U _ == VariantN!W, W...)) {
> 			alias type = Algebraic!/* Concatenate V[1..$] with U[1..$] */

Easy:

	alias type = Algebraic!(V[1..$], U[1..$]);

Template argument lists automatically expand, so this should do exactly what you want.


T

-- 
An elephant: A mouse built to government specifications. -- Robert Heinlein

On Friday, 21 April 2017 at 18:54:38 UTC, David Sanders wrote:
> Thank-you for your input. With your help, I was able to figure out number whether a type is an instantiation of std.variant.Algebraic.
>
> Now, I need help on concatenating Template Sequence Parameters. See the block comments below.
>
> Thanks,
> Dave
>
> import std.stdio;
> import std.variant;
>
> alias Zero = void;
>
> struct One{};
>
> struct Sum(T, U) {
> 	static if (is(T == Zero)) {
> 		static if (is(U == Zero)) {
> 			alias type = Zero;
> 		}
> 		else {
> 			alias type = U;
> 		}
> 	} else static if (is(U == Zero)) {
> 		alias type = T;
> 	} else static if (is(T _ == VariantN!V, V...)) {
> 		static if(is(U _ == VariantN!W, W...)) {
> 			alias type = Algebraic!/* Concatenate V[1..$] with U[1..$] */
> 		} else {
> 			alias type = Algebraic!/* Concatenate V[1..$] with U */
> 		}
> 	} else static if(is(U _ == VariantN!V, V...)) {
> 		alias type = Algebraic!/* Concatenate T with V[1..$] */
> 	} else {
> 		alias type = Algebraic!(T, U);
> 	}	
> }
>
> void main() {
> 	static assert (is(Zero == Sum!(Zero, Zero).type));
> 	static assert (is(One == Sum!(Zero, One).type));
> 	static assert (is(One == Sum!(One, Zero).type));
> 	static assert (is(Algebraic!(One, One) == Sum!(One, One).type));
> 	static assert (is(Algebraic!(One, One, One) == Sum!(Sum!(One, One).type, One).type));
> }

As an aside, there's a less convoluted way to do type-level arithmetic which is IMO also more concise and looks nicer. You don't have to mess around with Algebraic at all:

struct Zero;

struct Succ(N);

alias One = Succ!Zero;

alias Pred(N: Zero)        = Zero;
alias Pred(N: Succ!Np, Np) = Np;

alias Add(N1: Zero, N2: Zero) = Zero;
alias Add(N1,       N2: Zero) = N1;
alias Add(N1: Zero, N2)       = N2;
alias Add(N1,       N2)       = Add!(Succ!N1, Pred!N2);

void main()
{
    static assert(is(Pred!One == Zero));
    static assert(is(Succ!One == Succ!(Succ!Zero)));

    static assert(is(Add!(Zero, Zero) == Zero));
    static assert(is(Add!(Zero, One) == One));
    static assert(is(Add!(One, Zero) == One));
    static assert(is(Add!(One, One) == Succ!(Succ!(Zero))));

    alias Two = Succ!One;
    static assert(is(Add!(One, One) == Two));
    static assert(is(Add!(One, Two) == Succ!(Succ!(Succ!Zero))));

    static assert(is(Sub!(Zero, Zero) == Zero));
    static assert(is(Sub!(One, Zero) == One));
    static assert(is(Sub!(Zero, One) == Zero));
    static assert(is(Sub!(Two, One) == One));
    static assert(is(Sub!(One, Two) == Zero));
}

Implementing Mul, Div and the integer set is an exercise left to the reader.

On Friday, 21 April 2017 at 20:49:27 UTC, Meta wrote:
> On Friday, 21 April 2017 at 18:54:38 UTC, David Sanders wrote:
>> [...]
>
> As an aside, there's a less convoluted way to do type-level arithmetic which is IMO also more concise and looks nicer. You don't have to mess around with Algebraic at all:
>
> struct Zero;
>
> struct Succ(N);
>
> alias One = Succ!Zero;
>
> alias Pred(N: Zero)        = Zero;
> alias Pred(N: Succ!Np, Np) = Np;
>
> alias Add(N1: Zero, N2: Zero) = Zero;
> alias Add(N1,       N2: Zero) = N1;
> alias Add(N1: Zero, N2)       = N2;
> alias Add(N1,       N2)       = Add!(Succ!N1, Pred!N2);
>
> void main()
> {
>     static assert(is(Pred!One == Zero));
>     static assert(is(Succ!One == Succ!(Succ!Zero)));
>
>     static assert(is(Add!(Zero, Zero) == Zero));
>     static assert(is(Add!(Zero, One) == One));
>     static assert(is(Add!(One, Zero) == One));
>     static assert(is(Add!(One, One) == Succ!(Succ!(Zero))));
>
>     alias Two = Succ!One;
>     static assert(is(Add!(One, One) == Two));
>     static assert(is(Add!(One, Two) == Succ!(Succ!(Succ!Zero))));
>
>     static assert(is(Sub!(Zero, Zero) == Zero));
>     static assert(is(Sub!(One, Zero) == One));
>     static assert(is(Sub!(Zero, One) == Zero));
>     static assert(is(Sub!(Two, One) == One));
>     static assert(is(Sub!(One, Two) == Zero));
> }
>
> Implementing Mul, Div and the integer set is an exercise left to the reader.

What you've implemented is similar to the Church encoding for natural numbers. I'm not trying to encode natural numbers.

I'm trying to investigate the algebra of "adding", "multiplying", and "raising to a power" various data types. Adding the int type with the char type corresponds to Algebraic!(int, char). Multiplying the int type by the char type corresponds to Tuple!(int, char). Raising the int type to the char type corresponds to a function that accepts a char and returns an int. See the blog post in my original forum post for examples.

Thanks,
Dave