## digitalmars.D - Hamming numbers comparison, take 2

- bearophile <bearophileHUGS lycos.com> Jun 09 2010

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