digitalmars.D - [Challenge] implementing the ambiguous operator in D
- Philippe Sigaud <philippe.sigaud gmail.com> Sep 01 2010
- Peter Alexander <peter.alexander.au gmail.com> Sep 01 2010
- Pelle <pelle.mansson gmail.com> Sep 01 2010
- Peter Alexander <peter.alexander.au gmail.com> Sep 02 2010
- Philippe Sigaud <philippe.sigaud gmail.com> Sep 02 2010
- "Nick Sabalausky" <a a.a> Sep 02 2010
- "Nick Sabalausky" <a a.a> Sep 02 2010
- Peter Alexander <peter.alexander.au gmail.com> Sep 03 2010
- "Simen kjaeraas" <simen.kjaras gmail.com> Sep 03 2010
- Peter Alexander <peter.alexander.au gmail.com> Sep 03 2010
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Sep 05 2010
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Sep 05 2010
- Peter Alexander <peter.alexander.au gmail.com> Sep 06 2010
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Sep 06 2010
- Peter Alexander <peter.alexander.au gmail.com> Sep 06 2010
- Philippe Sigaud <philippe.sigaud gmail.com> Sep 06 2010
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Sep 06 2010
- Peter Alexander <peter.alexander.au gmail.com> Sep 07 2010
- bearophile <bearophileHUGS lycos.com> Sep 05 2010
- bearophile <bearophileHUGS lycos.com> Sep 05 2010
- Justin Johansson <no spam.com> Sep 03 2010
- bearophile <bearophileHUGS lycos.com> Sep 03 2010
- Don <nospam nospam.com> Sep 03 2010
- Peter Alexander <peter.alexander.au gmail.com> Sep 03 2010
- bearophile <bearophileHUGS lycos.com> Sep 03 2010
- Don <nospam nospam.com> Sep 03 2010
- bearophile <bearophileHUGS lycos.com> Sep 03 2010
- bearophile <bearophileHUGS lycos.com> Sep 04 2010
- bearophile <bearophileHUGS lycos.com> Sep 05 2010
- Philippe Sigaud <philippe.sigaud gmail.com> Sep 03 2010
- Philippe Sigaud <philippe.sigaud gmail.com> Sep 03 2010
- "Simen kjaeraas" <simen.kjaras gmail.com> Sep 03 2010
- "Simen kjaeraas" <simen.kjaras gmail.com> Sep 03 2010
- "Simen kjaeraas" <simen.kjaras gmail.com> Sep 03 2010
- Philippe Sigaud <philippe.sigaud gmail.com> Sep 03 2010
- Philippe Sigaud <philippe.sigaud gmail.com> Sep 04 2010
- "Simen kjaeraas" <simen.kjaras gmail.com> Sep 05 2010
- Philippe Sigaud <philippe.sigaud gmail.com> Sep 05 2010
- Philippe Sigaud <philippe.sigaud gmail.com> Sep 05 2010
- "Denis Koroskin" <2korden gmail.com> Sep 05 2010
- Philippe Sigaud <philippe.sigaud gmail.com> Sep 05 2010
- Philippe Sigaud <philippe.sigaud gmail.com> Sep 05 2010
- Philippe Sigaud <philippe.sigaud gmail.com> Sep 05 2010
- "Denis Koroskin" <2korden gmail.com> Sep 05 2010
- "Denis Koroskin" <2korden gmail.com> Sep 05 2010
- "Denis Koroskin" <2korden gmail.com> Sep 05 2010
- "Simen kjaeraas" <simen.kjaras gmail.com> Sep 05 2010
- "Simen kjaeraas" <simen.kjaras gmail.com> Sep 06 2010
- "Simen kjaeraas" <simen.kjaras gmail.com> Sep 06 2010
- "Simen kjaeraas" <simen.kjaras gmail.com> Sep 06 2010
- "Simen kjaeraas" <simen.kjaras gmail.com> Sep 06 2010
--001636c5b2bdd3ef89048f384137 Content-Type: text/plain; charset=ISO-8859-1 Hey, this question on SO makes for a good challenge: http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d The amb operator does this: amb([1, 2]) * amb([3, 4, 5]) == amb([3, 4, 5, 6, 8, 10]) amb(["hello", "world"]) ~ amb(["qwerty"]) == amb(["helloqwerty", "worldqwerty"]) amb(["hello", "world"]) ~ "qwerty" == amb(["helloqwerty", "worldqwerty"]) amb(["hello", "very long string"]).length = amb([5, 16]) (I find the guy examples much more comprehensible that the articles he links to) Are people interested in trying this? Peter, can we discuss your solution here? Philippe --001636c5b2bdd3ef89048f384137 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Hey, this question on SO makes for a good challenge:<br><br><a href=3D"http= ://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implem= ent-the-amb-operator-in-d">http://stackoverflow.com/questions/3608834/is-it= -possible-to-generically-implement-the-amb-operator-in-d</a><br> <br>The amb operator does this:<br><br><pre class=3D"prettyprint"><code><sp= an class=3D"pln">amb</span><span class=3D"pun">([</span><span class=3D"lit"=1</span><span class=3D"pun">,</span><span class=3D"pln"> </span><span clas=
<span class=3D"pun">*</span><span class=3D"pln"> amb</span><span class=3D"p= un">([</span><span class=3D"lit">3</span><span class=3D"pun">,</span><span = class=3D"pln"> </span><span class=3D"lit">4</span><span class=3D"pun">,</sp= an><span class=3D"pln"> </span><span class=3D"lit">5</span><span class=3D"p= un">])</span><span class=3D"pln"> </span><span class=3D"pun">=3D=3D</span><= span class=3D"pln"> amb</span><span class=3D"pun">([</span><span class=3D"l= it">3</span><span class=3D"pun">,</span><span class=3D"pln"> </span><span c= lass=3D"lit">4</span><span class=3D"pun">,</span><span class=3D"pln"> </spa= n><span class=3D"lit">5</span><span class=3D"pun">,</span><span class=3D"pl= n"> </span><span class=3D"lit">6</span><span class=3D"pun">,</span><span cl= ass=3D"pln"> </span><span class=3D"lit">8</span><span class=3D"pun">,</span=<span class=3D"pln"> </span><span class=3D"lit">10</span><span class=3D"pu=
amb</span><span class=3D"pun">([</span><span class=3D"str">"hello"= ;</span><span class=3D"pun">,</span><span class=3D"pln"> </span><span class= =3D"str">"world"</span><span class=3D"pun">])</span><span class= =3D"pln"> </span><span class=3D"pun">~</span><span class=3D"pln"> amb</span=<span class=3D"pun">([</span><span class=3D"str">"qwerty"</span>=
">=3D=3D</span><span class=3D"pln"> amb</span><span class=3D"pun">([</span>= <span class=3D"str">"helloqwerty"</span><span class=3D"pun">,</sp= an><span class=3D"pln"> </span><span class=3D"str">"worldqwerty"<= /span><span class=3D"pun">])</span><span class=3D"pln"><br> amb</span><span class=3D"pun">([</span><span class=3D"str">"hello"= ;</span><span class=3D"pun">,</span><span class=3D"pln"> </span><span class= =3D"str">"world"</span><span class=3D"pun">])</span><span class= =3D"pln"> </span><span class=3D"pun">~</span><span class=3D"pln"> </span><s= pan class=3D"str">"qwerty"</span><span class=3D"pln"> </span><spa= n class=3D"pun">=3D=3D</span><span class=3D"pln"> amb</span><span class=3D"= pun">([</span><span class=3D"str">"helloqwerty"</span><span class= =3D"pun">,</span><span class=3D"pln"> </span><span class=3D"str">"worl= dqwerty"</span><span class=3D"pun">])</span><span class=3D"pln"><br> amb</span><span class=3D"pun">([</span><span class=3D"str">"hello"= ;</span><span class=3D"pun">,</span><span class=3D"pln"> </span><span class= =3D"str">"very long string"</span><span class=3D"pun">]).</span><= span class=3D"pln">length </span><span class=3D"pun">=3D</span><span class= =3D"pln"> amb</span><span class=3D"pun">([</span><span class=3D"lit">5</spa= n><span class=3D"pun">,</span><span class=3D"pln"> </span><span class=3D"li= t">16</span><span class=3D"pun">])<br> </span><span class=3D"pln"></span></code></pre><br>(I find the guy examples= much more comprehensible that the articles he links to)<br><br>Are people = interested in trying this?<br><br>Peter, can we discuss your solution here?= <br> <br><br>Philippe<br><br> --001636c5b2bdd3ef89048f384137--
Sep 01 2010
On 1/09/10 9:08 PM, Philippe Sigaud wrote:Peter, can we discuss your solution here?
Sure, I'd be interested to hear any improvements. Like I said in my answer, I'm still learning D so I'm sure there's many issues. For example, I made no attempt for const-correctness or anything like that (mostly for simplicity). In particular, I'd be interested in knowing if there's a better way to write opDispatch i.e. a way that doesn't use that ugly mixin.
Sep 01 2010
On 09/01/2010 11:49 PM, Peter Alexander wrote:On 1/09/10 9:08 PM, Philippe Sigaud wrote:Peter, can we discuss your solution here?
Sure, I'd be interested to hear any improvements. Like I said in my answer, I'm still learning D so I'm sure there's many issues. For example, I made no attempt for const-correctness or anything like that (mostly for simplicity). In particular, I'd be interested in knowing if there's a better way to write opDispatch i.e. a way that doesn't use that ugly mixin.
It needs opEquals :-) something like this auto opEquals(E e) { auto cmp = (E a) { return a == e; }; return map!cmp(r); } ... writeln(5 == amb([1,2,3,4,5])); [false, false, false, false, true]
Sep 01 2010
Peter Alexander <peter.alexander.au gmail.com> On 2/09/10 7:34 AM, Pelle wrote:It needs opEquals :-)
Yeah, it needs a lot of things :) You could easily add unary operators as well (e.g. so that -amb([1, 2]) == [-1, -2]. I didn't bother adding more than I did because it would make the post too large, and wouldn't really add anything (I thought that the binary ops + dispatch covered most of the interesting cases). Also, I think it would supposed to return amb(map!...) instead of just returning map!... (otherwise you couldn't chain them), but that's a simple fix.
Sep 02 2010
--0016368e1ecf18da4e048f4be0d4 Content-Type: text/plain; charset=ISO-8859-1 On Thu, Sep 2, 2010 at 09:06, Peter Alexander <peter.alexander.au gmail.com>wrote:On 2/09/10 7:34 AM, Pelle wrote:It needs opEquals :-)
Yeah, it needs a lot of things :) You could easily add unary operators as well (e.g. so that -amb([1, 2]) == [-1, -2]. I didn't bother adding more than I did because it would make the post too large, and wouldn't really add anything (I thought that the binary ops + dispatch covered most of the interesting cases). Also, I think it would supposed to return amb(map!...) instead of just returning map!... (otherwise you couldn't chain them), but that's a simple fix.
Yes, like Haskell monads: get into, transform, return a wrapped result. Does your code compile for you? I tried it when you posted it on SO and the .length, .replace("a","u") didn't work. I had to change opDispatch from auto opDispatch(string f)() { mixin("return map!((E e) { return e."~f~"; })(r);"); } to: auto opDispatch(string f)() { return map!(unaryFun!("a."~f))(r); } I tried to do the same for the dispatch with arguments, but got very strange errors. DMD told me it couldn't get the args at CT. Oh, but you changed your code on SO. It can know do the first example too. That's good, and was in fact my main subject of interest. Amb seems to be like the product of two ranges (with an operator), which is then flattened. What I don't get is the link with the ruby article and its use of if. Philippe --0016368e1ecf18da4e048f4be0d4 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">On Thu, Sep 2, 2010 at 09:06, Peter Alex= ander <span dir=3D"ltr"><<a href=3D"http://peter.alexander.au">peter.ale= xander.au</a> <a href=3D"http://gmail.com">gmail.com</a>></span> wrote:<= br><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; bo= rder-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> On 2/09/10 7:34 AM, Pelle wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> It needs opEquals :-)<br> </blockquote> <br> Yeah, it needs a lot of things :)<br> <br> You could easily add unary operators as well (e.g. so that -amb([1, 2]) =3D= =3D [-1, -2]. I didn't bother adding more than I did because it would m= ake the post too large, and wouldn't really add anything (I thought tha= t the binary ops + dispatch covered most of the interesting cases).<br> <br> Also, I think it would supposed to return amb(map!...) instead of just retu= rning map!... (otherwise you couldn't chain them), but that's a sim= ple fix.<br></blockquote><div><br>Yes, like Haskell monads: get into, trans= form, return a wrapped result.<br> =A0</div></div><br>Does your code compile for you? I tried it when you post= ed it on SO and the .length, .replace("a","u") didn'= ;t work.<br>I had to change opDispatch from<br><br>=A0=A0=A0 auto opDispatc= h(string f)()<br> =A0=A0=A0 {<br>=A0=A0=A0=A0=A0=A0=A0 mixin("return map!((E e) { return= e."~f~"; })(r);");<br>=A0=A0=A0 }<br><br>to:<br><br>=A0=A0= =A0 auto opDispatch(string f)()<br>=A0=A0=A0 {<br>=A0=A0=A0=A0=A0=A0=A0 ret= urn map!(unaryFun!("a."~f))(r);<br>=A0=A0=A0 }<br> <br>I tried to do the same for the dispatch with arguments, but got very st= range errors. DMD told me it couldn't get the args at CT.<br><br>Oh, bu= t you changed your code on SO. It can know do the first example too. That&#= 39;s good, and was in fact my main subject of interest. Amb seems to be lik= e the product of two ranges (with an operator), which is then flattened.<br=
f.<br><br><br>Philippe<br><br> --0016368e1ecf18da4e048f4be0d4--
Sep 02 2010
"Philippe Sigaud" <philippe.sigaud gmail.com> wrote in message news:mailman.42.1283371696.858.digitalmars-d puremagic.com...Hey, this question on SO makes for a good challenge: http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d The amb operator does this: amb([1, 2]) * amb([3, 4, 5]) == amb([3, 4, 5, 6, 8, 10]) amb(["hello", "world"]) ~ amb(["qwerty"]) == amb(["helloqwerty", "worldqwerty"]) amb(["hello", "world"]) ~ "qwerty" == amb(["helloqwerty", "worldqwerty"]) amb(["hello", "very long string"]).length = amb([5, 16])
Interesting thing, but devil's advocate: What would be the uses/benefits of that versus just having "for each element" versions of the operators? Also, "ambiguous" seems like a rather odd name for what it does. I don't see how ambiguity has anything to do with it. That disconnect made it difficult at first for me to understand what it was. It's more like an "elementwise" or something. Certainly useful, I had reason to make a similar function once: /// ctfe_subMapJoin("Hi WHO. ", "WHO", ["Joey", "Q", "Sue"]) /// --> "Hi Joey. Hi Q. Hi Sue. " T ctfe_subMapJoin(T)(T str, T match, T[] replacements) if(isSomeString!T) { T value = ""; foreach(T replace; replacements) value ~= ctfe_substitute(str, match, replace); return value; } Though I'll grant that's a questionable name for it. I wasn't sure what else to call it though.
Sep 02 2010
"Nick Sabalausky" <a a.a> wrote in message news:i5p68t$2pth$1 digitalmars.com..."Philippe Sigaud" <philippe.sigaud gmail.com> wrote in message news:mailman.42.1283371696.858.digitalmars-d puremagic.com...Hey, this question on SO makes for a good challenge: http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d The amb operator does this: amb([1, 2]) * amb([3, 4, 5]) == amb([3, 4, 5, 6, 8, 10]) amb(["hello", "world"]) ~ amb(["qwerty"]) == amb(["helloqwerty", "worldqwerty"]) amb(["hello", "world"]) ~ "qwerty" == amb(["helloqwerty", "worldqwerty"]) amb(["hello", "very long string"]).length = amb([5, 16])
Interesting thing, but devil's advocate: What would be the uses/benefits of that versus just having "for each element" versions of the operators? Also, "ambiguous" seems like a rather odd name for what it does. I don't see how ambiguity has anything to do with it. That disconnect made it difficult at first for me to understand what it was. It's more like an "elementwise" or something.
I've been starting at the Ruby page, and I think I'm starting to understand it a little more: Suppose you have two "mostly" unknown values: x and y. Neither you, nor the computer at runtime, know what either of their values actually are. But, you *do* know a finite set of values that they *might* be: auto x = amb([1, 2]); // x is either 1 or 2, but I don't know which auto y = amb([3, 4, 5]); // y is either 3, 4 or 5, but I don't know which assert(x != 2); // Not guaranteed to be == 2 at this point assert(y != 4); // x*y must be one of these values, but I don't know which, it could be any of them: assert(x*y == amb([3, 4, 5, 6, 8, 10]); // Here's the *real* magic (psuedo-syntax): // For some bizarre reason, this means // that x*y must be == 8 (despite the !=) amb(if x*y != 8); // Since x*y has been determined to be 8, // the real values of x and y are now known and // completely unambiguous: assert(x == 2); assert(y == 4);
Sep 02 2010
== Quote from Nick Sabalausky (a a.a)'s articleInteresting thing, but devil's advocate: What would be the
that versus just having "for each element" versions of the
Well the obvious benefit is that you don't have to create all those extra version -- you get them all for free.Also, "ambiguous" seems like a rather odd name for what it does.
how ambiguity has anything to do with it. That disconnect made
at first for me to understand what it was. It's more like
or something.
I agree, it's a pretty bad name. I'd call it "all" or something.
Sep 03 2010
Philippe Sigaud <philippe.sigaud gmail.com> wrote:Hey, this question on SO makes for a good challenge: http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d The amb operator does this: amb([1, 2]) * amb([3, 4, 5]) == amb([3, 4, 5, 6, 8, 10]) amb(["hello", "world"]) ~ amb(["qwerty"]) == amb(["helloqwerty", "worldqwerty"]) amb(["hello", "world"]) ~ "qwerty" == amb(["helloqwerty", "worldqwerty"]) amb(["hello", "very long string"]).length = amb([5, 16]) (I find the guy examples much more comprehensible that the articles he links to) Are people interested in trying this?
Yes, very much so. However, Peter Alexander has misunderstood the ambiguous operator. The idea of amb is to return the combinatorial product of N ranges. if this sounds familiar, it is because it has been discussed at length here earlier, with me and Andrei being the prime contributors (see Combining infinite ranges and Huffman coding comparison). The solution has eluded me for a while, and I have shelved my efforts while doing other things. Perhaps now is the time to revisit it. Peter Alexander seems to have conflated the two concepts of the ambiguous operator and its require()-function. Basically, Amb should be a range of tuples, and you then filter it to retrieve the interesting parts. -- Simen
Sep 03 2010
== Quote from Simen kjaeraas (simen.kjaras gmail.com)'s articleYes, very much so. However, Peter Alexander has misunderstood the ambiguous operator.
Hey, I was just going by what the guy posted :) He mentioned nothing of tuples, and his examples certainly didn't show any tuples.
Sep 03 2010
On 09/05/2010 07:59 AM, Philippe Sigaud wrote:On Sun, Sep 5, 2010 at 12:00, Simen kjaeraas <simen.kjaras gmail.com <mailto:simen.kjaras gmail.com>> wrote: Philippe Sigaud <philippe.sigaud gmail.com <mailto:philippe.sigaud gmail.com>> wrote: I guess the D syntax would be auto x = amb([1,2,3]); auto y =amb([4,5,6]); x*y == 8; // forces desambiguation => the ambs explore the possibilities. assert(x == amb([2])); assert(y == amb([4])); There is only one value left, no more ambiguity. But what happens in the case where there is more than one value left? If I understand correctly the linked Ruby and Haskell versions, the search stops as soon as you find a possibility. But then, I'm no pro on this. That's one of the reasons I feel that doing the combination, then filtering it, is more correct. There is also the fact that the above syntax does not let you call arbitrary functions in the requirements, something filter does. The combining and filtering is interesting (in this case, it'd be like doing a list comprehension). But the real challenge in the SO question is the 'going back in time' part, which I have trouble to understand : how can you modify x and y through a multiplication and a comparison? I did a range comprehension maybe one year ago, which would be partially equivalent to the problem: auto solution = comp!("[a,b]", "a*b == 8")([1,2,3], [4,5,6]); solution is a range, in this case a one element range, containing only [2,4].
Here we need to have a crossProduct range, as we discussed in the thread "Combining infinite ranges". Then it's easy to combine it with filter: auto solutions = filter!"a*b == 8"(crossProduct([1,2,3], [4,5,6])); Andrei
Sep 05 2010
On 09/05/2010 09:30 AM, Philippe Sigaud wrote:On Sun, Sep 5, 2010 at 15:56, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org <mailto:SeeWebsiteForEmail erdani.org>> wrote: equivalent to the problem: auto solution = comp!("[a,b]", "a*b == 8")([1,2,3], [4,5,6]); solution is a range, in this case a one element range, containing only [2,4]. I did a range comprehension maybe one year ago, which would be partially Here we need to have a crossProduct range, as we discussed in the thread "Combining infinite ranges". Then it's easy to combine it with filter: auto solutions = filter!"a*b == 8"(crossProduct([1,2,3], [4,5,6])); Not exactly: crossProduct is a range, and the only element type that makes sense is Tuple!(A,B). Unless of course you're interested in adding binary predicates to filter, which would be understood as automatically opening tuples (and of course, would statically check the length of the tuple and the arity of the passed function). I can add this to Phobos.
Oh indeed. I think it's not onerous to require the client to write: auto solutions = filter!"a._0*a._0 == 8"(crossProduct([1,2,3], [4,5,6]));What you call crossProduct can be seen as zipWith!tuple(range, range2), which
Yah, per your follow-up post, it's a different problem. It's also a much more difficult one. I convinced myself crossProduct is impossible to implement if one input range and one infinite forward range are simultaneously present. It works with any number of infinite forward ranges, and also with other combinations. I couldn't formalize the exact requirements yet.If there is interest in this, I also suggest having a n-range version of map that takes a n-ary function and maps them in parallel. auto m = map!"a < b ? a : c"(range1, range2, range3); OK, I definitely need to take some time to assemble all this and propose it for a formal Phobos review. I'll bump it up higher in my TODO list. Philippe
Yah, definitely. Note that I have a functioning Zip in my upcoming commit to std.range. Andrei
Sep 05 2010
== Quote from Andrei AlexandrescuYah, per your follow-up post, it's a different problem. It's
more difficult one. I convinced myself crossProduct is
implement if one input range and one infinite forward range are simultaneously present. It works with any number of infinite
ranges, and also with other combinations. I couldn't formalize
requirements yet.
I must be missing something, because I don't understand how you could possibly take the cross product of any number of infinite ranges (other than to just return the range of (a[0], b[i]) for all (infinitely many) i in b). Note that I'm assuming you mean cartesian product, rather than cross product; I've never heard cross product used in the context of sets.
Sep 06 2010
On 09/06/2010 06:51 AM, Peter Alexander wrote:== Quote from Andrei AlexandrescuYah, per your follow-up post, it's a different problem. It's
more difficult one. I convinced myself crossProduct is
implement if one input range and one infinite forward range are simultaneously present. It works with any number of infinite
ranges, and also with other combinations. I couldn't formalize
requirements yet.
I must be missing something, because I don't understand how you could possibly take the cross product of any number of infinite ranges (other than to just return the range of (a[0], b[i]) for all (infinitely many) i in b). Note that I'm assuming you mean cartesian product, rather than cross product; I've never heard cross product used in the context of sets.
Yah, thanks for the correction. But probably ranges could be easier seen as vectors than as sets. We've discussed this before. Crosscartesian product of multiple infinite ranges can be easily done by applying Cantor's trick for proving that rational numbers are just as numerous than natural numbers. Google for "Cantor" with "site:digitalmars.com". Andrei
Sep 06 2010
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s articleWe've discussed this before. Crosscartesian product of multiple infinite ranges can be easily done by applying Cantor's trick for proving that rational numbers are just as numerous than natural numbers. Google for "Cantor" with "site:digitalmars.com". Andrei
Thanks. For some reason I had just assumed that we would have wanted to provide the product in lexicographic order, but Cantor's trick does seem like a solution to this problem.
Sep 06 2010
Peter:
I must be missing something, because I don't understand how you
could possibly take the cross product of any number of infinite
ranges (other than to just return the range of (a[0], b[i]) for
all (infinitely many) i in b).
The trick is to iterate diagonally. Me, I'll use tensorial product :p
Say you have: [0,1,2,...] x [0,1,2,...]
The tensorial product produces a range of ranges:
[[(0,0),(0,1),(0,2),(0,3),...
,[(1,0),(1,1),(1,2), ...
,[(2,0),(2,1),...
...
]
The standard cartesian product just iterates in the first line and will try to
explore an infinite row.
The trick is to iterate along the secondary diagonals, like this:
0 1 3 6
2 4 7
5 8
9
Which gives us: (0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3), ..
See the indices: sum of 0, then sum of 1, then sum of 2, ...
You never get stuck in an infinite line since these diagonal slices are finite.
Andrei:
We've discussed this before. Crosscartesian product of multiple infinite
ranges can be easily done by applying Cantor's trick for proving that rational
numbers are just as numerous than natural numbers. Google for "Cantor" with
"site:digitalmars.com".
Ok, I think I solved this particular problem, if only for infinite ranges.
It's in three parts:
1- A memorize(range) struct that slowly looks ahead in a range, store the result
in an internal array and so slowly transforms an input range into a
random-access
range. I tried this a few months ago, but got stuck in trying to propagate
properties (bidirectional, etc). Now it's just an input range. Much easier. It's
related to Zippers (in functional PL).
2- Generate the indices of sum = 0, then sum = 1, then sum = 2; etc.
3- Just take the corresponding indices in the input ranges.
example:
a = memorize(cycle([0,1,2,3,4])); // to make it infinite.
auto dp = diagonalProduct(a,a,a);
// -> (0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,0,2),(0,1,1), ...
entire source code attached (I hope it works). Now, I still have some problems
with finite ranges in the mix. Nothing crucial, but it's getting late.
Philippe
Sep 06 2010
On 09/06/2010 04:34 PM, Philippe Sigaud wrote:Which gives us: (0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3), .. See the indices: sum of 0, then sum of 1, then sum of 2, ... You never get stuck in an infinite line since these diagonal slices are finite.
I don't think iteration for constant index sums works with forward ranges - you need bidirectional ranges to go back in one while going forth in another. You need to only move forward in all ranges, or reset them to zero. It helps me a lot to think how I'd lay bricks to fill the first quadrant of an n-dimensional infinite space. If you tried the tensorial product, you'd lay a nice column of bricks, but you'd be busy at it forever because the column would have infinite "height". If you try your solution that has constant sums, then you are filling hypersimplexes of increasing size. That's certainly encouraging because it fills the space quite nicely, but again it requires bidirectional ranges. My solution is to fill hypercubes of increasing size from origin. One hypercube of size k is built by adding a layer of bricks on a hypercube of size k - 1. That can be done with forward iterators, and in fact is not all that difficult.Andrei: We've discussed this before. Crosscartesian product of multiple infinite ranges can be easily done by applying Cantor's trick for proving that rational numbers are just as numerous than natural numbers. Google for "Cantor" with "site:digitalmars.com". Ok, I think I solved this particular problem, if only for infinite ranges. It's in three parts: 1- A memorize(range) struct that slowly looks ahead in a range, store the result in an internal array and so slowly transforms an input range into a random-access range. I tried this a few months ago, but got stuck in trying to propagate properties (bidirectional, etc). Now it's just an input range. Much easier. It's related to Zippers (in functional PL). 2- Generate the indices of sum = 0, then sum = 1, then sum = 2; etc. 3- Just take the corresponding indices in the input ranges.
I don't think this is a good solution. Andrei
Sep 06 2010
I agree with Andrei here, building hypercubes makes more sense, and feels like it has more structure. It also has the nice property that, once you've seen a (n+1)th element of any range then you have already explored the entire product of the first n elements of every range, kind of like how the colex ordering works. But which way would you add the successive "shells"? Like this?: (00) (01 10 11) (02 12 20 21 22)... i.e. lex order? btw, what are some real-world uses of the cartesian product of infinite ranges? I can't think of any off the top of my head.
Sep 07 2010
On 09/07/2010 02:43 AM, Peter Alexander wrote:I agree with Andrei here, building hypercubes makes more sense, and feels like it has more structure. It also has the nice property that, once you've seen a (n+1)th element of any range then you have already explored the entire product of the first n elements of every range, kind of like how the colex ordering works. But which way would you add the successive "shells"? Like this?: (00) (01 10 11) (02 12 20 21 22)... i.e. lex order?
The algorithm builds one hyperplane at a time. At level k, there are n hyperplanes to build, each of which keeps exactly one range positioned on the kth element, and all others iterate from their first up to their kth element. Whenever you reached the corner of the hypercube (all ranges are at the kth position), you start building the next hyperplane. When all other hyperplanes are built, you popFront() the first range, reset all others, and start building the next shell.btw, what are some real-world uses of the cartesian product of infinite ranges? I can't think of any off the top of my head.
It's great for various solution-searching algorithms, like the example given (lazily generate solutions to the equation x * y = 8). Even for finite ranges of moderate size, exploring two iota()s in the naive order (keep one fixed and exhaust all others) most often takes a long time to find anything interesting. That's why I think finding a solid method to iterate the cartesian product is important even for finite ranges. Andrei
Sep 07 2010
Denis Koroskin:The code above should print: state saved state restored (not tested)
On Windows, dmd 2.048, this code: import std.c.stdio: puts; version (Windows) { alias int[16] jmp_buf; extern (C) extern { int setjmp(ref jmp_buf env); void longjmp(ref jmp_buf env, int value); } } struct State { int save() { return setjmp(buf); } void restore(int status) { assert(status != 0); longjmp(buf, status); } private jmp_buf buf; } void main() { State state; int result = state.save(); if (result == 0) { // first time here puts("state saved"); state.restore(1); } else { assert(result == 1); puts("state restored"); } } Gives an Access Violation after printing state saved. Bye, bearophile
Sep 05 2010
Denis Koroskin:Turn main into an "extern(C) int main()" and it works.
This version: import std.c.stdio: puts; version (Windows) { alias int[16] jmp_buf; extern (C) extern { int setjmp(ref jmp_buf env); void longjmp(ref jmp_buf env, int value); } } struct State { int save() { return setjmp(buf); } void restore(int status) { assert(status != 0); longjmp(buf, status); } private jmp_buf buf; } extern(C) int main() { State state; int result = state.save(); if (result == 0) { // first time here puts("state saved"); state.restore(1); } else { assert(result == 1); puts("state restored"); } return 0; } Gives link errors: test.obj(test) Error 42: Symbol Undefined __d_assertm test.obj(test) Error 42: Symbol Undefined __d_assert_msg Bye, bearophile
Sep 05 2010
On 02/09/10 05:38, Philippe Sigaud wrote:Hey, this question on SO makes for a good challenge: http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d
It's great to see someone doing the first D discussion topic with the [challenge] annotation. Bearophile, if you are reading this perhaps you might like to repost some of you previous "challenges" which have not received much attention with the [challenge] annotation in the subject line. I hope this idea of annotating ng discussion topics with their genre, say [challenge] or [trick], or perhaps [typesystem] or whatever takes on as much as [OT] threads seem to :-) Cheers Justin Johansson
Sep 03 2010
Justin Johansson:Bearophile, if you are reading this perhaps you might like to repost some of you previous "challenges" which have not received much attention with the [challenge] annotation in the subject line.
See: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=116505 Bye, bearpophile
Sep 03 2010
bearophile wrote:Justin Johansson:Bearophile, if you are reading this perhaps you might like to repost some of you previous "challenges" which have not received much attention with the [challenge] annotation in the subject line.
See: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=116505 Bye, bearpophile
That's not a very useful problem, because the timing depends entirely on BigInt, which is completely unoptimised for small values.
Sep 03 2010
== Quote from Don (nospam nospam.com)'s articleThat's not a very useful problem, because the timing depends entirely on BigInt, which is completely unoptimised for small values.
True, but it would be nice to get it as concise as Haskell's. In an ideal world, we'd simply write it as: auto H() { return chain([BigInt(1)], setIntersection(map!"2*a"(H()), map!"3*a"(H()), map!"5*a"(H()))); } BigInt hamming(int limit) { return H().at(limit); } But the unfortunately, due to D's type system, you cannot have recursive types (H's type depends on its own type). You should be able to get around this by introducing a "abstract range wrapper". I'll see what I can come up with.
Sep 03 2010
Don:That's not a very useful problem, because the timing depends entirely on BigInt, which is completely unoptimised for small values.
You are usually right, but this time what you say is useless. There are other means to judge how good a program is, beside running time: - Total line count of the program; - Max amount of memory used. The Haskell version of the program is quite fast, very short, and it's lazy so it uses very low memory. The "Alternate version using "Cyclic Iterators"" Python version invented by the great Raymond Hettinger too is lazy and uses very low memory. On the other hand, that D version, that I have translated from the Java code, is eager so it uses a lot of memory, is slow (mostly because of the bigint implementation, I agree), and its source is many lines long. So D must do better along one or more than one of those axis. This huge thread shows that this is a very interesting problem, and solving it well is important for a language like that D that wants to support lazy iterables a lot in its standard library, and wants to be able to express code at a high level too (this means short programs): http://lambda-the-ultimate.org/node/608 Bye, bearophile
Sep 03 2010
bearophile wrote:Don:That's not a very useful problem, because the timing depends entirely on BigInt, which is completely unoptimised for small values.
You are usually right, but this time what you say is useless. There are other means to judge how good a program is, beside running time: - Total line count of the program; - Max amount of memory used.
Well, I would hate for somebody to waste their time trying to optimise that problem either for speed or memory consumption, when both are limited by a fairly simple, short-term library issue. Lines of code, sure.
Sep 03 2010
Don:Well, I would hate for somebody to waste their time trying to optimise that problem either for speed or memory consumption, when both are limited by a fairly simple, short-term library issue.
What is the short-term Phobos issue that limits the memory usage? In the current Phobos2 I have not found any easy-to-use mean to transform that eager D version into a lazy version that uses about 1/10 of the memory it currently uses (s in the second Python version). Bye, bearophile
Sep 03 2010
Philippe Sigaud:It's crystal clear & short (but we should aim for J! :-), but being lazy I don't see how it can use less memory than a strict version of the same algo. Got to store all those thunks somewhere.<
I have appreciated how the Haskell version allows me to generate a sequence lazily in a recursive way, with a compact syntax and efficiently. But I don't know Haskell, so it's easy for what I say about Haskell programs to be false :-)What did you use to compare them? (out of curiosity, not attack).< I used GHCi, and got 8.8s for the millionth Hamming number, using ~450 Mo of RAM, according to GHCi itself (:set +s, :set +t). But I'm no pro in optimizing Haskell compilation.
For the Python and D programs I have used woerking memory & commit on Windows, for the Haskell version I have used Ideone: http://ideone.com/wH1YU It computes the result (ghc-6.8.2) in 0.93s using only 8.7 MB of memory.For my own D version, that is quite near the Rosetta Code version, I get 3.7s, 100 Mo of RAM. (-O -release -inline) Using the RC code (your own, translated from Java, right?), I get the same. Same result, same time, same memory consumption. Yeah, my code is not wrong :-)
On my very slow PC using DMD the D version requires about 2.7s and about max 92 MB of memory. The second Python version (the one by Hettinger) takes about 4.95s and less than 4.5 MB of memory. (The third Python version, that uses the eager array and Psyco is faster.) Are you able to write a short D version similar to the second Python version? (I have created one, but it's not as short as the second Python version, and it takes something like 4 seconds or more). Bye, bearophile
Sep 04 2010
Philippe Sigaud:Less than 1s is impressive.<
To compare, on the Ideone site the third Python version (Python 2.6.4 + Psyco) takes 1.46s and max 88 MB (this is where what Don has said about D bignums is important): http://ideone.com/5NvzRMaybe with lazy int delegates ?<
Right, but the devil is in details. Bye, bearophile
Sep 05 2010
--001636c5b4b85a104a048f5ff411 Content-Type: text/plain; charset=ISO-8859-1 On Fri, Sep 3, 2010 at 19:51, Peter Alexander <peter.alexander.au gmail.com>wrote:== Quote from Simen kjaeraas (simen.kjaras gmail.com)'s articleYes, very much so. However, Peter Alexander has misunderstood the ambiguous operator.
Hey, I was just going by what the guy posted :) He mentioned nothing of tuples, and his examples certainly didn't show any tuples.
Yes, I agree with Peter there. As I said, I personally prefer the examples in the SO OP than the Haskell/Ruby code, if only because the example are easily understood and I find this range combinator useful in some circumstances. What we have here in D is a bit like the List monad in Haskell: a way to represent a bunch of possible values for a computation. If a can 2 or 4 or 6, and b can be 0 or 1 or 2, it makes sense for a*b to among 0,2,4,6,8,12. So thanks, Peter. But does the code compile for you? As I said, here with 2.048, it doesn't. Now, the 'real'/intriguing/mind-bending amb operator (from the 60's) does like the Haskell implementation linked in SO does: backtracking on the results to avoid some condition. If someone is up to the challenge of implementing it in D, great! Maybe with closures? I never really thought about it. I guess the D syntax would be auto x = amb([1,2,3]); auto y =amb([4,5,6]); x*y == 8; // forces desambiguation => the ambs explore the possibilities. assert(x == amb([2])); assert(y == amb([4])); There is only one value left, no more ambiguity. Maybe in this case an 'alias possibilities[0] this' could do the trick: assert(x == 2); assert(y == 4); Can we do alias someArray[0] this; ? Philippe Philippe --001636c5b4b85a104a048f5ff411 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">On Fri, Sep 3, 2010 at 19:51, Peter Alex= ander <span dir=3D"ltr"><<a href=3D"http://peter.alexander.au">peter.ale= xander.au</a> <a href=3D"http://gmail.com">gmail.com</a>></span> wrote:<= br><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; bo= rder-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> =3D=3D Quote from Simen kjaeraas (<a href=3D"mailto:simen.kjaras gmail.com"=simen.kjaras gmail.com</a>)'s article<br>
nderstood the<br> > ambiguous operator.<br> <br> </div>Hey, I was just going by what the guy posted :) =A0He mentioned<br> nothing of tuples, and his examples certainly didn't show any<br> tuples.<br> </blockquote></div><br>Yes, I agree with Peter there. As I said, I personal= ly prefer the examples in the SO OP than the Haskell/Ruby code, if only bec= ause the example are easily understood and I find this range combinator use= ful in some circumstances.<br> What we have here in D is a bit like the List monad in Haskell: a way to re= present a bunch of possible values for a computation. If a can 2 or 4 or 6,= and b can be 0 or 1 or 2, it makes sense for a*b to among 0,2,4,6,8,12.<br=
th 2.048, it doesn't.<br> <br> Now, the 'real'/intriguing/mind-bending amb operator (from the 60&#= 39;s)=20 does like the Haskell implementation linked in SO does: backtracking on the= results to avoid some condition. If someone is up to the challenge of impl= ementing it in D, great! Maybe with closures? I never really thought about = it.<br> <br>I guess the D syntax would be <br>auto x =3D amb([1,2,3]);<br>auto y = =3Damb([4,5,6]);<br>x*y =3D=3D 8; // forces desambiguation =3D> the ambs= explore the possibilities.<br>assert(x =3D=3D amb([2]));<br>assert(y =3D= =3D amb([4]));<br> <br>There is only one value left, no more ambiguity. Maybe in this case an = 'alias possibilities[0] this' could do the trick:<br><br>assert(x = =3D=3D 2);<br>assert(y =3D=3D 4);<br><br>Can we do alias someArray[0] this;= ?<br> <br><br>Philippe<br><br><br><br><br>Philippe<br><br> --001636c5b4b85a104a048f5ff411--
Sep 03 2010
--0016e6d58fd649fda6048f5ffd24 Content-Type: text/plain; charset=ISO-8859-1 On Fri, Sep 3, 2010 at 16:30, Justin Johansson <no spam.com> wrote:On 02/09/10 05:38, Philippe Sigaud wrote:Hey, this question on SO makes for a good challenge: http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d
It's great to see someone doing the first D discussion topic with the [challenge] annotation.
This was just for fun, because combining ranges is always fun, and in this case, it's a good example of operator overloading. I have a more interesting / less academic challenge in mind: make idmd, an interactive,REPL-like, D "interpreter". Philippe --0016e6d58fd649fda6048f5ffd24 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">On Fri, Sep 3, 2010 at 16:30, Justin Joh= ansson <span dir=3D"ltr"><<a href=3D"mailto:no spam.com">no spam.com</a>= ></span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin: 0p= t 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1= ex;"> <div class=3D"im">On 02/09/10 05:38, Philippe Sigaud wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> Hey, this question on SO makes for a good challenge:<br> <br> <a href=3D"http://stackoverflow.com/questions/3608834/is-it-possible-to-gen= erically-implement-the-amb-operator-in-d" target=3D"_blank">http://stackove= rflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb= -operator-in-d</a><br> </blockquote> <br></div> It's great to see someone doing the first D discussion topic<br> with the [challenge] annotation.<font color=3D"#888888"><br></font></blockq= uote><div><br>This was just for fun, because combining ranges is always fun= , and in this case, it's a good example of operator overloading.<br> <br>I have a more interesting / less academic challenge in mind: make idmd,= an interactive,REPL-like, D "interpreter".<br><br><br>Philippe <= br></div></div><br> --0016e6d58fd649fda6048f5ffd24--
Sep 03 2010
Peter Alexander <peter.alexander.au gmail.com> wrote:== Quote from Simen kjaeraas (simen.kjaras gmail.com)'s articleYes, very much so. However, Peter Alexander has misunderstood the ambiguous operator.
Hey, I was just going by what the guy posted :) He mentioned nothing of tuples, and his examples certainly didn't show any tuples.
Sorry, yes. Copied the wrong name off of the OP on SO. Should have said chrisdew, not Peter Alexander. -- Simen
Sep 03 2010
Philippe Sigaud <philippe.sigaud gmail.com> wrote:Now, the 'real'/intriguing/mind-bending amb operator (from the 60's) does like the Haskell implementation linked in SO does: backtracking on the results to avoid some condition. If someone is up to the challenge of implementing it in D, great! Maybe with closures? I never really thought about it. I guess the D syntax would be auto x = amb([1,2,3]); auto y =amb([4,5,6]); x*y == 8; // forces desambiguation => the ambs explore the possibilities.
I believe this will only work with arrays as input. Either that, or I need a way to make this work: struct Foo( R ) if ( isForwardRange!R ) { bool delegate( ElementType!R ) bar; Filter!( bar, R ) range; } Or, well, something like it. I need a static type for a Filter that delegates to a struct member, in this case bar.assert(x == amb([2])); assert(y == amb([4])); There is only one value left, no more ambiguity. Maybe in this case an 'alias possibilities[0] this' could do the trick: assert(x == 2); assert(y == 4); Can we do alias someArray[0] this; ?
For a simple assert like that, overloading opEquals ought to do the trick, no? -- Simen
Sep 03 2010
Simen kjaeraas <simen.kjaras gmail.com> wrote:I believe this will only work with arrays as input. Either that, or I need a way to make this work: struct Foo( R ) if ( isForwardRange!R ) { bool delegate( ElementType!R ) bar; Filter!( bar, R ) range; } Or, well, something like it. I need a static type for a Filter that delegates to a struct member, in this case bar.
I would have thought this'd work, but apparently I'm wrong: module foo; import std.stdio; import std.algorithm; import std.range; struct Foo( R ) if ( isForwardRange!R ) { R range; void delegate( ) _popFront; bool delegate( ) _empty; ElementType!R delegate( ) _front; this( R rng ) { range = rng; _popFront = { range.popFront( ); }; _empty = { return range.empty; }; _front = { return range.front; }; } void attempt( bool delegate( ElementType!R ) dg ) { auto rng = filter!dg( range ); _popFront = { rng.popFront( ); }; _empty = { return rng.empty; }; _front = { return rng.front; }; } void popFront( ) { _popFront( ); } property bool empty( ) { return _empty( ); } property ElementType!R front( ) { return _front( ); } } Foo!R bar( R )( R rng ) if ( isForwardRange!R ) { return Foo!R( rng ); } void main() { auto b = bar( [1,2,3] ); foreach ( e; b ) { writeln( e ); } } Output: 1 object.Error: Access Violation -- Simen
Sep 03 2010
--001636d34c2979fbc7048f699214 Content-Type: text/plain; charset=ISO-8859-1 On Sat, Sep 4, 2010 at 01:40, Simen kjaeraas <simen.kjaras gmail.com> wrote:Simen kjaeraas <simen.kjaras gmail.com> wrote: I believe this will only work with arrays as input. Either that, or I needa way to make this work: struct Foo( R ) if ( isForwardRange!R ) { bool delegate( ElementType!R ) bar; Filter!( bar, R ) range; } Or, well, something like it. I need a static type for a Filter that delegates to a struct member, in this case bar.
struct DynamicFilter(R) if (isInputRange!R) { R range; bool delegate(ElementType!R) predicate; bool set; this(R _range) { range = _range; } this(R _range, bool delegate(ElementType!R) _predicate) { range = _range; predicate = _predicate; set = true; popFront(); } void setPredicate(bool delegate(ElementType!R) _predicate) { predicate = _predicate; set = true; popFront();} ElementType!R front() { if (set) { return range.front();} else { throw new Exception("Calling DynamicFilter with an unset predicate.");};} bool empty() { if (set) {return range.empty;} else { throw new Exception("Calling DynamicFilter with an unset predicate.");};} void popFront() { if (set) { while( !range.empty && !predicate(range.front)) { range.popFront(); } } else { throw new Exception("Calling DynamicFilter with an unset predicate."); } } } //DynamicFilter!(R) dynamicFilter(R)(R range) //{ // return DynamicFilter!R(range); //} DynamicFilter!(R) dynamicFilter(R,E)(R range, bool delegate(E) pred = null) if ((isInputRange!R) && is(ElementType!R == E)) { if (pred is null) return DynamicFilter!(R)(range); else return DynamicFilter!R(range, pred); } void main() { auto f = dynamicFilter([0,1,2,3], (int i) { return i%2 == 0;}); writeln(f.front); // 0 f.setPredicate((int i) { return i%2 == 1;}); writeln(f.front); // 1 } Note that in this version, the filtered range always advances. When you change filter, it continues to consume elements from the current point. For backtracking, maybe you need a forward range input, a saved version of this input, and have setPredicate rewind the inner range to the saved version. Philippe --001636d34c2979fbc7048f699214 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">On Sat, Sep 4, 2010 at 01:40, Simen kjae= raas <span dir=3D"ltr"><<a href=3D"mailto:simen.kjaras gmail.com">simen.= kjaras gmail.com</a>></span> wrote:<br><blockquote class=3D"gmail_quote"= style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 2= 04); padding-left: 1ex;"> <div>Simen kjaeraas <<a href=3D"mailto:simen.kjaras gmail.com" target=3D= "_blank">simen.kjaras gmail.com</a>> wrote:<br> <br> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> I believe this will only work with arrays as input. Either that, or I need<= br> a way to make this work:<br> <br> struct Foo( R ) if ( isForwardRange!R ) {<br> =A0 =A0 bool delegate( ElementType!R ) bar;<br> =A0 =A0 Filter!( bar, R ) range;<br> }<br> <br> Or, well, something like it. I need a static type for a Filter that<br> delegates to a struct member, in this case bar.<br> </blockquote> </div></blockquote><div><br>Maybe with a dynamic filter?<br><br>struct Dyna= micFilter(R) if (isInputRange!R)<br>{<br>=A0=A0=A0 R range;<br>=A0=A0=A0 bo= ol delegate(ElementType!R) predicate;<br>=A0=A0=A0 bool set;<br>=A0=A0=A0 t= his(R _range) { range =3D _range; }<br> =A0=A0=A0 this(R _range, bool delegate(ElementType!R) _predicate) { range = =3D _range; predicate =3D _predicate; set =3D true; popFront(); }<br>=A0=A0= =A0 void setPredicate(bool delegate(ElementType!R) _predicate) { predicate = =3D _predicate; set =3D true; popFront();}<br> <br>=A0=A0=A0 ElementType!R front() { if (set) { return range.front();} els= e { throw new Exception("Calling DynamicFilter with an unset predicate= .");};}<br>=A0=A0=A0 bool empty() { if (set) {return range.empty;} els= e { throw new Exception("Calling DynamicFilter with an unset predicate= .");};}<br> =A0=A0=A0 void popFront()<br>=A0=A0=A0 {<br>=A0=A0=A0=A0=A0=A0=A0 if (set)<= br>=A0=A0=A0=A0=A0=A0=A0 {<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 while( !ran= ge.empty && !predicate(range.front))<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0 {<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 range.popFront();= <br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 }<br>=A0=A0=A0=A0=A0=A0=A0 }<br>=A0= =A0=A0=A0=A0=A0=A0 else<br> =A0=A0=A0=A0=A0=A0=A0 {<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 throw new Exce= ption("Calling DynamicFilter with an unset predicate.");<br>=A0= =A0=A0=A0=A0=A0=A0 }<br>=A0=A0=A0 }<br>}<br><br>//DynamicFilter!(R) dynamic= Filter(R)(R range)<br>//{<br>//=A0=A0=A0 return DynamicFilter!R(range);<br> //}<br><br>DynamicFilter!(R) dynamicFilter(R,E)(R range, bool delegate(E) p= red =3D null) if ((isInputRange!R) && is(ElementType!R =3D=3D E))<b= r>{<br>=A0=A0=A0 if (pred is null)<br>=A0=A0=A0=A0=A0=A0=A0 return DynamicF= ilter!(R)(range);<br>=A0=A0=A0 else<br> =A0=A0=A0=A0=A0=A0=A0 return DynamicFilter!R(range, pred);<br>}<br><br>void= main()<br>{<br>=A0=A0=A0 auto f =3D dynamicFilter([0,1,2,3], (int i) { ret= urn i%2 =3D=3D 0;});<br>=A0=A0=A0 writeln(f.front); // 0<br>=A0=A0=A0 f.set= Predicate((int i) { return i%2 =3D=3D 1;});<br> =A0=A0=A0 writeln(f.front); // 1<br>}<br><br><br>Note that in this version,= the filtered range always advances. When you change filter, it continues t= o consume elements from the current point. For backtracking, maybe you need= a forward range input, a saved version of this input, and have setPredicat= e rewind the inner range to the saved version.<br> <br><br>Philippe<br></div></div> --001636d34c2979fbc7048f699214--
Sep 03 2010
--0016e6dab73fd0eef4048f75cd3d Content-Type: text/plain; charset=ISO-8859-1 On Fri, Sep 3, 2010 at 21:43, bearophile <bearophileHUGS lycos.com> wrote:Don:That's not a very useful problem, because the timing depends entirely on BigInt, which is completely unoptimised for small values.
You are usually right, but this time what you say is useless. There are other means to judge how good a program is, beside running time: - Total line count of the program; - Max amount of memory used. The Haskell version of the program is quite fast, very short, and it's lazy so it uses very low memory.
It's crystal clear & short (but we should aim for J! :-), but being lazy I don't see how it can use less memory than a strict version of the same algo. Got to store all those thunks somewhere.The "Alternate version using "Cyclic Iterators"" Python version invented by the great Raymond Hettinger too is lazy and uses very low memory. On the other hand, that D version, that I have translated from the Java code, is eager so it uses a lot of memory, is slow (mostly because of the bigint implementation, I agree), and its source is many lines long. So D must do better along one or more than one of those axis.
What did you use to compare them? (out of curiosity, not attack). I used GHCi, and got 8.8s for the millionth Hamming number, using ~450 Mo of RAM, according to GHCi itself (:set +s, :set +t). But I'm no pro in optimizing Haskell compilation. For my own D version, that is quite near the Rosetta Code version, I get 3.7s, 100 Mo of RAM. (-O -release -inline) Using the RC code (your own, translated from Java, right?), I get the same. Same result, same time, same memory consumption. Yeah, my code is not wrong :-) So, at least naively like this for me, D is more than twice as fast as Haskell and uses about 80% less memory. Of course, GHC caches results, so the second time I ask for the millionth Hamming number, I get it almost instantaneously. Nifty, that! Philippe --0016e6dab73fd0eef4048f75cd3d Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">On Fri, Sep 3, 2010 at 21:43, bearophile= <span dir=3D"ltr"><<a href=3D"mailto:bearophileHUGS lycos.com">bearophi= leHUGS lycos.com</a>></span> wrote:<br><blockquote class=3D"gmail_quote"= style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 2= 04); padding-left: 1ex;"> Don:<br> <div class=3D"im">> That's not a very useful problem, because the ti= ming depends entirely on<br> > BigInt, which is completely unoptimised for small values.<br> <br> </div>You are usually right, but this time what you say is useless. There a= re other means to judge how good a program is, beside running time:<br> - Total line count of the program;<br> - Max amount of memory used.<br> <br> The Haskell version of the program is quite fast, very short, and it's = lazy so it uses very low memory.</blockquote><div><br>It's crystal clea= r & short (but we should aim for J! :-), but being lazy I don't see= how it can use less memory than a strict version of the same algo. Got to = store all those thunks somewhere.<br> =A0</div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8= ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> The &qu= ot;Alternate version using "Cyclic Iterators"" Python versio= n invented by the great Raymond Hettinger too is lazy and uses very low mem= ory. On the other hand, that D version, that I have translated from the Jav= a code, is eager so it uses a lot of memory, is slow (mostly because of the= bigint implementation, I agree), and its source is many lines long. So D m= ust do better along one or more than one of those axis.<font color=3D"#8888= 88"><br> </font></blockquote><div><br>What did you use to compare them? (out of curi= osity, not attack).<br>I used GHCi, and got 8.8s for the millionth Hamming = number, using ~450 Mo of RAM, according to GHCi itself (:set +s, :set +t). = But I'm no pro in optimizing Haskell compilation.<br> For my own D version, that is quite near the Rosetta Code version, I get 3.= 7s, 100 Mo of RAM. (-O -release -inline)<br>Using the RC code (your own, tr= anslated from Java, right?), I get the same. Same result, same time, same m= emory consumption. Yeah, my code is not wrong :-)<br> So, at least naively like this for me, D is more than twice as fast as Hask= ell and uses about 80% less memory.<br><br>Of course, GHC caches results, s= o the second time I ask for the millionth Hamming number, I get it almost i= nstantaneously. Nifty, that!<br> <br><br>Philippe<br></div></div><br> --0016e6dab73fd0eef4048f75cd3d--
Sep 04 2010
Philippe Sigaud <philippe.sigaud gmail.com> wrote:I guess the D syntax would be auto x = amb([1,2,3]); auto y =amb([4,5,6]); x*y == 8; // forces desambiguation => the ambs explore the possibilities. assert(x == amb([2])); assert(y == amb([4])); There is only one value left, no more ambiguity.
But what happens in the case where there is more than one value left? That's one of the reasons I feel that doing the combination, then filtering it, is more correct. There is also the fact that the above syntax does not let you call arbitrary functions in the requirements, something filter does.Maybe in this case an 'alias possibilities[0] this' could do the trick: assert(x == 2); assert(y == 4); Can we do alias someArray[0] this; ?
Well, we can do this: struct foo( R ) { R range; ref ElementType!R getFront( ) { return range.front; } alias getFront this; } -- Simen
Sep 05 2010
--0016e6d56670980920048f8263a7 Content-Type: text/plain; charset=ISO-8859-1 On Sat, Sep 4, 2010 at 23:55, bearophile <bearophileHUGS lycos.com> wrote:It computes the result (ghc-6.8.2) in 0.93s using only 8.7 MB of memory.
OK, so that may the difference between GHCi and GHC proper. Less than 1s is impressive. I see I have GHC 6.12.3 on my system. I may give this code a try one day. I tend to do most (if not all) of my Haskell 'dips' with GHCi.For my own D version, that is quite near the Rosetta Code version, I get 3.7s, 100 Mo of RAM. (-O -release -inline) Using the RC code (your own, translated from Java, right?), I get the
Same result, same time, same memory consumption. Yeah, my code is not
On my very slow PC using DMD the D version requires about 2.7s and about max 92 MB of memory.
Maybe my PC is even slower :-)The second Python version (the one by Hettinger) takes about 4.95s and less than 4.5 MB of memory. (The third Python version, that uses the eager array and Psyco is faster.) Are you able to write a short D version similar to the second Python version? (I have created one, but it's not as short as the second Python version, and it takes something like 4 seconds or more).
Funnily, this second Python version was the only one I knew. So no, I'm not able to do the deferred output in D. That's were the trick is anyway, to have the solution recurse on a 'younger' version of itself. Maybe with lazy int delegates ? Philippe --0016e6d56670980920048f8263a7 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Sat, Sep 4, 2010 at 23:55, bearophile <span d= ir=3D"ltr"><<a href=3D"mailto:bearophileHUGS lycos.com">bearophileHUGS l= ycos.com</a>></span> wrote:<br><blockquote class=3D"gmail_quote" style= =3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); p= adding-left: 1ex;"> <br> It computes the result (ghc-6.8.2) in 0.93s using only 8.7 MB of memory.<br=</blockquote><div><br>OK, so that may the difference between GHCi and GHC =
. I may give this code a try one day. I tend to do most (if not all) of my = Haskell 'dips' with GHCi.<br> <br>=A0</div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt= 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> <div class=3D"im"> <br> > For my own D version, that is quite near the Rosetta Code version, I g= et<br> > 3.7s, 100 Mo of RAM. (-O -release -inline)<br> > Using the RC code (your own, translated from Java, right?), I get the = same.<br> > Same result, same time, same memory consumption. Yeah, my code is not = wrong :-)<br> <br> </div>On my very slow PC using DMD the D version requires about 2.7s and ab= out max 92 MB of memory.<br></blockquote><div><br>Maybe my PC is even slowe= r :-)<br>=A0</div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0p= t 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"=
<br> The second Python version (the one by Hettinger) takes about 4.95s and less= than 4.5 MB of memory.<br> (The third Python version, that uses the eager array and Psyco is faster.)<= br> <br> Are you able to write a short D version similar to the second Python versio= n? (I have created one, but it's not as short as the second Python vers= ion, and it takes something like 4 seconds or more).<br></blockquote><div> <br>Funnily, this second Python version was the only one I knew. So no, I&#= 39;m not able to do the deferred output in D. That's were the trick is = anyway, to have the solution recurse on a 'younger' version of itse= lf. Maybe with lazy int delegates ?<br> =A0<br><br>Philippe<br></div></div> --0016e6d56670980920048f8263a7--
Sep 05 2010
--001485f85a9425064d048f82bcd0 Content-Type: text/plain; charset=ISO-8859-1 On Sun, Sep 5, 2010 at 12:00, Simen kjaeraas <simen.kjaras gmail.com> wrote:Philippe Sigaud <philippe.sigaud gmail.com> wrote: I guess the D syntax would beauto x = amb([1,2,3]); auto y =amb([4,5,6]); x*y == 8; // forces desambiguation => the ambs explore the possibilities. assert(x == amb([2])); assert(y == amb([4])); There is only one value left, no more ambiguity.
But what happens in the case where there is more than one value left?
If I understand correctly the linked Ruby and Haskell versions, the search stops as soon as you find a possibility. But then, I'm no pro on this.That's one of the reasons I feel that doing the combination, then filtering it, is more correct. There is also the fact that the above syntax does not let you call arbitrary functions in the requirements, something filter does.
The combining and filtering is interesting (in this case, it'd be like doing a list comprehension). But the real challenge in the SO question is the 'going back in time' part, which I have trouble to understand : how can you modify x and y through a multiplication and a comparison? I did a range comprehension maybe one year ago, which would be partially equivalent to the problem: auto solution = comp!("[a,b]", "a*b == 8")([1,2,3], [4,5,6]); solution is a range, in this case a one element range, containing only [2,4]. PhilippeMaybe in this case an'alias possibilities[0] this' could do the trick: assert(x == 2); assert(y == 4); Can we do alias someArray[0] this; ?
Well, we can do this: struct foo( R ) { R range; ref ElementType!R getFront( ) { return range.front; } alias getFront this; } -- Simen
--001485f85a9425064d048f82bcd0 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">On Sun, Sep 5, 2010 at 12:00, Simen kjae= raas <span dir=3D"ltr"><<a href=3D"mailto:simen.kjaras gmail.com">simen.= kjaras gmail.com</a>></span> wrote:<br><blockquote class=3D"gmail_quote"= style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 2= 04); padding-left: 1ex;"> <div class=3D"im">Philippe Sigaud <<a href=3D"mailto:philippe.sigaud gma= il.com" target=3D"_blank">philippe.sigaud gmail.com</a>> wrote:<br> <br> </div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex;= border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class= =3D"im"> I guess the D syntax would be<br> auto x =3D amb([1,2,3]);<br> auto y =3Damb([4,5,6]);<br> x*y =3D=3D 8; // forces desambiguation =3D> the ambs explore the possibi= lities.<br></div><div class=3D"im"> assert(x =3D=3D amb([2]));<br> assert(y =3D=3D amb([4]));<br> <br> There is only one value left, no more ambiguity.<br> </div></blockquote> <br> But what happens in the case where there is more than one value left?<br></= blockquote><div><br>If I understand correctly the linked Ruby and Haskell v= ersions, the search stops as soon as you find a possibility. But then, I= 9;m no pro on this.<br> <br><br>=A0</div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt= 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> That's one of the reasons I feel that doing the combination, then<br> filtering it, is more correct. There is also the fact that the above<br> syntax does not let you call arbitrary functions in the requirements,<br> something filter does.</blockquote><div><br>The combining and filtering is = interesting (in this case, it'd be like doing a=A0 list comprehension).= <br>But the real challenge in the SO question is the 'going back in ti= me' part, which I have trouble to understand : how can you modify x and= y through a multiplication and a comparison?<br> <br>I did a range comprehension maybe one year ago, which would be partiall= y equivalent to the problem:<br><br>auto solution =3D comp!("[a,b]&quo= t;, "a*b =3D=3D 8")([1,2,3], [4,5,6]);<br><br>solution is a range= , in this case a one element range, containing only [2,4].<br> <br><br>Philippe<br><br>=A0</div><blockquote class=3D"gmail_quote" style=3D= "margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padd= ing-left: 1ex;"><div class=3D"im"><br> <br> <br> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> Maybe in this case an<br> 'alias possibilities[0] this' could do the trick:<br> <br> assert(x =3D=3D 2);<br> assert(y =3D=3D 4);<br> <br> Can we do alias someArray[0] this; ?<br> </blockquote> <br></div> Well, we can do this:<br> <br> struct foo( R ) {<br> =A0 =A0R range;<br> <br> =A0 =A0ref ElementType!R getFront( ) {<br> =A0 =A0 =A0 =A0return range.front;<br> =A0 =A0}<br> <br> =A0 =A0alias getFront this;<br> }<br> <br> -- <br><font color=3D"#888888"> Simen<br> </font></blockquote></div><br> --001485f85a9425064d048f82bcd0--
Sep 05 2010
On Sun, 05 Sep 2010 16:59:31 +0400, Philippe Sigaud <philippe.sigaud gmail.com> wrote:But the real challenge in the SO question is the 'going back in time' part, which I have trouble to understand : how can you modify x and y through a multiplication and a comparison?
It can be done using setjmp/longjmp, see C implementation for an example: http://homepage.mac.com/sigfpe/Computing/continuations.html
Sep 05 2010
--000325559fded551bb048f83eccd Content-Type: text/plain; charset=ISO-8859-1 2010/9/5 Denis Koroskin <2korden gmail.com>On Sun, 05 Sep 2010 16:59:31 +0400, Philippe Sigaud < philippe.sigaud gmail.com> wrote: But the real challenge in the SO question is the 'going back in time'part, which I have trouble to understand : how can you modify x and y through a multiplication and a comparison?
http://homepage.mac.com/sigfpe/Computing/continuations.html
How can we access setjmp/longjmp in D? Anyway, I'm a bit nervous with using such a raw statement. An oh-so-slightly wrapped equivalent for D would be better. Philippe --000325559fded551bb048f83eccd Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">2010/9/5 Denis Koroskin <span dir=3D"ltr= "><<a href=3D"mailto:2korden gmail.com">2korden gmail.com</a>></span>= <br><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; b= order-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> <div class=3D"im">On Sun, 05 Sep 2010 16:59:31 +0400, Philippe Sigaud <<= a href=3D"mailto:philippe.sigaud gmail.com" target=3D"_blank">philippe.siga= ud gmail.com</a>> wrote:<br> <br> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> But the real challenge in the SO question is the 'going back in time= 9; part,<br> which I have trouble to understand : how can you modify x and y through a<b= r> multiplication and a comparison?<br> <br> </blockquote> <br></div> It can be done using setjmp/longjmp, see C implementation for an example:<b= r> <br> <a href=3D"http://homepage.mac.com/sigfpe/Computing/continuations.html" tar= get=3D"_blank">http://homepage.mac.com/sigfpe/Computing/continuations.html<= /a><br> </blockquote></div><br>How can we access setjmp/longjmp in D?<br><br>Anyway= , I'm a bit nervous with using such a raw statement. An oh-so-slightly = wrapped equivalent for D would be better.<br><br><br>Philippe<br><br> --000325559fded551bb048f83eccd--
Sep 05 2010
--0016e6d58a140711e6048f84035f Content-Type: text/plain; charset=ISO-8859-1 On Sun, Sep 5, 2010 at 15:56, Andrei Alexandrescu < SeeWebsiteForEmail erdani.org> wrote:equivalent to the problem:auto solution = comp!("[a,b]", "a*b == 8")([1,2,3], [4,5,6]); solution is a range, in this case a one element range, containing only [2,4].
Here we need to have a crossProduct range, as we discussed in the thread "Combining infinite ranges". Then it's easy to combine it with filter: auto solutions = filter!"a*b == 8"(crossProduct([1,2,3], [4,5,6]));
Not exactly: crossProduct is a range, and the only element type that makes sense is Tuple!(A,B). Unless of course you're interested in adding binary predicates to filter, which would be understood as automatically opening tuples (and of course, would statically check the length of the tuple and the arity of the passed function). I can add this to Phobos. What you call crossProduct can be seen as zipWith!tuple(range, range2), which If there is interest in this, I also suggest having a n-range version of map that takes a n-ary function and maps them in parallel. auto m = map!"a < b ? a : c"(range1, range2, range3); OK, I definitely need to take some time to assemble all this and propose it for a formal Phobos review. I'll bump it up higher in my TODO list. Philippe Philippe --0016e6d58a140711e6048f84035f Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Sun, Sep 5, 2010 at 15:56, Andrei Alexandresc= u <span dir=3D"ltr"><<a href=3D"mailto:SeeWebsiteForEmail erdani.org">Se= eWebsiteForEmail erdani.org</a>></span> wrote:<br><blockquote class=3D"g= mail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(= 204, 204, 204); padding-left: 1ex;"> <br><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; b= order-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class=3D= "im"> equivalent to the problem:<br> <br> auto solution =3D comp!("[a,b]", "a*b =3D=3D 8")([1,2,3= ], [4,5,6]);<br> <br> solution is a range, in this case a one element range, containing only<br> [2,4].<br> </div></blockquote>I did a range comprehension maybe one year ago, which wo= uld be partially<br> <br> Here we need to have a crossProduct range, as we discussed in the thread &q= uot;Combining infinite ranges". Then it's easy to combine it with = filter:<br> <br> auto solutions =3D filter!"a*b =3D=3D 8"(crossProduct([1,2,3], [4= ,5,6]));<font color=3D"#888888"></font></blockquote><div><br>Not exactly: c= rossProduct is a range, and the only element type that makes sense is Tuple= !(A,B).<br> Unless of course you're interested in adding binary predicates to filte= r, which would be understood as automatically opening tuples (and of course= , would statically check the length of the tuple and the arity of the passe= d function). I can add this to Phobos.<br> <br>What you call crossProduct can be seen as zipWith!tuple(range, range2),= which<br><br>If there is interest in this, I also suggest having a n-range= version of map that takes a n-ary function and maps them in parallel. <br> <br>auto m =3D map!"a < b ? a : c"(range1, range2, range3);<br=<br>OK, I definitely need to take some time to assemble all this and propo=
t.<br> <br>Philippe<br><br><br>Philippe<br></div></div> --0016e6d58a140711e6048f84035f--
Sep 05 2010
--0016e6d58a14839d97048f841cbd Content-Type: text/plain; charset=ISO-8859-1 On Sun, Sep 5, 2010 at 16:30, Philippe Sigaud <philippe.sigaud gmail.com>wrote:What you call crossProduct can be seen as zipWith!tuple(range, range2), which
--0016e6d58a14839d97048f841cbd Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Sun, Sep 5, 2010 at 16:30, Philippe Sigaud <s= pan dir=3D"ltr"><<a href=3D"mailto:philippe.sigaud gmail.com">philippe.s= igaud gmail.com</a>></span> wrote:<br><blockquote class=3D"gmail_quote" = style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 20= 4); padding-left: 1ex;"> <div class=3D"gmail_quote">What you call crossProduct can be seen as zipWit= h!tuple(range, range2), which<br><div><br></div></div></blockquote><div><br=Scratch that. zipWith *is* mapping on n ranges in parallel.<br><br>=A0<br>
--0016e6d58a14839d97048f841cbd--
Sep 05 2010
On Sun, 05 Sep 2010 18:24:43 +0400, Philippe Sigaud <philippe.sigaud gmail.com> wrote:2010/9/5 Denis Koroskin <2korden gmail.com>On Sun, 05 Sep 2010 16:59:31 +0400, Philippe Sigaud < philippe.sigaud gmail.com> wrote: But the real challenge in the SO question is the 'going back in time'part, which I have trouble to understand : how can you modify x and y through a multiplication and a comparison?
example: http://homepage.mac.com/sigfpe/Computing/continuations.html
How can we access setjmp/longjmp in D? Anyway, I'm a bit nervous with using such a raw statement. An oh-so-slightly wrapped equivalent for D would be better. Philippe
It is available after the following import: import core.sys.posix.setjmp; It is not defined on Windows, but I believe you can use the following declaration with dmd (works for ddmd): version (Windows) { alias int[16] jmp_buf; extern (C) extern { int setjmp(ref jmp_buf env); void longjmp(ref jmp_buf env, int value); } } Some documentation: http://en.wikipedia.org/wiki/Setjmp.h Use the following struct (or make it a class) if you prefer OOP style: struct State { int save() { return setjmp(buf); } void restore(int status) { assert(status != 0); longjmp(buf, status); } private jmp_buf buf; } import std.stdio; void main() { State state; int result = state.save(); if (result == 0) { // first time here writeln("state saved"); state.restore(1); } else { assert(result == 1); writeln("state restored"); } } The code above should print: state saved state restored (not tested)
Sep 05 2010
On Sun, 05 Sep 2010 19:17:55 +0400, bearophile <bearophileHUGS lycos.com> wrote:Denis Koroskin:The code above should print: state saved state restored (not tested)
On Windows, dmd 2.048, this code: import std.c.stdio: puts; version (Windows) { alias int[16] jmp_buf; extern (C) extern { int setjmp(ref jmp_buf env); void longjmp(ref jmp_buf env, int value); } } struct State { int save() { return setjmp(buf); } void restore(int status) { assert(status != 0); longjmp(buf, status); } private jmp_buf buf; } void main() { State state; int result = state.save(); if (result == 0) { // first time here puts("state saved"); state.restore(1); } else { assert(result == 1); puts("state restored"); } } Gives an Access Violation after printing state saved. Bye, bearophile
Turn main into an "extern(C) int main()" and it works. Surround the code with try/catch block and it fails again. Looks like longjmp fails if you run the function inside a try/catch block for some reason.
Sep 05 2010
On Sun, 05 Sep 2010 20:18:13 +0400, bearophile <bearophileHUGS lycos.com> wrote:Denis Koroskin:Turn main into an "extern(C) int main()" and it works.
This version: import std.c.stdio: puts; version (Windows) { alias int[16] jmp_buf; extern (C) extern { int setjmp(ref jmp_buf env); void longjmp(ref jmp_buf env, int value); } } struct State { int save() { return setjmp(buf); } void restore(int status) { assert(status != 0); longjmp(buf, status); } private jmp_buf buf; } extern(C) int main() { State state; int result = state.save(); if (result == 0) { // first time here puts("state saved"); state.restore(1); } else { assert(result == 1); puts("state restored"); } return 0; } Gives link errors: test.obj(test) Error 42: Symbol Undefined __d_assertm test.obj(test) Error 42: Symbol Undefined __d_assert_msg Bye, bearophile
Try linking with phobos explicitly: # dmd test.d phobos.lib
Sep 05 2010
Philippe Sigaud <philippe.sigaud gmail.com> wrote:But the real challenge in the SO question is the 'going back in time' part, which I have trouble to understand : how can you modify x and y through a multiplication and a comparison?
I believe this to be possible, though horrible and unpleasant. Basically, binary operations on Amb ranges create a new, temporary type. This type keeps track of which ranges have been involved in the operation thus far, and which operations, and at the end gives each Amb a bool delegate( ElementType!Amb ) that has a heap copy of each other range and evaluates the operations on each. However, this solution may lead to inconsistent state in the combination of ranges. Another solution is for each Amb to keep track of a 'controller', which keeps track of the constraints given. This controller would be a combinatorial product of references to the ranges involved. Any call to popFront on the Amb ranges would delegate to the controller's popFront, which would update the involved ranges. Due to the unknowability of the number and type of ranges involved, this controller would need to be a class. I believe, but cannot prove, that only one constraint (i.e. one set of operations) would be feasible to keep track of in such a system, and thus the following would not work: auto a = amb( [1,2,3] ); auto b = amb( [1,3,6] ); auto c = amb( [3,6,9] ); a * b = 6; a * c = 9; assert( a == 1 ); assert( b == 6 ); assert( c == 9 ); A system based around the combinatorial range as a stand-alone, and using filter(s) could easily do the equivalent, but would be limited in that it would only yield one range unless given reference semantics. In the latter case, it would function much like above, except the controller would be a known type that the programmer him- or herself would need to manage. Another problem of the first system is that it has no support for conditionals. -- Simen
Sep 05 2010
Peter Alexander <peter.alexander.au gmail.com> wrote:I must be missing something, because I don't understand how you could possibly take the cross product of any number of infinite ranges (other than to just return the range of (a[0], b[i]) for all (infinitely many) i in b). Note that I'm assuming you mean cartesian product, rather than cross product; I've never heard cross product used in the context of sets.
Quite simple - the result is also an infinte range (infinitely infinite, if you will :p ), that is lazily calculated. And yes, Cartesian product is exactly what we're talking about. -- Simen
Sep 06 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:I convinced myself crossProduct is impossible to implement if one input range and one infinite forward range are simultaneously present. It works with any number of infinite forward ranges, and also with other combinations. I couldn't formalize the exact requirements yet.
This is indeed correct. Now, I have found a working algorithm (it works on paper, I swear!), but I can't seem to get it to work in code. Special cases come for input ranges - I will not consider those. All forward ranges can be treated the same, regardless of infiniteness. We need to keep track of the active ranges, and the initial versions of those (i.e. those passed to the constructor). In addition, we need to keep the position of each range, probably as a ulong (2 ranges should give 2^128 combinations, which will not cover the whole solution space for infinite ranges, but will still be enough for practical purposes). Also, we must maintain a stack of locked ranges. The solution is recursive to the number of ranges, and is given in pseudocode below. Critique is very, VERY welcome! bool movedEnough( lastUnlocked, lockedStack.peek ) { if ( lastUnlocked.empty ) { // If range is empty, don't pop stuff off of it. return true; } else if ( lastUnlocked > lockedStack.peek ) { // If the last unlocked range has a higher index than // the next one the locked stack, check if popping // would bring us past its position. return pos[lastUnlocked] >= pos[lockedStack.peek]; } else { // If the last unlocked range has a lower index than // the next one the locked stack, check if popping // would bring us to its position. return pos[lastUnlocked] >= pos[lockedStack.peek] -1; } } void popFront( ) { if ( !unlockedRanges.empty ) { // If there are unlocked ranges, use the first of them currentRange = unlockedRanges[0]; } else { // No unlocked ranges, so unlock one. currentRange = lastUnlocked = lockedStack.pop; unlock( lastUnlocked ); while ( movedEnough( lastUnlocked, lockedStack.peek ) ) { // We have moved far enough along this range, move the next one up. currentRange = lastUnlocked = lockedStack.pop; unlock( lastUnlocked ); if ( // If there are more unlocked ranges below this one ( lastUnlocked != unlockedRanges[$] ) || // Or there are no more locked ranges ( lockedStack.empty ) ) { // Move to the next range. Note that firstAfter would need to return 0 on being passed $. currentRange = unlockedRanges.firstAfter( lastUnlocked ); // We have found the next range from which to pop. break; } } } // Pop off the found range, the lock it, and reset all unlocked ranges to their saved states. currentRange.popFront(); lock(currentRange); foreach ( unlockedRanges ) { reset(); } } Given cartesian( [1,2], "ab" ), the result should be as follows: tuple( 1, 'a' ); tuple( 2, 'a' ); tuple( 2, 'b' ); tuple( 1, 'b' ); And for cartesian( [1,2,3], "abc" ): tuple( 1, 'a' ); tuple( 2, 'a' ); tuple( 2, 'b' ); tuple( 1, 'b' ); tuple( 3, 'a' ); tuple( 3, 'b' ); tuple( 3, 'c' ); tuple( 1, 'c' ); tuple( 2, 'c' ); -- Simen
Sep 06 2010
Simen kjaeraas <simen.kjaras gmail.com> wrote:Special cases come for input ranges - I will not consider those. All forward ranges can be treated the same, regardless of infiniteness.
Actually, input ranges make everything a lot easier - the best solution is the brute-force stupid solution. -- Simen
Sep 06 2010
------------cX4RmVk2x311O5yQsT5f4i Content-Type: text/plain; charset=utf-8; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit Attached latest version. It bugs out with an infinite loop, and I'm too tired to look more at it now. -- Simen ------------cX4RmVk2x311O5yQsT5f4i Content-Disposition: attachment; filename=autoRefTuple.d Content-Type: application/octet-stream; name=autoRefTuple.d Content-Transfer-Encoding: Base64 bW9kdWxlIGF1dG9SZWZUdXBsZTsNCg0KaW1wb3J0IHN0ZC5yYW5nZTsNCmltcG9y dCBzdGQudHJhaXRzOw0KaW1wb3J0IHN0ZC50eXBldHVwbGU7DQppbXBvcnQgc3Rk LmNvbnY7DQoNCnRlbXBsYXRlIGhhc0x2YWx1ZUVsZW1lbnRzKCBSICkgaWYgKCBp c0lucHV0UmFuZ2UhUiApIHsNCgllbnVtIGhhc0x2YWx1ZUVsZW1lbnRzID0gaXMo IHR5cGVvZiggeyBSIHI7IGF1dG8gYSA9ICYoIHIuZnJvbnQgKTsgfSApICk7DQp9 DQoNCnRlbXBsYXRlIGhhc0x2YWx1ZUVsZW1lbnRzKCBSICkgaWYgKCAhaXNJbnB1 dFJhbmdlIVIgKSB7DQoJcHJhZ21hKCBtc2csIFIgKTsNCglzdGF0aWMgYXNzZXJ0 KCBmYWxzZSApOw0KfQ0KDQpzdHJ1Y3QgUmVmKCBUICkgew0KCXN0YXRpYyBzdHJ1 Y3QgUmVmSW1wbCB7DQoJCVQqIF9kYXRhOw0KCQkNCgkJQHByb3BlcnR5DQoJCXJl ZiBUIGRhdGEoICkgew0KCQkJcmV0dXJuICpfZGF0YTsNCgkJfQ0KCQlhbGlhcyBk YXRhIHRoaXM7DQoNCgkJcmVmIFQgb3BBc3NpZ24oIHJlZiBUIHZhbHVlICkgew0K CQkJX2RhdGEgPSAmdmFsdWU7DQoJCQlyZXR1cm4gKl9kYXRhOw0KCQl9DQoJCQ0K CQl2b2lkIGFzc2lnbiggcmVmIFQgdmFsdWUgKSB7DQoJCQlfZGF0YSA9ICZ2YWx1 ZTsNCgkJfQ0KCX0NCglwcml2YXRlIFJlZkltcGwgUmVmOw0KCWFsaWFzIFJlZiB0 aGlzOw0KDQoJcmVmIFQgb3BBc3NpZ24oIFQgdmFsdWUgKSB7DQoJCSpSZWYuX2Rh dGEgPSB2YWx1ZTsNCgkJcmV0dXJuICpSZWYuX2RhdGE7DQoJfQ0KfQ0KDQpzdHJ1 Y3QgTm9SZWYoIFQgKSB7DQoJc3RhdGljIHN0cnVjdCBSZWZJbXBsIHsNCgkJVCBk YXRhOw0KCQlhbGlhcyBkYXRhIHRoaXM7DQoNCgkJcmVmIFQgb3BBc3NpZ24oIFQg dmFsdWUgKSB7DQoJCQlkYXRhID0gdmFsdWU7DQoJCQlyZXR1cm4gZGF0YTsNCgkJ fQ0KCX0NCglwcml2YXRlIFJlZkltcGwgUmVmOw0KCQ0KCXJlZiBUIF9kYXRhKCAp IHsNCgkJcmV0dXJuIFJlZi5kYXRhOw0KCX0NCglhbGlhcyBfZGF0YSB0aGlzOw0K DQoJcmVmIFQgb3BBc3NpZ24oIFQgdmFsdWUgKSB7DQoJCVJlZi5kYXRhID0gdmFs dWU7DQoJCXJldHVybiBSZWYuZGF0YTsNCgl9DQp9DQoNCnRlbXBsYXRlIGF1dG9S ZWZFbGVtZW50VHlwZSggUiApICB7DQoJYWxpYXMgU2VsZWN0ISggaGFzTHZhbHVl RWxlbWVudHMhUiwgUmVmISggRWxlbWVudFR5cGUhKCBSICkgKSwgTm9SZWYhKCBF bGVtZW50VHlwZSEoIFIgKSApICkgYXV0b1JlZkVsZW1lbnRUeXBlOw0KfQ0KDQpz dHJ1Y3QgQXV0b1JlZlR1cGxlKCBULi4uICkgew0KCWFsaWFzIFR5cGVUdXBsZSEo IHN0YXRpY01hcCEoIGF1dG9SZWZFbGVtZW50VHlwZSwgVCApICkgUFQ7DQoJUFQg ZmllbGQ7DQoJYWxpYXMgZmllbGQgZXhwYW5kOw0KCQ0KCXRoaXMoIFQgdmFsdWVz ICkgew0KCQlmb3JlYWNoICggaSwgdmFsOyB2YWx1ZXMgKSB7DQoJCQlmaWVsZFtp XS5SZWYgPSB2YWwuZnJvbnQ7DQoJCX0NCgl9DQoJDQoJc3RyaW5nIHRvU3RyaW5n KCApIHsNCgkJc3RyaW5nIHJlc3VsdCA9IEF1dG9SZWZUdXBsZS5zdHJpbmdvZiB+ ICIoIjsNCgkJZm9yZWFjaCAoIGksIGZpZWxkOyBleHBhbmQgKSB7DQoJCQlyZXN1 bHQgfj0gdG8hc3RyaW5nKCBmaWVsZC5SZWYuZGF0YSApIH4gIiwiOw0KCQl9DQoJ CXJldHVybiByZXN1bHRbMC4uJC0xXSB+ICIpIjsNCgl9DQp9DQoNCmF1dG8gYXV0 b1JlZlR1cGxlKCBSLi4uICkoIFIgcmFuZ2VzICkgew0KCXJldHVybiBBdXRvUmVm VHVwbGUhUiggcmFuZ2VzICk7DQp9 ------------cX4RmVk2x311O5yQsT5f4i Content-Disposition: attachment; filename=combine.d Content-Type: application/octet-stream; name=combine.d Content-Transfer-Encoding: Base64 bW9kdWxlIGNvbWJpbmU7DQoNCmltcG9ydCBzdGQuc3RkaW87DQoNCmltcG9ydCBz dGQuY29udjsNCmltcG9ydCBzdGQudHJhaXRzOw0KaW1wb3J0IHN0ZC5yYW5nZTsN CmltcG9ydCBzdGQudHlwZXR1cGxlOw0KDQppbXBvcnQgYXV0b1JlZlR1cGxlOw0K DQp0ZW1wbGF0ZSBzdGF0aWNJb3RhKCBpbnQgc3RhcnQsIGludCBlbmQsIGludCBz dGVwID0gMSApIHsNCglzdGF0aWMgaWYgKCBzdGFydCArIHN0ZXAgPD0gZW5kICkg ew0KCQlhbGlhcyBUeXBlVHVwbGUhKCBzdGFydCwgc3RhdGljSW90YSEoIHN0YXJ0 ICsgc3RlcCwgZW5kLCBzdGVwICkgKSBzdGF0aWNJb3RhOw0KCX0gZWxzZSB7DQoJ CWFsaWFzIFR5cGVUdXBsZSEoKSBzdGF0aWNJb3RhOw0KCX0NCn0NCg0Kc3RydWN0 IENvbWJpbmVyKCBSLi4uICkgaWYgKCBhbGxTYXRpc2Z5ISggaXNGb3J3YXJkUmFu Z2UsIFIgKSApIHsNCglzdHJ1Y3QgQ29tYmluZXJJbXBsIHsNCgkJUiByYW5nZXNf b3JpZywNCgkJCQlyYW5nZXM7DQoJCXVsb25nW1IubGVuZ3RoXSBwb3M7DQoJCWlu dFtSLmxlbmd0aF0gbG9ja2VkU3RhY2s7DQoJCWludCBsYXN0TG9ja2VkOw0KCQlh bGlhcyBzdGF0aWNJb3RhISggMCwgUi5sZW5ndGggKSByYW5nZUluZGljZXM7DQoJ CQ0KCQl2b2lkIHBvcEZyb250UmFuZ2UoIGludCBpICkgew0KCQkJc3dpdGNoICgg aSApIHsNCgkJCQlmb3JlYWNoICggZTsgcmFuZ2VJbmRpY2VzICkgew0KCQkJCQlj YXNlIGU6DQoJCQkJCQlyYW5nZXNbIGUgXS5wb3BGcm9udCggKTsNCgkJCQkJCXBv c1sgZSBdKys7DQoJCQkJCQlyZXR1cm47DQoJCQkJfQ0KCQkJCWRlZmF1bHQ6DQoJ CQkJCWFzc2VydCggZmFsc2UgKTsNCgkJCX0NCgkJfQ0KCQkNCgkJdm9pZCBwdXNo TG9ja2VkKCBpbnQgaW5kZXggKSB7DQoJCQlsb2NrZWRTdGFja1srK2xhc3RMb2Nr ZWRdID0gaW5kZXg7DQoJCX0NCgkJDQoJCWludCBwb3BMb2NrZWQoICkgew0KCQkJ bGFzdExvY2tlZC0tOw0KCQkJcmV0dXJuIGxvY2tlZFN0YWNrW2xhc3RMb2NrZWQr MV07DQoJCX0NCgkJDQoJCWludCBmaXJzdFVubG9ja2VkKCApIHsNCgkJCWZvcmVh Y2ggKCBpOyByYW5nZUluZGljZXMgKSB7DQoJCQkJaWYgKCBpc0xvY2tlZCggaSAp ICkgew0KCQkJCQlicmVhazsNCgkJCQl9DQoJCQkJcmV0dXJuIGk7DQoJCQl9DQoJ CQlyZXR1cm4gLTE7DQoJCX0NCgkJDQoJCWludCB1bmxvY2tlZEFmdGVyKCBpbnQg aSApIHsNCgkJCWZvcmVhY2ggKCBqOyBpKzEuLlIubGVuZ3RoICkgew0KCQkJCWlm ICggIWlzTG9ja2VkKCBqICkgKSB7DQoJCQkJCXJldHVybiBqOw0KCQkJCX0NCgkJ CX0NCgkJCWZvcmVhY2ggKCBqOyAwLi5pICkgew0KCQkJCWlmICggIWlzTG9ja2Vk KCBqICkgKSB7DQoJCQkJCXJldHVybiBqOw0KCQkJCX0NCgkJCX0NCgkJCXJldHVy biAtMTsNCgkJfQ0KCQkNCgkJYm9vbCBpc0xvY2tlZCggaW50IGkgKSB7DQoJCQlm b3JlYWNoICggajsgMC4ubGFzdExvY2tlZCsxICkgew0KCQkJCWlmICggbG9ja2Vk U3RhY2tbal0gPT0gaSApIHsNCgkJCQkJcmV0dXJuIHRydWU7DQoJCQkJfQ0KCQkJ fQ0KCQkJcmV0dXJuIGZhbHNlOw0KCQl9DQoJCQ0KCQlib29sIHJhbmdlRW1wdHko IGludCBpICkgew0KCQkJc3dpdGNoICggaSApIHsNCgkJCQlmb3JlYWNoICggZTsg cmFuZ2VJbmRpY2VzICkgew0KCQkJCQljYXNlIGU6DQoJCQkJCQlyZXR1cm4gcmFu Z2VzWyBlIF0uZW1wdHk7DQoJCQkJfQ0KCQkJCWRlZmF1bHQ6DQoJCQkJCWFzc2Vy dCggZmFsc2UgKTsNCgkJCX0NCgkJfQ0KCQkNCgkJYm9vbCBtb3ZlZEVub3VnaCgg aW50IGN1cnJlbnQgKSB7DQoJCQlpZiAoIHJhbmdlRW1wdHkoIGN1cnJlbnQgKSAp IHsNCgkJCQlyZXR1cm4gdHJ1ZTsNCgkJCX0gZWxzZSBpZiAoIGxhc3RMb2NrZWQg PT0gLTEgKSB7DQoJCQkJcmV0dXJuIHRydWU7DQoJCQl9IGVsc2UgaWYgKCBjdXJy ZW50ID4gbG9ja2VkU3RhY2tbbGFzdExvY2tlZF0gKSB7DQoJCQkJcmV0dXJuIHBv c1tjdXJyZW50XSA+PSBwb3NbbG9ja2VkU3RhY2tbbGFzdExvY2tlZF1dOw0KCQkJ fSBlbHNlIHsNCgkJCQlyZXR1cm4gcG9zW2N1cnJlbnRdID49IHBvc1tsb2NrZWRT dGFja1tsYXN0TG9ja2VkXV0gLTE7DQoJCQl9DQoJCX0NCg0KCQlpbnQgbGFzdFVu bG9ja2VkKCApIHsNCgkJCWludCByZXN1bHQgPSAtMTsNCgkJCWZvcmVhY2ggKCBp OyByYW5nZUluZGljZXMgKSB7DQoJCQkJaWYgKCAhaXNMb2NrZWQoIGkgKSApIHsN CgkJCQkJcmVzdWx0ID0gaTsNCgkJCQl9DQoJCQl9DQoJCQlyZXR1cm4gcmVzdWx0 Ow0KCQl9DQoJCQ0KCQl2b2lkIHJlc2V0VW5sb2NrZWQoICkgew0KCQkJZm9yZWFj aCAoIGk7IHJhbmdlSW5kaWNlcyApIHsNCgkJCQlpZiAoICFpc0xvY2tlZCggaSAp ICkgew0KCQkJCQlyYW5nZXNbaV0gPSByYW5nZXNfb3JpZ1tpXS5zYXZlKCApOw0K CQkJCQlwb3NbaV0gPSAwOw0KCQkJCX0NCgkJCX0NCgkJfQ0KCQkNCgkJdm9pZCBw b3BGcm9udCggKSB7DQoJCQlpbnQgY3VycmVudFJhbmdlID0gMDsNCgkJCWlmICgg bGFzdExvY2tlZCA9PSBSLmxlbmd0aCApIHsNCgkJCQljdXJyZW50UmFuZ2UgPSBm aXJzdFVubG9ja2VkKCApOw0KCQkJfSBlbHNlIHsNCgkJCQl3aGlsZSAoIG1vdmVk RW5vdWdoKCBjdXJyZW50UmFuZ2UgKSApIHsNCgkJCQkJY3VycmVudFJhbmdlID0g cG9wTG9ja2VkKCApOw0KCQkJCQlpZiAoICggY3VycmVudFJhbmdlICE9IGxhc3RV bmxvY2tlZCggKSApIHx8ICggbGFzdExvY2tlZCA9PSAtMSApICkgew0KCQkJCQkJ Y3VycmVudFJhbmdlID0gdW5sb2NrZWRBZnRlciggY3VycmVudFJhbmdlICk7DQoJ CQkJCQlicmVhazsNCgkJCQkJfQ0KCQkJCX0NCgkJCX0NCgkJCQ0KCQkJcG9wRnJv bnRSYW5nZSggY3VycmVudFJhbmdlICk7DQoJCQlwdXNoTG9ja2VkKCBjdXJyZW50 UmFuZ2UgKTsNCgkJCQ0KCQkJcmVzZXRVbmxvY2tlZCggKTsNCgkJfQ0KCX0NCgkN CglDb21iaW5lckltcGwgQ29tYmluZXI7DQoJYWxpYXMgQXV0b1JlZlR1cGxlIVIg RWxlbWVudFR1cGxlOw0KCQ0KCXRoaXMoIFIgcnMgKSB7DQoJCWZvcmVhY2ggKCBp LCBlOyBycyApIHsNCgkJCUNvbWJpbmVyLnJhbmdlc19vcmlnW2ldID0gZS5zYXZl KCApOw0KCQkJQ29tYmluZXIucmFuZ2VzW2ldID0gZS5zYXZlKCApOw0KCQl9DQoJ CUNvbWJpbmVyLnBvc1tdID0gMDsNCgkJQ29tYmluZXIubG9ja2VkU3RhY2tbXSA9 IDA7DQoJCUNvbWJpbmVyLmxhc3RMb2NrZWQgPSAtMTsNCgkJQ29tYmluZXIucHVz aExvY2tlZCggMCApOw0KCX0NCgkNCglAcHJvcGVydHkNCglib29sIGVtcHR5KCAp IGNvbnN0IHsNCgkJZm9yZWFjaCAoIGU7IENvbWJpbmVyLnJhbmdlcyApIHsNCgkJ CWlmICggZS5lbXB0eSApIHsNCgkJCQlyZXR1cm4gdHJ1ZTsNCgkJCX0NCgkJfQ0K CQlyZXR1cm4gZmFsc2U7DQoJfQ0KCQ0KCUBwcm9wZXJ0eSANCglFbGVtZW50VHVw bGUgZnJvbnQoICkgew0KCQlyZXR1cm4gRWxlbWVudFR1cGxlKCBDb21iaW5lci5y YW5nZXMgKTsNCgl9DQoJDQoJdm9pZCBwb3BGcm9udCggKSB7DQoJCUNvbWJpbmVy LnBvcEZyb250KCApOw0KCX0NCn0NCg0KYXV0byBjb21iaW5lKCBSLi4uICkoIFIg cmFuZ2VzICkgaWYgKCBhbGxTYXRpc2Z5ISggaXNGb3J3YXJkUmFuZ2UsIFIgKSAp IHsNCglzdGF0aWMgaWYgKCBSLmxlbmd0aCA9PSAxICkgew0KCQlyZXR1cm4gcmFu Z2VzWzBdOw0KCX0gZWxzZSB7DQoJCXJldHVybiBDb21iaW5lciFSKCByYW5nZXMg KTsNCgl9DQp9DQoNCnZvaWQgbWFpbiggKSB7DQoJYXV0byBvID0gdGFrZSggY29t YmluZSggWzEsMl0sICJhYiIgKSwgMTAgKTsNCglmb3JlYWNoICggZTsgbyApIHsN CgkJd3JpdGVsbiggZSApOw0KCX0NCgl3cml0ZWxuKCAiPT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT0iICk7DQoJDQoJbyA9IHRha2UoIGNvbWJp bmUoIFsxLDIsM10sICJhYmMiICksIDEwICk7DQoJZm9yZWFjaCAoIGU7IG8gKSB7 DQoJCXdyaXRlbG4oIGUgKTsNCgl9DQp9 ------------cX4RmVk2x311O5yQsT5f4i--
Sep 06 2010