www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Algebra With Types

reply David Sanders <insideoutclub gmail.com> writes:
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));
}
Apr 21
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
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
Apr 21
parent reply Meta <jared771 gmail.com> writes:
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
Apr 21
parent reply David Sanders <insideoutclub gmail.com> writes:
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)); }
Apr 21
next sibling parent "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
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
Apr 21
prev sibling parent reply Meta <jared771 gmail.com> writes:
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.
Apr 21
parent David Sanders <insideoutclub gmail.com> writes:
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
Apr 24