www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [Challenge] implementing the ambiguous operator in D

reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
--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">&quot;hello&quot= ;</span><span class=3D"pun">,</span><span class=3D"pln"> </span><span class= =3D"str">&quot;world&quot;</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">&quot;qwerty&quot;</span>=

">=3D=3D</span><span class=3D"pln"> amb</span><span class=3D"pun">([</span>= <span class=3D"str">&quot;helloqwerty&quot;</span><span class=3D"pun">,</sp= an><span class=3D"pln"> </span><span class=3D"str">&quot;worldqwerty&quot;<= /span><span class=3D"pun">])</span><span class=3D"pln"><br> amb</span><span class=3D"pun">([</span><span class=3D"str">&quot;hello&quot= ;</span><span class=3D"pun">,</span><span class=3D"pln"> </span><span class= =3D"str">&quot;world&quot;</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">&quot;qwerty&quot;</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">&quot;helloqwerty&quot;</span><span class= =3D"pun">,</span><span class=3D"pln"> </span><span class=3D"str">&quot;worl= dqwerty&quot;</span><span class=3D"pun">])</span><span class=3D"pln"><br> amb</span><span class=3D"pun">([</span><span class=3D"str">&quot;hello&quot= ;</span><span class=3D"pun">,</span><span class=3D"pln"> </span><span class= =3D"str">&quot;very long string&quot;</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
next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
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
parent reply Pelle <pelle.mansson gmail.com> writes:
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
parent Peter Alexander <peter.alexander.au gmail.com> writes:
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
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--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">&lt;<a href=3D"http://peter.alexander.au">peter.ale= xander.au</a> <a href=3D"http://gmail.com">gmail.com</a>&gt;</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&#39;t bother adding more than I did because it would m= ake the post too large, and wouldn&#39;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&#39;t chain them), but that&#39;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(&quot;a&quot;,&quot;u&quot;) didn&#39= ;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(&quot;return map!((E e) { return= e.&quot;~f~&quot;; })(r);&quot;);<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!(&quot;a.&quot;~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&#39;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
prev sibling next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"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
next sibling parent "Nick Sabalausky" <a a.a> writes:
"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
prev sibling parent Peter Alexander <peter.alexander.au gmail.com> writes:
== Quote from Nick Sabalausky (a a.a)'s article
 Interesting 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
prev sibling next sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
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
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
== Quote from Simen kjaeraas (simen.kjaras gmail.com)'s article
 Yes, 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
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
== Quote from Andrei Alexandrescu
 Yah, 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
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 09/06/2010 06:51 AM, Peter Alexander wrote:
 == Quote from Andrei Alexandrescu
 Yah, 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
next sibling parent Peter Alexander <peter.alexander.au gmail.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 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

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
prev sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
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
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
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
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
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
parent bearophile <bearophileHUGS lycos.com> writes:
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
prev sibling next sibling parent reply Justin Johansson <no spam.com> writes:
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
parent reply bearophile <bearophileHUGS lycos.com> writes:
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
parent reply Don <nospam nospam.com> writes:
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
next sibling parent Peter Alexander <peter.alexander.au gmail.com> writes:
== Quote from Don (nospam nospam.com)'s article
 That'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
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
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
next sibling parent reply Don <nospam nospam.com> writes:
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
parent bearophile <bearophileHUGS lycos.com> writes:
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
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
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
parent bearophile <bearophileHUGS lycos.com> writes:
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/5NvzR
Maybe with lazy int delegates ?<

Right, but the devil is in details. Bye, bearophile
Sep 05 2010
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--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 article
 Yes, 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">&lt;<a href=3D"http://peter.alexander.au">peter.ale= xander.au</a> <a href=3D"http://gmail.com">gmail.com</a>&gt;</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>)&#39;s article<br>

