Implementing Haskell's Type-Level Quicksort in D

[Meta]

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,
> but it tends to be a bit heavier than ML/F#/Haskell.

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).