Following the use of This in Algebraic (https://github.com/D-Programming-Language/phobos/pull/3394), we can apply the same idea to Tuple, thus allowing one to create self-referential types with ease.

Consider:

// A singly-linked list is payload + pointer to list
alias List(T) = Tuple!(T, This*);

// A binary tree is payload + two children
alias Tree(T) = Tuple!(T, This*, This*);
// or
alias Tree(T) = Tuple!(T, "payload", This*, "left", This*, "right");

// A binary tree with payload only in leaves
alias Tree2(T) = Algebraic!(T, Tuple!(This*, This*));

Is there interest in this? Other application ideas to motivate the addition?


Andrei

On Tuesday, 9 June 2015 at 15:28:16 UTC, Andrei Alexandrescu wrote:
> Following the use of This in Algebraic (https://github.com/D-Programming-Language/phobos/pull/3394), we can apply the same idea to Tuple, thus allowing one to create self-referential types with ease.
>
> Consider:
>
> // A singly-linked list is payload + pointer to list
> alias List(T) = Tuple!(T, This*);
>
> // A binary tree is payload + two children
> alias Tree(T) = Tuple!(T, This*, This*);
> // or
> alias Tree(T) = Tuple!(T, "payload", This*, "left", This*, "right");
>
> // A binary tree with payload only in leaves
> alias Tree2(T) = Algebraic!(T, Tuple!(This*, This*));
>
> Is there interest in this? Other application ideas to motivate the addition?

Yes, I'm interested. As a practical example, how would you represent a JSON AST type, which might look something like this in OCaml (type json at the top)

  http://mjambon.com/yojson-doc/Yojson.Safe.html

using Algebraic? And once you've encoded it using Algebraic, how do you operate on it, for example, how would you write a 'toString' on the AST? These are both straightforward in OCaml (the straightforward yet inefficient toString pracitically writes itself from the definition, the efficient version with buffers is only a little more involved) so a D version would be a good test.

On 6/9/15 8:59 AM, Brian Rogoff wrote:
> On Tuesday, 9 June 2015 at 15:28:16 UTC, Andrei Alexandrescu wrote:
>> Following the use of This in Algebraic
>> (https://github.com/D-Programming-Language/phobos/pull/3394), we can
>> apply the same idea to Tuple, thus allowing one to create
>> self-referential types with ease.
>>
>> Consider:
>>
>> // A singly-linked list is payload + pointer to list
>> alias List(T) = Tuple!(T, This*);
>>
>> // A binary tree is payload + two children
>> alias Tree(T) = Tuple!(T, This*, This*);
>> // or
>> alias Tree(T) = Tuple!(T, "payload", This*, "left", This*, "right");
>>
>> // A binary tree with payload only in leaves
>> alias Tree2(T) = Algebraic!(T, Tuple!(This*, This*));
>>
>> Is there interest in this? Other application ideas to motivate the
>> addition?
>
> Yes, I'm interested. As a practical example, how would you represent a
> JSON AST type, which might look something like this in OCaml (type json
> at the top)
>
>    http://mjambon.com/yojson-doc/Yojson.Safe.html
>
> using Algebraic? And once you've encoded it using Algebraic, how do you
> operate on it, for example, how would you write a 'toString' on the AST?
> These are both straightforward in OCaml (the straightforward yet
> inefficient toString pracitically writes itself from the definition, the
> efficient version with buffers is only a little more involved) so a D
> version would be a good test.

Excellent example! Here's a shot:

alias JsonPayload = Algebraic!(
    bool,
    double,
    long,
    string,
    This[],
    This[string]
);

I notice that in Ocaml you get to give names to fields, so I added https://issues.dlang.org/show_bug.cgi?id=14670 to investigate the matter.

Converting a complex JsonPayload to string can be done with relative ease by using visitation.


Thansk,

Andrei

On 06/09/2015 05:28 PM, Andrei Alexandrescu wrote:
> Following the use of This in Algebraic
> (https://github.com/D-Programming-Language/phobos/pull/3394), we can
> apply the same idea to Tuple, thus allowing one to create
> self-referential types with ease.
>
> Consider:
>
> // A singly-linked list is payload + pointer to list
> alias List(T) = Tuple!(T, This*);
>
> // A binary tree is payload + two children
> alias Tree(T) = Tuple!(T, This*, This*);
> // or
> alias Tree(T) = Tuple!(T, "payload", This*, "left", This*, "right");
>
> // A binary tree with payload only in leaves
> alias Tree2(T) = Algebraic!(T, Tuple!(This*, This*));
>
> Is there interest in this? Other application ideas to motivate the
> addition?
>
>
> Andrei

Well, the issue is with this kind of use case:

alias List(T)=Algebraic!(Tuple!(),Tuple!(T,This*));

On 6/9/15 3:58 PM, Timon Gehr wrote:
> On 06/09/2015 05:28 PM, Andrei Alexandrescu wrote:
>> Following the use of This in Algebraic
>> (https://github.com/D-Programming-Language/phobos/pull/3394), we can
>> apply the same idea to Tuple, thus allowing one to create
>> self-referential types with ease.
>>
>> Consider:
>>
>> // A singly-linked list is payload + pointer to list
>> alias List(T) = Tuple!(T, This*);
>>
>> // A binary tree is payload + two children
>> alias Tree(T) = Tuple!(T, This*, This*);
>> // or
>> alias Tree(T) = Tuple!(T, "payload", This*, "left", This*, "right");
>>
>> // A binary tree with payload only in leaves
>> alias Tree2(T) = Algebraic!(T, Tuple!(This*, This*));
>>
>> Is there interest in this? Other application ideas to motivate the
>> addition?
>>
>>
>> Andrei
>
> Well, the issue is with this kind of use case:
>
> alias List(T)=Algebraic!(Tuple!(),Tuple!(T,This*));

So a list is either nothing, or a head and a tail. What is the problem here? -- Andrei

On Tuesday, 9 June 2015 at 23:04:41 UTC, Andrei Alexandrescu wrote:
> On 6/9/15 3:58 PM, Timon Gehr wrote:
>> On 06/09/2015 05:28 PM, Andrei Alexandrescu wrote:
>>> Following the use of This in Algebraic
>>> (https://github.com/D-Programming-Language/phobos/pull/3394), we can
>>> apply the same idea to Tuple, thus allowing one to create
>>> self-referential types with ease.
>>>
>>> Consider:
>>>
>>> // A singly-linked list is payload + pointer to list
>>> alias List(T) = Tuple!(T, This*);
>>>
>>> // A binary tree is payload + two children
>>> alias Tree(T) = Tuple!(T, This*, This*);
>>> // or
>>> alias Tree(T) = Tuple!(T, "payload", This*, "left", This*, "right");
>>>
>>> // A binary tree with payload only in leaves
>>> alias Tree2(T) = Algebraic!(T, Tuple!(This*, This*));
>>>
>>> Is there interest in this? Other application ideas to motivate the
>>> addition?
>>>
>>>
>>> Andrei
>>
>> Well, the issue is with this kind of use case:
>>
>> alias List(T)=Algebraic!(Tuple!(),Tuple!(T,This*));
>
> So a list is either nothing, or a head and a tail. What is the problem here? -- Andrei

The `This*` here is not mapped to `Algebraic!(Tuple!(),Tuple!(T,This*))` - it's mapped to the closest containing tuple, `Tuple!(T,This*)`. This means that the tail is not a list - it's a head and a tail. The list is either empty or infinite.

At any rate, I think this feature is useful enough even if it doesn't support such use cases. You can always declare a list as a regular struct...

On 06/10/2015 01:04 AM, Andrei Alexandrescu wrote:
> On 6/9/15 3:58 PM, Timon Gehr wrote:
>> On 06/09/2015 05:28 PM, Andrei Alexandrescu wrote:
>>> Following the use of This in Algebraic
>>> (https://github.com/D-Programming-Language/phobos/pull/3394), we can
>>> apply the same idea to Tuple, thus allowing one to create
>>> self-referential types with ease.
>>>
>>> Consider:
>>>
>>> // A singly-linked list is payload + pointer to list
>>> alias List(T) = Tuple!(T, This*);
>>>
>>> // A binary tree is payload + two children
>>> alias Tree(T) = Tuple!(T, This*, This*);
>>> // or
>>> alias Tree(T) = Tuple!(T, "payload", This*, "left", This*, "right");
>>>
>>> // A binary tree with payload only in leaves
>>> alias Tree2(T) = Algebraic!(T, Tuple!(This*, This*));
>>>
>>> Is there interest in this? Other application ideas to motivate the
>>> addition?
>>>
>>>
>>> Andrei
>>
>> Well, the issue is with this kind of use case:
>>
>> alias List(T)=Algebraic!(Tuple!(),Tuple!(T,This*));
>
> So a list is either nothing, or a head and a tail. What is the problem
> here? -- Andrei

It's about which type 'This' refers to. Is it the Algebraic or the Tuple? I assume here it would be the algebraic, which is expected, but it can get non-obvious quickly especially when e.g. a template parameter is a recursive tuple and the template uses the type in an Algebraic. It's just a mess. E.g. what happens if you do List!(Tree!int)? ReplaceType would need to treat Tuples specially, and then you lose the other semantics even though it might sometimes be needed. 'This' is a cute hack, but it doesn't replace a proper template fixpoint operator.

On 06/10/2015 01:43 AM, Idan Arye wrote:
> On Tuesday, 9 June 2015 at 23:04:41 UTC, Andrei Alexandrescu wrote:
>> On 6/9/15 3:58 PM, Timon Gehr wrote:
>>> On 06/09/2015 05:28 PM, Andrei Alexandrescu wrote:
>>>> Following the use of This in Algebraic
>>>> (https://github.com/D-Programming-Language/phobos/pull/3394), we can
>>>> apply the same idea to Tuple, thus allowing one to create
>>>> self-referential types with ease.
>>>>
>>>> Consider:
>>>>
>>>> // A singly-linked list is payload + pointer to list
>>>> alias List(T) = Tuple!(T, This*);
>>>>
>>>> // A binary tree is payload + two children
>>>> alias Tree(T) = Tuple!(T, This*, This*);
>>>> // or
>>>> alias Tree(T) = Tuple!(T, "payload", This*, "left", This*, "right");
>>>>
>>>> // A binary tree with payload only in leaves
>>>> alias Tree2(T) = Algebraic!(T, Tuple!(This*, This*));
>>>>
>>>> Is there interest in this? Other application ideas to motivate the
>>>> addition?
>>>>
>>>>
>>>> Andrei
>>>
>>> Well, the issue is with this kind of use case:
>>>
>>> alias List(T)=Algebraic!(Tuple!(),Tuple!(T,This*));
>>
>> So a list is either nothing, or a head and a tail. What is the problem
>> here? -- Andrei
>
> The `This*` here is not mapped to `Algebraic!(Tuple!(),Tuple!(T,This*))`
> - it's mapped to the closest containing tuple, `Tuple!(T,This*)`. This
> means that the tail is not a list - it's a head and a tail. The list is
> either empty or infinite.
>

Exactly. Probably it was confusing that I used a raw pointer and not some kind of NonNull!T hack. Non-null was the intention.

On 6/9/15 4:43 PM, Idan Arye wrote:
>
> The `This*` here is not mapped to `Algebraic!(Tuple!(),Tuple!(T,This*))`
> - it's mapped to the closest containing tuple, `Tuple!(T,This*)`. This
> means that the tail is not a list - it's a head and a tail. The list is
> either empty or infinite.
>
> At any rate, I think this feature is useful enough even if it doesn't
> support such use cases. You can always declare a list as a regular
> struct...

Way ahead of you :o). Algebraic would use std.variant.This, whereas Tuple would use std.typecons.This. So you get to choose. -- Andrei

On Tuesday, 9 June 2015 at 15:28:16 UTC, Andrei Alexandrescu wrote:
> Following the use of This in Algebraic (https://github.com/D-Programming-Language/phobos/pull/3394), we can apply the same idea to Tuple, thus allowing one to create self-referential types with ease.
>
> Consider:
>
> // A singly-linked list is payload + pointer to list
> alias List(T) = Tuple!(T, This*);
>
> // A binary tree is payload + two children
> alias Tree(T) = Tuple!(T, This*, This*);
> // or
> alias Tree(T) = Tuple!(T, "payload", This*, "left", This*, "right");
>
> // A binary tree with payload only in leaves
> alias Tree2(T) = Algebraic!(T, Tuple!(This*, This*));
>
> Is there interest in this? Other application ideas to motivate the addition?
>
>
> Andrei

Useful, not ground breaking. I would not add right now.