www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Hamming numbers comparison, take 2

I have tried to implement the rosettacode Hamming Numbers Task:
http://rosettacode.org/wiki/Hamming_numbers

I have tried to translate the Python version (but the best version is the
Haskell one). I have tried to perform this translation time ago, and it was too
much early for Phobos2. Now I have tried again, and I can see things are
getting better, but Phobos2 seems not good enough yet.

I am using this to find the multiples, this is easy:
    auto m2 = map!q{2 * a}(p2); // multiples of 2
    auto m3 = map!q{3 * a}(p3); // multiples of 3
    auto m5 = map!q{5 * a}(p5); // multiples of 5

But then nWayUnion can't be used, because it accepts an iterable of iterables:
    auto merged = nWayUnion([m2, m3, m5]);
So I'd like nWayUnion to accept N different iterables all of of different type,
with just the constraint that each one yields the same type. I presume it can
work as chain() (I don't know why chain() and nWayUnion() have a so much
different signature).

To remove the duplicates I use this, that looks good enough:
auto output = map!q{a.field[0]}(group(combined)); // eliminate duplicates

The group() of Phobos2 isn't as powerful as the Python groupby(), because
group() yields the pair of head item and its count, while Python groupby()
yields the pair of the head item and a lazy iterable of the duplicated items.

This design of the Python version is sometimes less handy because if you want
to know how many similar items there are (and this is a common usage of
groupby()) you have to count them for example with something like a walkLength,
but it's more powerful because the items can define a generic equality, so they
can be actually not the same item and you may need them all.


Adding the starting item is easy:
auto combined = chain([1], merged); // prepend a starting point
But in practice this Task asks for the millionth item of this Hamming sequence,
that is larger than a ulong, so I have to use something like this:
auto combined = chain([BigInt(1)], merged); // prepend a starting point
But then the BigInt lack a handy toString() (irony: I have seen that inside the
unittests of BigInt there is one such function).

I think Phobos2 lacks a tee() function:
http://docs.python.org/library/itertools.html#itertools.tee
And I have not seen the islice() (a lazy slice) but this is easy enough to
implement.
(I don't know if such ranges are already present in some dsource module about
extra ranges).

A bigger problem in the translation comes from the deferred_output and output,
that I am not sure how to define/translate yet. I accept suggestions :-)
I invite other people to try to use Phobos2, because in practice you can spot
similar troubles only if you actually try to use it.

Bye,
bearophile
Jun 09 2010