I'm trying to write a D implementation of Haskell's "type level quicksort"[0], but I'm already running into problems with std.typecons.Typedef. I have tried to translate this Haskell code:

 data Zero
 data Succ a

 -- booleans
 data True
 data False

 -- lists
 data Nil
 data Cons a b

 -- shortcuts
 type One   = Succ Zero
 type Two   = Succ One
 type Three = Succ Two
 type Four  = Succ Three



To this code in D:

import std.typecons;

struct Zero {}
struct Succ(a) {}

struct True  {}
struct False {}

struct Nil {}
struct Cons(a, b) {}

alias One = Typedef!(Succ!Zero);
alias Two = Typedef!(Succ!One);
alias Three = Typedef!(Succ!Two);
alias Four = Typedef!(Succ!Three);


void main()
{
	auto test = Four();
}

But I'm getting a compiler error when actually trying to construct a Four:

Error: template std.typecons.Typedef!(Succ!(Zero), Succ()).Typedef.Proxy!(Typedef_payload).opCall does not match any function template declaration.

Candidates are:
std.typecons.Typedef!(Succ!(Zero), Succ()).Typedef.Proxy!(Typedef_payload).opCall(this X, Args...)(auto ref Args args)



I tried defining a static opCall in the Zero struct that doesn't take any arguments, but that didn't make a difference. I'm guessing this is a bug with Typedef, but does anyone have an idea of where that bug might be?




1. http://www.haskell.org/haskellwiki/Type_arithmetic#An_Advanced_Example_:_Type-Level_Quicksort

On Monday, 10 February 2014 at 17:12:11 UTC, Meta wrote:

> I tried defining a static opCall in the Zero struct that doesn't take any arguments, but that didn't make a difference. I'm guessing this is a bug with Typedef, but does anyone have an idea of where that bug might be?

I would say it's not Typedef's fault, but std.typecons.Proxy's one. It has issues forwarding through opCall and opDispatch:

https://d.puremagic.com/issues/show_bug.cgi?id=11947

I'm currently working on a fix:

https://github.com/D-Programming-Language/phobos/pull/1914

Looks like a case for static opCall should also be covered.

Meta:

> alias One = Typedef!(Succ!Zero);
> alias Two = Typedef!(Succ!One);
> alias Three = Typedef!(Succ!Two);
> alias Four = Typedef!(Succ!Three);

Note that you need a "cookie" for those Typedefs, otherwise they are not useful. Unless this gets implemented:
http://d.puremagic.com/issues/show_bug.cgi?id=12100

Bye,
bearophile

> Note that you need a "cookie" for those Typedefs, otherwise they are not useful. Unless this gets implemented:
> http://d.puremagic.com/issues/show_bug.cgi?id=12100

See also:
http://d.puremagic.com/issues/show_bug.cgi?id=11828

Bye,
bearophile

On Mon, Feb 10, 2014 at 6:12 PM, Meta <jared771@gmail.com> wrote:
> I'm trying to write a D implementation of Haskell's "type level quicksort"[0], but I'm already running into problems with std.typecons.Typedef. I have tried to translate this Haskell code:

> alias One = Typedef!(Succ!Zero);
> alias Two = Typedef!(Succ!One);
> alias Three = Typedef!(Succ!Two);
> alias Four = Typedef!(Succ!Three);

Did you try just using:

alias One = Succ!Zero;
alias Two = Succ!One;
alias Three = Succ!Two;
alias Four = Succ!Three;

?

I remember having fun implementing type-level addition and multiplication using D and this Peano construct, so Quicksort is probably possible.

On Tuesday, 11 February 2014 at 19:13:01 UTC, Philippe Sigaud wrote:
> On Mon, Feb 10, 2014 at 6:12 PM, Meta <jared771@gmail.com> wrote:
>> I'm trying to write a D implementation of Haskell's "type level
>> quicksort"[0], but I'm already running into problems with
>> std.typecons.Typedef. I have tried to translate this Haskell code:
>
>> alias One = Typedef!(Succ!Zero);
>> alias Two = Typedef!(Succ!One);
>> alias Three = Typedef!(Succ!Two);
>> alias Four = Typedef!(Succ!Three);
>
> Did you try just using:
>
> alias One = Succ!Zero;
> alias Two = Succ!One;
> alias Three = Succ!Two;
> alias Four = Succ!Three;
>
> ?
>
> I remember having fun implementing type-level addition and
> multiplication using D and this Peano construct, so Quicksort is
> probably possible.

