Hamming numbers

Hamming aka Ugly, 5-smooth aka Regular numbers.
It is considered to be a trivial task to write it using any functional language, but very difficult on imperatice languages.
My goal is to check whether it is easy (possible) to write a lazy algorithm on functional-style on C++ using boost library (generator_iterator or proto library).

Before I start with c++, let me play with Haskell and Python to understand what I want.
Merge is boring on both languages.

--does WordPress supports Haskell syntax highlight? probably not...
merge xx@(x:xs) yy@(y:ys)
 | x  y = y : xx `merge` ys
 | otherwise = x : xs `merge` ys
def merge(it1, it2):
    i1=it1.__next__()
    i2=it2.__next__()
    while(True):
        if (i1i2):
                yield i2
                i2=it2.__next__()
            else:
                yield i1
                i1=it1.__next__()
                i2=it2.__next__()

def merge3(l1, l2, l3):
    merge(l1, ( i for i in merge(merl2, l3)))
  • Python version 1:Now, Python.
    Interesting discussion can be found here, but I changed it to work on Python 3K and too look nicer. (For me, almost always shorter == nicer.

    def m1_235():
     yield 1
     for i in merge3((2*i for i in m1_235(),
     3*i for i in m1_235(),
     5*i for i in m1_235()):
     yield i
    
  • Python version 2:It uses internal tool to be more lazy: it frees unneeded memory. Haskell (as beeng more lazy) does this automatically.
    from itertools import tee
    def m3_235():
         def _m235():
             yield 1
             for n in merge3((2*i for i in m2),
                         (3*i for i in m3),
                         (5*i for i in m5)):
                 yield n
         m1 = _m235()
         m2, m3, m5, mRes = tee(m1, 4)
         return mRes
    
    it = m3_235()
    

    Now, let’s have fun with haskell

  • Taken from WikiPedia
hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*) hamming
  • more one-line variants
h2= 1 : map (2*) h2 `merge` map (3*) h2 `merge` map (5*) h2
h3= 1 : foldl1 merge [map (2*) h3, map (3*) h3, map (5*) h3]
h7= 1 : foldl1 merge [map ((*) 2) h7, map((*) 3) h7, map((*) 5)h7]
h11 = 1 : foldl1 merge (map ((flip $ x->;map $(x*)) h11) [2, 3, 5])
h12 = 1 : foldl1 merge [map f h12 |f <- map (*) [2, 3, 5]]
h15 = 1 : foldl1 merge ( ap (map map (map (*) [2, 3, 5])) [h15])
h16 = 1 : foldl1 merge [ [f h | h<-h16 ] | f <- map (*) [2, 3, 5]]
h17 = 1 : foldl1 merge [ [f h | h<-h17, f<-[(*2), (*3), (*5)]]]
h18 = 1 : foldl1 merge [ [f h | h<-h18, f<-map (*) [2, 3, 5]]]
h19 f1 f2 f3= (1 : foldl1 merge ( ap (f1 f2 (f3 (*) [2, 3, 5])) [h19 f1 f2 f3]))-- take 111 (h19 map map map)
h20 = 1 : foldl1 merge ( ap (f f (f (*) [2, 3, 5])) [h20]) where f=map

to test them, you should write something like take 111 h2

To be continued: Probably with prolog and C++

Advertisements

Tags: , , , ,

One Response to “Hamming numbers”

  1. fugtve Says:

    the letter l and the digit 1 are indistingushab1e

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: