Algebraic Data Types in D?

[Timon Gehr via Digitalmars-d]

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.
>>>>
>>>> http://dlang.org/phobos/std_variant.html#.Algebraic
>>>>
>>>> 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
>