<br><br><div class="gmail_quote">On Mon, Dec 21, 2009 at 23:44, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:SeeWebsiteForEmail@erdani.org">SeeWebsiteForEmail@erdani.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
This is a great example that I don't have the time to look into now. In essence the task is to generate all numbers of the form 2^^a*3^^b*5^^c where a, b, and c are natural numbers.<br>
<br>
Currently Phobos doesn't have the means to compute the cross-product of ranges. I encourage people to think about implementing that.<br><font color="#888888">
<br>
Andrei</font></blockquote><div><br>I posted yesterday on D.announce that I have some code related to that:<br><br><a href="http://www.dsource.org/projects/dranges">http://www.dsource.org/projects/dranges</a><br><br>If some people are interested, I'd be delighted to have some feedback. The docs for the algorithm module is here:<br>
<br><a href="http://svn.dsource.org/projects/dranges/trunk/docs/algorithm2.html">http://svn.dsource.org/projects/dranges/trunk/docs/algorithm2.html</a><br><br>There is a cross-product for ranges (returning tuples), called combinations. As in, <br>
<br>auto c = combinations(r1, r2, r3, r4); // Takes a variadic number of ranges. <br><br><br>I put a Hamming numbers example in the docs, for the merge function.<br>From the docs :<br><br><pre class="d_code"><font color="green">// Calculating Hamming numbers, numbers of the form 2^i * 3^j * 5^k<br>
</font><font color="green">// see <a href="http://en.wikipedia.org/wiki/Regular_number">http://en.wikipedia.org/wiki/Regular_number</a><br></font><font color="green">// Dijkstra's algorithm heavily uses merge.<br></font>T[] hamming(T)(T[] r)<br>
{<br> <font color="blue">return</font> 1 ~ <u>merge2</u>(map!<font color="red">"2*a"</font>(r),<u>merge2</u>(map!<font color="red">"3*a"</font>(r),map!<font color="red">"5*a"</font>(r)));<br>
}<br><br><font color="blue">auto</font> hammingNumbers = iterate!hamming([1UL][]); <font color="green">// develops the Hamming sequence at each iteration.</font><br><font color="green">// 1,2,3,4,5,6,8,9,10,12,...<br></font><font color="green">// For the i-th iteration, the sequence is complete up to 2^i,<br>
</font><font color="green">// but has much more numbers already calculated.<br><br></font></pre>So I kind of cheat there: it's not Haskell's elegant self-recursive definition, but it's very near Dijkstra's algorithm and can be made a one-liner, if that's really a criteria... At each front call, iterate extends the sequence.<br>
<br>merge2 is greedy and works only for two ranges (hence it's name), but I have a templated, predicate-aliased, lazy, n-ranges version called merge in the module.<br><br> Philippe<br><br></div></div>