Search
Recursive discriminated unions [Phobos2]
Feb 15, 2009
```Okay, we all [hopefully] know what a discriminated union is, and those of us who are trying out D2 can probably generally agree that std.variant.Algebraic makes life a good deal easier in this arena.  The actual usage is different, but it is definitely a gift from heaven. Except there's one thing it can't do: recursive types.

// D1
struct MyVar {
// ...
union {
int i;
double f;
char[] s;
MyVar[] l;	// lists good to go
MyVar[MyVar] h;	// hashtables good to go
}
// ...
}

// D2
alias Algebraic!(int, double, string, MyVar[], MyVar[MyVar]) MyVar;

Bzzzzzt!  Big ole error!

Fooey.  Because I want this, badly (its absolutely necessary for a program I'm working on).  I asked Andrei if he had any suggestion, especially since it is a known limitation mentioned explicitly in the specs.  No luck.  He did have an idea on syntax:

Algebraic!(int, double, string, This[])

Where the 'This' token is recognized specially as recursive.  It reads well, although my first thought was '_' similar to the way std.bind works.  The million dollar question is: how to make this work?

-- Chris Nicholson-Sauls

PS: Apologies, as I just got home from a very long day, so the brain is a bit tired and I probably came off silly.
```
```Chris Nicholson-Sauls wrote:
> Okay, we all [hopefully] know what a discriminated union is, and those of us who are trying out D2 can probably generally agree that std.variant.Algebraic makes life a good deal easier in this arena.  The actual usage is different, but it is definitely a gift from heaven. Except there's one thing it can't do: recursive types.
[snip]

Ok, I have a solution now. I'm not checking it in yet because I have a brazillion other changes in my tree and I don't want to break something. But I attach it to this message and it contains the following unittest:

unittest
{
alias Algebraic!(real, This[], This[int], This[This]) A;
A v1, v2, v3;
v2 = 5.0L;
v3 = 42.0L;
v1 = [ v2 ][];
auto v = v1.peek!(A[]);
writeln(v[0]);
v1 = [ 9 : v3 ];
writeln(v1);
v1 = [ v3 : v3 ];
writeln(v1);
}

The patterns This[], This*, This[U], U[This], and This[This] are detected, but alas, no general solution yet (I don't know how to). Anyhow, std.variant is starting to get interesting with this feature in tow.

Andrei

```
```Andrei Alexandrescu wrote:
> Ok, I have a solution now. I'm not checking it in yet because I have a brazillion other changes in my tree and I don't want to break something. But I attach it to this message and it contains the following unittest:
>
> unittest
> {
>     alias Algebraic!(real, This[], This[int], This[This]) A;
>     A v1, v2, v3;
>     v2 = 5.0L;
>     v3 = 42.0L;
>     v1 = [ v2 ][];
>     auto v = v1.peek!(A[]);
>     writeln(v[0]);
>     v1 = [ 9 : v3 ];
>     writeln(v1);
>     v1 = [ v3 : v3 ];
>     writeln(v1);
> }
>
> The patterns This[], This*, This[U], U[This], and This[This] are detected, but alas, no general solution yet (I don't know how to). Anyhow, std.variant is starting to get interesting with this feature in tow.
>
>
> Andrei
>

I've noticed a shortcoming that I somehow hadn't come across before. The same issue exists in the current Phobos2, so it isn't anything new.
Apparently (and this may be known to all but me already) in order to use an array type, you must also use its element type.  Doing otherwise results in tripping a static assert.

Example:

module test2;

import std.variant;

alias Algebraic!(void, string) var_t;

void main () {
var_t foo = "quux";
}

Shows: ../bin/../src/phobos/std/variant.d(418): static assert  "Cannot store a immutable(char) in a VariantN!(maxSize,void,immutable(char)[])"

Add invariant(char) to the list and all works fine, though.  The offending code is seemingly in VariantN.handler!(A):

case OpID.index:
auto me = cast(A*) pStore;
static if (isArray!(A))
{
// array type; input and output are the same VariantN
auto result = cast(VariantN*) parm;
size_t index = result.convertsTo!(int)
? result.get!(int) : result.get!(size_t);
*result = (*me)[index];

break;
}

Specifically the statement (*result = (*me)[index];) triggers it, by spawning an opAssign!(elem_type).  I'm not sure how to cleanly alter it right off the top of my head.

----------

On the other hand, the new form This[] works fine, so far.  The only missing feature is an opApply().

The form This[This]... Using 'foo.get!(table_t)[k] = v;' results in a range violation.  For the moment, they are essentially immutable hashes.
Could actually be fine for a number of purposes.

----------

If I get some extra free time this weekend (assuming V-day isn't the death of me) I'll hack away at it some and see if I can't figure some things out, on all counts above.

Oh, and THANKS.  :)

-- Chris Nicholson-Sauls
```
```Chris Nicholson-Sauls wrote:
> I've noticed a shortcoming that I somehow hadn't come across before. The same issue exists in the current Phobos2, so it isn't anything new.
>  Apparently (and this may be known to all but me already) in order to use an array type, you must also use its element type.  Doing otherwise results in tripping a static assert.
>
> Example:
>
>     module test2;
>
>     import std.variant;
>
>     alias Algebraic!(void, string) var_t;
>
>     void main () {
>         var_t foo = "quux";
>     }

This was an oversight caused by implementing opIndex, which I now fixed with credit. Thanks!

Now if you haven an Algebraic containing an array, you won't be able to call its opIndex directly; it will throw an exception. This is because opIndex wants to return the same type as this, and that type is unable to hold the element type of the array!

[snip]
> Specifically the statement (*result = (*me)[index];) triggers it, by spawning an opAssign!(elem_type).  I'm not sure how to cleanly alter it right off the top of my head.
>
> ----------
>
> On the other hand, the new form This[] works fine, so far.  The only missing feature is an opApply().

Ok, I filed a bug report on your behalf.

> The form This[This]... Using 'foo.get!(table_t)[k] = v;' results in a range violation.  For the moment, they are essentially immutable hashes.
>  Could actually be fine for a number of purposes.

That's because foo.get returns by value. Try using peek, which returns a pointer. Could you please post some code if that doesn't work for your case?

> ----------
>
> If I get some extra free time this weekend (assuming V-day isn't the death of me) I'll hack away at it some and see if I can't figure some things out, on all counts above.
>
> Oh, and THANKS.  :)

Advantage #1 of marrying a foreigner: you get to convince her that V-day is an artificial event created for commercial interests only because they want to sell blood diamonds. Watching "Blood Diamond" together a week before V-day recommended.

Andrei
```
```Andrei Alexandrescu wrote:
> Advantage #1 of marrying a foreigner: you get to convince her that V-day is an artificial event created for commercial interests only because they want to sell blood diamonds. Watching "Blood Diamond" together a week before V-day recommended.
>
> Andrei

Psst.. not to burst your bubble, but you're just as much a foreigner as she is.  So cut that out and go do something nice for your wife. :)

Later,
```
```Brad Roberts wrote:
> Andrei Alexandrescu wrote:
>> Advantage #1 of marrying a foreigner: you get to convince her that V-day
>> is an artificial event created for commercial interests only because
>> they want to sell blood diamonds. Watching "Blood Diamond" together a
>> week before V-day recommended.
>>
>> Andrei
>
> Psst.. not to burst your bubble, but you're just as much a foreigner as
> she is.  So cut that out and go do something nice for your wife. :)

Of course. That does not diminish the effectiveness of the technique in the least. The problems start of course when you share some V-Day equivalent in your native culture (e.g. March 8 for us). At that point I usually bring up the "When in Rome..." saying. :o)

Andrei
```
```Andrei Alexandrescu wrote:
>> Andrei Alexandrescu wrote:
>>> Advantage #1 of marrying a foreigner: you get to convince her that V-day
>>> is an artificial event created for commercial interests only because
>>> they want to sell blood diamonds. Watching "Blood Diamond" together a
>>> week before V-day recommended.
>>>
>>> Andrei
>>
>> Psst.. not to burst your bubble, but you're just as much a foreigner as
>> she is.  So cut that out and go do something nice for your wife. :)
>
> Of course. That does not diminish the effectiveness of the technique in the least. The problems start of course when you share some V-Day equivalent in your native culture (e.g. March 8 for us). At that point I usually bring up the "When in Rome..." saying. :o)
>
> Andrei

A couple of years back I introduced her to the Japanese "white day," which is (warning: oversimplified explanation ahead) held a week later, with the roles reversed as it were.  Works out well for me.

-- Chris Nicholson-Sauls
```
```Andrei Alexandrescu wrote:
> Chris Nicholson-Sauls wrote:
>> On the other hand, the new form This[] works fine, so far.  The only missing feature is an opApply().
>
> Ok, I filed a bug report on your behalf.

Thanks...  I somehow always forget we have that available.

>> The form This[This]... Using 'foo.get!(table_t)[k] = v;' results in a range violation.  For the moment, they are essentially immutable hashes.  Could actually be fine for a number of purposes.
>
> That's because foo.get returns by value. Try using peek, which returns a pointer. Could you please post some code if that doesn't work for your case?

Will try that tomorrow after work.

>> ----------
>>
>> If I get some extra free time this weekend (assuming V-day isn't the death of me) I'll hack away at it some and see if I can't figure some things out, on all counts above.
>>
>> Oh, and THANKS.  :)
>
> Advantage #1 of marrying a foreigner: you get to convince her that V-day is an artificial event created for commercial interests only because they want to sell blood diamonds. Watching "Blood Diamond" together a week before V-day recommended.
>
>
> Andrei

Thanks for the advice, I'll try it next year.  ;)

-- Chris Nicholson-Sauls
```