digitalmars.D.learn - Implementing Haskell's Type-Level Quicksort in D
- Meta (47/47) Feb 10 2014 I'm trying to write a D implementation of Haskell's "type level
- Stanislav Blinov (7/11) Feb 10 2014 I would say it's not Typedef's fault, but std.typecons.Proxy's
- bearophile (6/10) Feb 10 2014 Note that you need a "cookie" for those Typedefs, otherwise they
- bearophile (4/7) Feb 10 2014 See also:
- bearophile (4/10) Feb 11 2014 They are different types, so my comment is wrong :-) I don't
- Philippe Sigaud (10/17) Feb 11 2014 Did you try just using:
- Meta (6/25) Feb 11 2014 I have tried once before only semi-seriously, and using just a
- Meta (17/17) Feb 13 2014 Coming back to this after a few days. I got a bit farther, but
- bearophile (11/18) Feb 13 2014 See a recent thread of mine:
- Meta (6/30) Feb 13 2014 It seems strange that it would choke now, as Cons is a struct.
- Philippe Sigaud (10/15) Feb 13 2014 `alias` is just a bit of syntax sugar, it does not (at least for
- bearophile (6/8) Feb 14 2014 I'd like some of such syntax for templates (and a little
- Meta (31/40) Feb 14 2014 Right. What I was saying, however, is it is strange to me that
- bearophile (9/13) Feb 14 2014 I keep reading blog posts that use Haskell and present supposed
- Philippe Sigaud (9/19) Feb 14 2014 Well, I have a tutorial, but I admit it being somewhat incomplete and
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
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
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
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=12100See also: http://d.puremagic.com/issues/show_bug.cgi?id=11828 Bye, bearophile
Feb 10 2014
They are different types, so my comment is wrong :-) I don't understand why you have used Typedef there. Bye, bearophilealias 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.
Feb 11 2014
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
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 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.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
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
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
On Friday, 14 February 2014 at 02:41:12 UTC, bearophile wrote:Meta: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 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
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
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
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
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
On Fri, Feb 14, 2014 at 3:24 PM, bearophile <bearophileHUGS lycos.com> wrote:Meta:Well, I have a tutorial, but I admit it being somewhat incomplete and now partially out of date (2012).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).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