digitalmars.D.learn - Algebra With Types
- David Sanders (46/46) Apr 21 2017 I'm trying to do algebra with types ala
- H. S. Teoh via Digitalmars-d-learn (7/15) Apr 21 2017 [...]
- Meta (4/22) Apr 21 2017 There's also a private `isAlgebraic` template[1]. Is there any
- David Sanders (42/69) Apr 21 2017 Thank-you for your input. With your help, I was able to figure
- H. S. Teoh via Digitalmars-d-learn (10/15) Apr 21 2017 [...]
- Meta (32/74) Apr 21 2017 As an aside, there's a less convoluted way to do type-level
- David Sanders (12/46) Apr 24 2017 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 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: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 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: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 2017
"H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> 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 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.
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 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: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 2017