www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Implementing Haskell's Type-Level Quicksort in D

reply "Meta" <jared771 gmail.com> writes:
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
Feb 10 2014
next sibling parent "Stanislav Blinov" <stanislav.blinov gmail.com> writes:
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.
Feb 10 2014
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Feb 10 2014
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 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
Feb 10 2014
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 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
Feb 11 2014
prev sibling next sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
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.
Feb 11 2014
parent "Meta" <jared771 gmail.com> writes:
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.
Feb 11 2014
prev sibling parent reply "Meta" <jared771 gmail.com> writes:
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)
Feb 13 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Feb 13 2014
parent reply "Meta" <jared771 gmail.com> writes:
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.
Feb 13 2014
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Fri, Feb 14, 2014 at 3:54 AM, Meta <jared771 gmail.com> wrote:


 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.


`alias` is just a bit of syntax sugar, it does not (at least for
2.064) have the same power than fully defining a template and the
`is(...)` expression.

So yes, D does not have Haskell nice syntax for pattern matching. You
can do some pattern matching using templates, but it tends to be a bit


(Some would say that at least D does not force you to encode numbers
as succ/zero list, since you can use numbers directly as template
args, but that's another story).
Feb 13 2014
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Philippe Sigaud:


 So yes, D does not have Haskell nice syntax for pattern 
 matching.


I'd like some of such syntax for templates (and a little 
different syntax added to match structs inside switch statements: 
https://d.puremagic.com/issues/show_bug.cgi?id=596 ).

Bye,
bearophile
Feb 14 2014
prev sibling parent reply "Meta" <jared771 gmail.com> writes:
On Friday, 14 February 2014 at 06:05:08 UTC, Philippe Sigaud 
wrote:

 `alias` is just a bit of syntax sugar, it does not (at least for
 2.064) have the same power than fully defining a template and 
 the `is(...)` expression.


Right. What I was saying, however, is it is strange to me that 
this code will compile:

alias numPred(N: Succ!a, a) = a;

struct Number(a)
if (is(a == Zero) || is(a == Succ!x, x))
{}

enum numValue(N: Number!Zero) = 0;
enum numValue(N: Number!x, x) = numValue!(Number!(numPred!x)) + 1;

assert(numValue!(Number!Zero) == 0);
assert(numValue!(Number!Four) == 4);


While this code won't:

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

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;

assert(is(numlHead!list1 == Three));


Since list1 is a roughly similar construction to 
Number!(Succ!(Succ!(Succ!(Succ!Zero)))), it is surprising to me 
that the template matching system can correctly destructure the 
latter, while not the former. This is obviously a bug, I'm just 
surprised that it exists.


 So yes, D does not have Haskell nice syntax for pattern 
 matching. You can do some pattern matching using templates,



While it is heavier than Haskell's syntax, I have been 
consistently and pleasantly surprised by how powerful D's 
template pattern matching is (bugs notwithstanding). I wonder how 
well-known this is outside this mailing list...


 (Some would say that at least D does not force you to encode 
 numbers as succ/zero list, since you can use numbers directly 
 as template args, but that's another story).


Sure, but I want to stay as close to the original Haskell as 
possible (and Peano Numbers are pretty damn cool anyway).
Feb 14 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Meta:


 While it is heavier than Haskell's syntax, I have been 
 consistently and pleasantly surprised by how powerful D's 
 template pattern matching is (bugs notwithstanding). I wonder 
 how well-known this is outside this mailing list...


I keep reading blog posts that use Haskell and present supposed 
"marvels", using very complex things, that can be routinely done 
in D, and with less complexity for the brain of the programer, 
often leading to faster code and equally safe :-) So while I like 
several parts of Haskell, it's sometimes over-hyped (while D is 
nearly invisible).

Bye,
bearophile
Feb 14 2014
parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Fri, Feb 14, 2014 at 3:24 PM, bearophile <bearophileHUGS lycos.com> wrote:

 Meta:



 While it is heavier than Haskell's syntax, I have been consistently and
 pleasantly surprised by how powerful D's template pattern matching is (bugs
 notwithstanding). I wonder how well-known this is outside this mailing
 list...




Well, I have a tutorial, but I admit it being somewhat incomplete and
now partially out of date (2012).


 I keep reading blog posts that use Haskell and present supposed "marvels",
 using very complex things, that can be routinely done in D, and with less
 complexity for the brain of the programer, often leading to faster code and
 equally safe :-) So while I like several parts of Haskell, it's sometimes
 over-hyped (while D is nearly invisible).


Same here, same here! But you have to admit some of their examples are
pretty damn elegant :)

I remember doing some Haskell -> D translation (a bit like what Meta
is doing), making it work, doing the happy-happy dance, and then
suddenly realizing I could do the same compile-time computation in one
line of D ;)
Feb 14 2014