digitalmars.D - Algebraic Data Types in D?
- Remo (5/5) Jul 31 2014 http://tech.esper.com/2014/07/30/algebraic-data-types/
- w0rp (6/11) Jul 31 2014 There is a library solution for this in the standard library.
- Andrei Alexandrescu (3/14) Jul 31 2014 alias Foo = Algebraic!(This[]);
- Timon Gehr (12/30) Jul 31 2014 alias Foo = Algebraic!(int,Algebraic!(Foo[],double)[]);
- Andrei Alexandrescu (11/43) Jul 31 2014 Good point! That's why I'd submitted this at some point:
- bearophile (6/8) Aug 01 2014 A more general solution is to add a onGC() optional method that
- Timon Gehr (39/88) Aug 01 2014 It might also be possible that this is what is actually wanted:
- Andrei Alexandrescu (8/54) Aug 01 2014 Yah, there'd probably be a more precise name for it.
- Timon Gehr (12/65) Aug 01 2014 Actually yes, but I currently have a backlog of work to do, partly due
- Wyatt (6/11) Jul 31 2014 I think you're looking for std.variant?
- =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= (17/21) Jul 31 2014 I'm currently in the process of polishing one up to improve vibe.d's
- Justin Whear (15/21) Jul 31 2014 In addition to the suggestions of Algebraic or Variant elsewhere in this...
- bearophile (6/23) Jul 31 2014 See for a bare-bones built-in pattern matching, with an optional
- Remo (26/52) Jul 31 2014 Yes this is also possible to do in C++ too.
- Meta (28/47) Jul 31 2014 import std.stdio;
http://tech.esper.com/2014/07/30/algebraic-data-types/ D already has product type it is struct. But D lacks sum type also called tagged-union. Do you think it would be possible to add something like this to D2 ?
Jul 31 2014
On Thursday, 31 July 2014 at 11:42:21 UTC, Remo wrote:http://tech.esper.com/2014/07/30/algebraic-data-types/ D already has product type it is struct. But D lacks sum type also called tagged-union. Do you think it would be possible to add something like this to D2 ?There is a library solution for this in the standard library. It doesn't handle recursive types at the moment, like alias Foo = Algebraic!(Foo[]). Apart from that, it should be what you are looking for.
Jul 31 2014
On 7/31/14, 6:03 AM, w0rp wrote:On Thursday, 31 July 2014 at 11:42:21 UTC, Remo wrote:alias Foo = Algebraic!(This[]); Andreihttp://tech.esper.com/2014/07/30/algebraic-data-types/ D already has product type it is struct. But D lacks sum type also called tagged-union. Do you think it would be possible to add something like this to D2 ?There is a library solution for this in the standard library. It doesn't handle recursive types at the moment, like alias Foo = Algebraic!(Foo[]). Apart from that, it should be what you are looking for.
Jul 31 2014
On 07/31/2014 06:23 PM, Andrei Alexandrescu wrote:On 7/31/14, 6:03 AM, w0rp wrote:alias Foo = Algebraic!(int,Algebraic!(Foo[],double)[]); There is also this kind of approach: mixin ADT!q{ List(T): | Nil | Cons T List!T }; Of course, product types ("tuples") and sum types ("tagged unions") and recursive types are elementary enough to be proper language features in one way or another with all the syntactic convenience that yields for pattern matching.On Thursday, 31 July 2014 at 11:42:21 UTC, Remo wrote:alias Foo = Algebraic!(This[]); Andreihttp://tech.esper.com/2014/07/30/algebraic-data-types/ D already has product type it is struct. But D lacks sum type also called tagged-union. Do you think it would be possible to add something like this to D2 ?There is a library solution for this in the standard library. It doesn't handle recursive types at the moment, like alias Foo = Algebraic!(Foo[]). Apart from that, it should be what you are looking for.
Jul 31 2014
On 7/31/14, 5:35 PM, Timon Gehr wrote:On 07/31/2014 06:23 PM, Andrei Alexandrescu wrote:Good point! That's why I'd submitted this at some point: https://issues.dlang.org/show_bug.cgi?id=9608 It should be possible to achieve alpha replacement of This with the needed type at any level inside a composite type.On 7/31/14, 6:03 AM, w0rp wrote:alias Foo = Algebraic!(int,Algebraic!(Foo[],double)[]);On Thursday, 31 July 2014 at 11:42:21 UTC, Remo wrote:alias Foo = Algebraic!(This[]); Andreihttp://tech.esper.com/2014/07/30/algebraic-data-types/ D already has product type it is struct. But D lacks sum type also called tagged-union. Do you think it would be possible to add something like this to D2 ?There is a library solution for this in the standard library. It doesn't handle recursive types at the moment, like alias Foo = Algebraic!(Foo[]). Apart from that, it should be what you are looking for.There is also this kind of approach: mixin ADT!q{ List(T): | Nil | Cons T List!T };Interesting! Is there code available for that?Of course, product types ("tuples") and sum types ("tagged unions") and recursive types are elementary enough to be proper language features in one way or another with all the syntactic convenience that yields for pattern matching.Well one other way to look at it is that striving to do things in a library pushes introspection forward. I do agree tagged unions should be pushed into the language; they'd help the GC. Andrei
Jul 31 2014
Andrei Alexandrescu:I do agree tagged unions should be pushed into the language; they'd help the GC.A more general solution is to add a onGC() optional method that gets called by the GC on collections, and tells it what's inside the union. Bye, bearophile
Aug 01 2014
On 08/01/2014 03:26 AM, Andrei Alexandrescu wrote:On 7/31/14, 5:35 PM, Timon Gehr wrote:It might also be possible that this is what is actually wanted: alias Foo = Algebraic!(int,Algebraic!(This[],double)[]); (I.e. This refers to the inner type.) There is always this issue as well: alias ListInt=Algebraic!(Tuple!(),Tuple!(int,ListInt*)); How would you use the proposed enhancement to fix this? (BTW: Algebraic implements a plain sum type, so I again think the name is a little strange :o).)On 07/31/2014 06:23 PM, Andrei Alexandrescu wrote:Good point! That's why I'd submitted this at some point: https://issues.dlang.org/show_bug.cgi?id=9608 It should be possible to achieve alpha replacement of This with the needed type at any level inside a composite type. ...On 7/31/14, 6:03 AM, w0rp wrote:alias Foo = Algebraic!(int,Algebraic!(Foo[],double)[]);On Thursday, 31 July 2014 at 11:42:21 UTC, Remo wrote:alias Foo = Algebraic!(This[]); Andreihttp://tech.esper.com/2014/07/30/algebraic-data-types/ D already has product type it is struct. But D lacks sum type also called tagged-union. Do you think it would be possible to add something like this to D2 ?There is a library solution for this in the standard library. It doesn't handle recursive types at the moment, like alias Foo = Algebraic!(Foo[]). Apart from that, it should be what you are looking for.You can find an incomplete proof-of-concept implementation here: http://dpaste.dzfl.pl/77abae58a087 (The 'match' is not particularly great, opEquals is missing, etc.) It was quite hard to get past the compiler.There is also this kind of approach: mixin ADT!q{ List(T): | Nil | Cons T List!T };Interesting! Is there code available for that? ...Based on past experiences, I think we'd see some opposition if the language was to be extended in a way to allow those kinds of features to be implemented completely in the library such that they behave and look optimally. In any case, having a template Fix operator would sometimes be convenient: struct Foo1(T){ T* self; } alias Foo=Fix!Foo1; /+ instantiates to something like: struct Foo{ Foo* self; } +/ :o) the most natural implementation of Fix does not work for obvious reasons: alias Fix(alias F)=F!(Fix!F); Making this work is not completely out of reach though, I think. The best I can currently do to "save" 'Algebraic' is the following: http://dpaste.dzfl.pl/65afd3a7ce52Of course, product types ("tuples") and sum types ("tagged unions") and recursive types are elementary enough to be proper language features in one way or another with all the syntactic convenience that yields for pattern matching.Well one other way to look at it is that striving to do things in a library pushes introspection forward. ...I do agree tagged unions should be pushed into the language; they'd help the GC. ...The GC as well as the language semantics. E.g. how to lazily initialize a struct field of a type that has no .init value, such as a nested struct outside of its context, or something with disable this()? (Many structs are nested because of local template instantiation.) Furthermore, they are really convenient if done right.Andrei
Aug 01 2014
On 8/1/14, 7:18 AM, Timon Gehr wrote:It might also be possible that this is what is actually wanted: alias Foo = Algebraic!(int,Algebraic!(This[],double)[]); (I.e. This refers to the inner type.) There is always this issue as well: alias ListInt=Algebraic!(Tuple!(),Tuple!(int,ListInt*)); How would you use the proposed enhancement to fix this?I don't think there's an easy way.(BTW: Algebraic implements a plain sum type, so I again think the name is a little strange :o).)Yah, there'd probably be a more precise name for it.On a cursory inspection, looks good! The question there is whether you or anyone would be interested in taking that to a proposal.You can find an incomplete proof-of-concept implementation here: http://dpaste.dzfl.pl/77abae58a087 (The 'match' is not particularly great, opEquals is missing, etc.) It was quite hard to get past the compiler.There is also this kind of approach: mixin ADT!q{ List(T): | Nil | Cons T List!T };Interesting! Is there code available for that? ...That's interesting. Fix is worth making to work either as a built-in on a library artifact. AndreiWell one other way to look at it is that striving to do things in a library pushes introspection forward. ...Based on past experiences, I think we'd see some opposition if the language was to be extended in a way to allow those kinds of features to be implemented completely in the library such that they behave and look optimally. In any case, having a template Fix operator would sometimes be convenient: struct Foo1(T){ T* self; } alias Foo=Fix!Foo1; /+ instantiates to something like: struct Foo{ Foo* self; } +/ :o) the most natural implementation of Fix does not work for obvious reasons: alias Fix(alias F)=F!(Fix!F); Making this work is not completely out of reach though, I think. The best I can currently do to "save" 'Algebraic' is the following: http://dpaste.dzfl.pl/65afd3a7ce52
Aug 01 2014
On 08/01/2014 05:28 PM, Andrei Alexandrescu wrote:On 8/1/14, 7:18 AM, Timon Gehr wrote:It's hard to fix without Fix! :o)It might also be possible that this is what is actually wanted: alias Foo = Algebraic!(int,Algebraic!(This[],double)[]); (I.e. This refers to the inner type.) There is always this issue as well: alias ListInt=Algebraic!(Tuple!(),Tuple!(int,ListInt*)); How would you use the proposed enhancement to fix this?I don't think there's an easy way. ...Actually yes, but I currently have a backlog of work to do, partly due to having been involved in a strange debate about the meaning of words.On a cursory inspection, looks good! The question there is whether youYou can find an incomplete proof-of-concept implementation here: http://dpaste.dzfl.pl/77abae58a087 (The 'match' is not particularly great, opEquals is missing, etc.) It was quite hard to get past the compiler.There is also this kind of approach: mixin ADT!q{ List(T): | Nil | Cons T List!T };Interesting! Is there code available for that? ...or anyone would be interested in taking that to a proposal. ...I wouldn't be opposed to that option. Any volunteers willing to take up the effort?Agreed. The fact that the above 'iso-recursive' approach works now may serve as an implication that most relevant assumptions that templates may make about their parameters that are broken by a fix operator weren't valid before either. I have a very strong suspicion that Fix cannot be implemented without modifying the language a little bit, but I'd be happy to be proven wrong.That's interesting. Fix is worth making to work either as a built-in on a library artifact. ...Well one other way to look at it is that striving to do things in a library pushes introspection forward. ...... In any case, having a template Fix operator would sometimes be convenient: ... the most natural implementation of Fix does not work for obvious reasons: alias Fix(alias F)=F!(Fix!F); Making this work is not completely out of reach though, I think. The best I can currently do to "save" 'Algebraic' is the following: http://dpaste.dzfl.pl/65afd3a7ce52Andrei
Aug 01 2014
On Thursday, 31 July 2014 at 11:42:21 UTC, Remo wrote:http://tech.esper.com/2014/07/30/algebraic-data-types/ D already has product type it is struct. But D lacks sum type also called tagged-union. Do you think it would be possible to add something like this to D2 ?I think you're looking for std.variant? http://dlang.org/phobos/std_variant.html (My understanding is it's undergoing some heavy work, so do be aware of that.) -Wyatt
Jul 31 2014
Am 31.07.2014 13:42, schrieb Remo:http://tech.esper.com/2014/07/30/algebraic-data-types/ D already has product type it is struct. But D lacks sum type also called tagged-union. Do you think it would be possible to add something like this to D2 ?I'm currently in the process of polishing one up to improve vibe.d's Json/Bson type implementations. It's definitely possible to do (I've been using one for years), but has its caveats when there are dependency cycles in the code. Just to make clear what the difference is: - "Variant": open set of types, using TypeInfo for identification - "Algebraic": closed set of types, using TypeInfo for identification - Tagged union: closed set of types with a numeric ID for each type The latter has a few advantages in some situations - Doesn't require type info - Can use "switch" instead of iterating over all possible types or storing a pointer to helper functions for dealing with the type - Allows to use "final switch" to guarantee handling all cases - Provides a handy type value that can be used and stored in user code (vs. passing and storing TypeInfo instances) - Could be made to store the same type with different IDs
Jul 31 2014
On Thu, 31 Jul 2014 11:42:20 +0000, Remo wrote:http://tech.esper.com/2014/07/30/algebraic-data-types/ D already has product type it is struct. But D lacks sum type also called tagged-union. Do you think it would be possible to add something like this to D2 ?In addition to the suggestions of Algebraic or Variant elsewhere in this thread, it's trivial to implement your own concrete tagged unions: struct MyTaggedUnion { enum Type { Int, Float, String } Type tag; union { int int_; float float_; string string_; } } You can also hide the union members with private and only allow access via property getters that check the tag.
Jul 31 2014
Justin Whear:In addition to the suggestions of Algebraic or Variant elsewhere in this thread, it's trivial to implement your own concrete tagged unions: struct MyTaggedUnion { enum Type { Int, Float, String } Type tag; union { int int_; float float_; string string_; } } You can also hide the union members with private and only allow access via property getters that check the tag.See for a bare-bones built-in pattern matching, with an optional "opMatch" struct method that gets called by the improved switch: https://d.puremagic.com/issues/show_bug.cgi?id=596 Bye, bearophile
Jul 31 2014
On Thursday, 31 July 2014 at 15:03:09 UTC, Justin Whear wrote:On Thu, 31 Jul 2014 11:42:20 +0000, Remo wrote:Thanks for all the answers !http://tech.esper.com/2014/07/30/algebraic-data-types/ D already has product type it is struct. But D lacks sum type also called tagged-union. Do you think it would be possible to add something like this to D2 ?In addition to the suggestions of Algebraic or Variant elsewhere in this thread, it's trivial to implement your own concrete tagged unions: struct MyTaggedUnion { enum Type { Int, Float, String } Type tag; union { int int_; float float_; string string_; } } You can also hide the union members with private and only allow access via property getters that check the tag.it's trivial to implement your own concrete tagged unionsYes this is also possible to do in C++ too. But I do not think that this is trivial at least not for 10 or 20 values. Enum and Union need always to be in sync and compiler will not output error if the programmer/user will make any mistake. How to translate this useless Rust code to D, with as least D code as possible ? How be sure that everything will still work as expected if programmer will add White color ? enum Color { Red, Green, Blue, Rgb(int,int,int) } fn main() { let r = Rgb(64,128,255); match r { Red => println!("Red"), Green => println!("Green"), Blue => println!("Blue"), Rgb(r,g,b) => println!("Rgb({},{},{})",r,g,b), } }
Jul 31 2014
On Thursday, 31 July 2014 at 20:28:55 UTC, Remo wrote:How to translate this useless Rust code to D, with as least D code as possible ? How be sure that everything will still work as expected if programmer will add White color ? enum Color { Red, Green, Blue, Rgb(int,int,int) } fn main() { let r = Rgb(64,128,255); match r { Red => println!("Red"), Green => println!("Green"), Blue => println!("Blue"), Rgb(r,g,b) => println!("Rgb({},{},{})",r,g,b), } }import std.stdio; import std.variant; struct Red {} struct Green{} struct Blue {} struct RGB { int r; int g; int b; } alias Color = Algebraic!(Red, Green, Blue, RGB); void main() { auto r = Color(RGB(64, 128, 255)); r.visit!( (Red r) => writeln("Red"), (Green g) => writeln("Green"), (Blue b) => writeln("Blue"), (RGB rgb) => writefln("RGB(%s, %s, %s)", rgb.r, rgb.g, rgb.b), ); } D's Algebraic needs some work, but it's okay for basic usage. The most annoying thing is that you can't instantiate an RGB and expect the compiler to magically know that it's a subtype of Color. Maybe there's a way to work around that, but I can't think of one right off.
Jul 31 2014