## digitalmars.D.learn - Algebra With Types

- David Sanders (46/46) Apr 21 I'm trying to do algebra with types ala
- H. S. Teoh via Digitalmars-d-learn (7/15) Apr 21 [...]
- Meta (4/22) Apr 21 There's also a private `isAlgebraic` template[1]. Is there any
- David Sanders (42/69) Apr 21 Thank-you for your input. With your help, I was able to figure
- H. S. Teoh via Digitalmars-d-learn (10/15) Apr 21 [...]
- Meta (32/74) Apr 21 As an aside, there's a less convoluted way to do type-level
- David Sanders (12/46) Apr 24 What you've implemented is similar to the Church encoding for

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

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

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: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#L2236I'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

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: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 04:16:30PM +0000, David Sanders via Digitalmars-d-learn wrote: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#L2236I'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

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

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

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: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[...]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 24