nderstood the<br> &gt; 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&#39;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&#39;t.<br> <br> Now, the &#39;real&#39;/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&gt; 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 = &#39;alias possibilities[0] this&#39; 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
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--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">&lt;<a href=3D"mailto:no spam.com">no spam.com</a>= &gt;</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&#39;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&#39;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 &quot;interpreter&quot;.<br><br><br>Philippe <= br></div></div><br> --0016e6d58fd649fda6048f5ffd24--
Sep 03 2010
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Peter Alexander <peter.alexander.au gmail.com> wrote:

 == Quote from Simen kjaeraas (simen.kjaras gmail.com)'s article
 Yes, 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
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
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
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
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
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--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 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.


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">&lt;<a href=3D"mailto:simen.kjaras gmail.com">simen.= kjaras gmail.com</a>&gt;</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 &lt;<a href=3D"mailto:simen.kjaras gmail.com" target=3D= "_blank">simen.kjaras gmail.com</a>&gt; 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(&quot;Calling DynamicFilter with an unset predicate= .&quot;);};}<br>=A0=A0=A0 bool empty() { if (set) {return range.empty;} els= e { throw new Exception(&quot;Calling DynamicFilter with an unset predicate= .&quot;);};}<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 &amp;&amp; !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(&quot;Calling DynamicFilter with an unset predicate.&quot;);<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) &amp;&amp; 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
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--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">&lt;<a href=3D"mailto:bearophileHUGS lycos.com">bearophi= leHUGS lycos.com</a>&gt;</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">&gt; That&#39;s not a very useful problem, because the ti= ming depends entirely on<br> &gt; 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&#39;s = lazy so it uses very low memory.</blockquote><div><br>It&#39;s crystal clea= r &amp; short (but we should aim for J! :-), but being lazy I don&#39;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 &quot;Cyclic Iterators&quot;&quot; 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&#39;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
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
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
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--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">&lt;<a href=3D"mailto:bearophileHUGS lycos.com">bearophileHUGS l= ycos.com</a>&gt;</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 &#39;dips&#39; 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> &gt; For my own D version, that is quite near the Rosetta Code version, I g= et<br> &gt; 3.7s, 100 Mo of RAM. (-O -release -inline)<br> &gt; Using the RC code (your own, translated from Java, right?), I get the = same.<br> &gt; 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&#39;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&#39;s were the trick is = anyway, to have the solution recurse on a &#39;younger&#39; version of itse= lf. Maybe with lazy int delegates ?<br> =A0<br><br>Philippe<br></div></div> --0016e6d56670980920048f8263a7--
Sep 05 2010
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--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 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]. Philippe
  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

--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">&lt;<a href=3D"mailto:simen.kjaras gmail.com">simen.= kjaras gmail.com</a>&gt;</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 &lt;<a href=3D"mailto:philippe.sigaud gma= il.com" target=3D"_blank">philippe.sigaud gmail.com</a>&gt; 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&gt; 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&#3= 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&#39;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&#39;d be like doing a=A0 list comprehension).= <br>But the real challenge in the SO question is the &#39;going back in ti= me&#39; 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!(&quot;[a,b]&quo= t;, &quot;a*b =3D=3D 8&quot;)([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> &#39;alias possibilities[0] this&#39; 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
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
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
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--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= ">&lt;<a href=3D"mailto:2korden gmail.com">2korden gmail.com</a>&gt;</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 &lt;<= a href=3D"mailto:philippe.sigaud gmail.com" target=3D"_blank">philippe.siga= ud gmail.com</a>&gt; 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 &#39;going back in time&#3= 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&#39;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
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--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">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdani.org">Se= eWebsiteForEmail erdani.org</a>&gt;</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!(&quot;[a,b]&quot;, &quot;a*b =3D=3D 8&quot;)([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&quot;. Then it&#39;s easy to combine it with = filter:<br> <br> auto solutions =3D filter!&quot;a*b =3D=3D 8&quot;(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&#39;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!&quot;a &lt; b ? a : c&quot;(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
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--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">&lt;<a href=3D"mailto:philippe.sigaud gmail.com">philippe.s= igaud gmail.com</a>&gt;</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
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
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
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
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
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
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
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
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
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
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
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
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
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
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
prev sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
------------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