www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Algebraic Data Types in D?

reply "Remo" <remo4d gmail.com> writes:
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
next sibling parent reply "w0rp" <devw0rp gmail.com> writes:
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
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/31/14, 6:03 AM, w0rp wrote:
 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.
alias Foo = Algebraic!(This[]); Andrei
Jul 31 2014
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 07/31/2014 06:23 PM, Andrei Alexandrescu wrote:
 On 7/31/14, 6:03 AM, w0rp wrote:
 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.
alias Foo = Algebraic!(This[]); Andrei
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.
Jul 31 2014
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/31/14, 5:35 PM, Timon Gehr wrote:
 On 07/31/2014 06:23 PM, Andrei Alexandrescu wrote:
 On 7/31/14, 6:03 AM, w0rp wrote:
 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.
alias Foo = Algebraic!(This[]); Andrei
alias Foo = Algebraic!(int,Algebraic!(Foo[],double)[]);
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.
 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
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 08/01/2014 03:26 AM, Andrei Alexandrescu wrote:
 On 7/31/14, 5:35 PM, Timon Gehr wrote:
 On 07/31/2014 06:23 PM, Andrei Alexandrescu wrote:
 On 7/31/14, 6:03 AM, w0rp wrote:
 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.
alias Foo = Algebraic!(This[]); Andrei
alias Foo = Algebraic!(int,Algebraic!(Foo[],double)[]);
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. ...
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).)
 There is also this kind of approach:

 mixin ADT!q{
   List(T):
   | Nil
   | Cons T List!T
 };
Interesting! Is there code available for that? ...
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.
 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. ...
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
 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
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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.
 There is also this kind of approach:

 mixin ADT!q{
   List(T):
   | Nil
   | Cons T List!T
 };
Interesting! Is there code available for that? ...
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.
On a cursory inspection, looks good! The question there is whether you or anyone would be interested in taking that to a proposal.
 Well 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
That's interesting. Fix is worth making to work either as a built-in on a library artifact. Andrei
Aug 01 2014
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 08/01/2014 05:28 PM, Andrei Alexandrescu wrote:
 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. ...
It's hard to fix without Fix! :o)
 There is also this kind of approach:

 mixin ADT!q{
   List(T):
   | Nil
   | Cons T List!T
 };
Interesting! Is there code available for that? ...
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.
On a cursory inspection, looks good! The question there is whether you
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.
 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?
 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/65afd3a7ce52
That's interesting. Fix is worth making to work either as a built-in on a library artifact. ...
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.
 Andrei
Aug 01 2014
prev sibling next sibling parent "Wyatt" <wyatt.epp gmail.com> writes:
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
prev sibling next sibling parent =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig rejectedsoftware.com> writes:
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
prev sibling parent reply Justin Whear <justin economicmodeling.com> writes:
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
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
prev sibling parent reply "Remo" <remo4d gmail.com> writes:
On Thursday, 31 July 2014 at 15:03:09 UTC, Justin Whear wrote:
 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.
Thanks for all the answers !
 it's trivial to implement your own concrete tagged unions
Yes 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
parent "Meta" <jared771 gmail.com> writes:
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