I have tried once before only semi-seriously, and using just a bare alias was my initial strategy. It didn't work for some reason, and I can't really remember why. Maybe I'll give it another try and just drop the Typedef.

>> alias One = Typedef!(Succ!Zero);
>> alias Two = Typedef!(Succ!One);
>> alias Three = Typedef!(Succ!Two);
>> alias Four = Typedef!(Succ!Three);
>
> Note that you need a "cookie" for those Typedefs, otherwise they are not useful.

They are different types, so my comment is wrong :-) I don't understand why you have used Typedef there.

Bye,
bearophile

Coming back to this after a few days. I got a bit farther, but I'm running into trouble with the template args pattern matching. I'd like to turn this code:

 list1 :: Cons Three (Cons Two (Cons Four (Cons One Nil)))
 list1 = undefined

 numlHead :: Cons a b -> a
 numlHead = const undefined

 numlTail :: Cons a b -> b
 numlTail = const undefined'


Into this D code:

alias list1 = Cons!(Three, Cons!(Two, Cons!(Four, Cons!(One, Nil))));

alias numlHead(L: Cons!(a, b), a, b) = a;

alias numlTail(L: Cons!(a, b), a, b) = b;


But the compiler is complaining loudly about a mismatch:

/d43/f234.d(39): Error: template instance numlHead!(list1) does not match template declaration numlHead(L : Cons!(a, b), a, b)

Meta:

> alias list1 = Cons!(Three, Cons!(Two, Cons!(Four, Cons!(One, Nil))));
>
> alias numlHead(L: Cons!(a, b), a, b) = a;
>
> alias numlTail(L: Cons!(a, b), a, b) = b;
>
>
> But the compiler is complaining loudly about a mismatch:
>
> /d43/f234.d(39): Error: template instance numlHead!(list1) does not match template declaration numlHead(L : Cons!(a, b), a, b)

See a recent thread of mine:
http://forum.dlang.org/thread/vlwgufdlpjgewpnnhkma@forum.dlang.org

Currently I think you have to accept types and aliases with a regular template syntax, and verify the types and kinds with template constraints. Something like (untested):

template numlTail(C) if (TemplateOf!(C, Cons)) {
    alias numlTail = TemplateArgsOf!(C)[1];
}

Bye,
bearophile

On Friday, 14 February 2014 at 02:41:12 UTC, bearophile wrote:
> Meta:
>
>> alias list1 = Cons!(Three, Cons!(Two, Cons!(Four, Cons!(One, Nil))));
>>
>> alias numlHead(L: Cons!(a, b), a, b) = a;
>>
>> alias numlTail(L: Cons!(a, b), a, b) = b;
>>
>>
>> But the compiler is complaining loudly about a mismatch:
>>
>> /d43/f234.d(39): Error: template instance numlHead!(list1) does not match template declaration numlHead(L : Cons!(a, b), a, b)
>
> See a recent thread of mine:
> http://forum.dlang.org/thread/vlwgufdlpjgewpnnhkma@forum.dlang.org
>
> Currently I think you have to accept types and aliases with a regular template syntax, and verify the types and kinds with template constraints. Something like (untested):
>
> template numlTail(C) if (TemplateOf!(C, Cons)) {
>     alias numlTail = TemplateArgsOf!(C)[1];
> }
>
> Bye,
> bearophile

It seems strange that it would choke now, as Cons is a struct. Therefore, Cons!(Three, ...) should create a new type, and `L: Cons!(a, b), a, b` shouldn't be any trouble to destructure into two types, `Three` and `Cons!(Two, ...)`. It had no problem handling the Succ and Number struct templates I defined.