## digitalmars.D.learn - Algebra With Types

```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 2017
```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 2017
```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

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. 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 2017
```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

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. 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.

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 2017
```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

[...]
} 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 2017
```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.

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;

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

alias Two = Succ!One;

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
```
Apr 21 2017
```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;

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

alias Two = Succ!One;
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

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 2017