divisors, in order, with MERGE

gistfile1.hs

    hamm = 1:foldl (\s n->let r = merge s (n:map (n*) r) in r)  [] [5,3,2]

      r0 = []
      r1 = merge r0 (5: map (5*) r1) = [5^i | i<-[1..]]
      r2 = merge r1 (3: map (3*) r2) = r1 + map(3*)(1:r1) + map(9*)(1:r1) + ...
                                          + map( 3^n *)(1:r1) + ...
      r3 = merge r2 (2: map (2*) r3) = r2 + map(2*)(1:r2) + map(4*)(1:r2) + ...
                                          + map( 2^n *)(1:r2) + ...

    so, given a factorization [(p_i,k_i)], the number's divisors are:

      foldr (\(p,k) r-> tail $ foldr merge [] [map ((p^i)*) (1:r) | i<-[0..k]]) [] 

-------------------------------------------------------------------------------------
divis = (1:).foldr (\(p,k) r-> merge r $ 
               foldr (\(x:xs) ys -> x:merge xs ys)
                  [] [m : map (m*) r | m <- take k $ iterate (p*) p]) []
-------------------------------------------------------------------------------------
divis = (1:).foldr (\(p,k) r-> merge r $ 
               foldr merge [] [map (m*) (1:r) | m <- take k $ iterate (p*) p]) []
-------------------------------------------------------------------------------------
divis = (1:).foldr (\(p,k) r-> 
               foldr merge [] $ r:[map (m*) (1:r) | m <- take k $ iterate (p*) p]) []
-------------------------------------------------------------------------------------
divis = (1:).foldr (\(p,k) r->  
               foldr merge r [map (m*) (1:r) | m <- take k $ iterate (p*) p]) []
-------------------------------------------------------------------------------------

-- tied hamming numbers
hamm = 1:foldl (\s n->fix (merge s.(n:).map (n*))) [] [5,3,2]     -- 100k: 0.07s (interp) 

-- regular version
h = 1 : foldi g [] [map (p*) h | p <- [2,3,5]]                    -- 100k: 0.13s 
    where g (x:xs) ys = x : union xs ys        

-- untied hamming numbers
uhamm = foldr (\p r-> merge r $
          foldr (\(x:xs) ys -> x:merge xs ys)
            [] [m : map (m*) r | m <- iterate (p*) p]) [] [5,3,2] --  100k:0.23s(interp); [2,3,5]->0.40s
--
uhamm = foldr (\p r-> merge r $ foldr (\(x:xs) ys-> x:merge xs ys) [] [m:map (m*) r | m <- iterate (p*) p]) [] [2,3,5]



-- kinda-paramorphism ( kata on tails ):
divis = (1:) . foldr (\((p,k):z) r-> 
                 case z of [] -> take k $ iterate (p*) p    -- the biggest factor
                          ; _ -> merge r $ 
                   foldr (\(x:xs) ys -> x:merge xs ys)      -- would foldi/foldt be faster here??
                     [] [m : map (m*) r | m <- take k $ iterate (p*) p]) [] . tails


---
http://stackoverflow.com/questions/12480291/new-state-of-the-art-in-unlimited-generation-of-hamming-sequence/12482897#12482897
---

So basically, now that Daniel Fischer gave his answer, I can say that I came across this recently, and I think this is an exciting development, since the classical code was known for ages, since Dijkstra.

Daniel correctly identified the redundancy of the duplicates generation which must then be removed, in the classical version.

**[The credit for the original discovery (AFAIK) goes to Rosettacode.org's contributor Ledrug](http://rosettacode.org/mw/index.php?title=Hamming_numbers&diff=143055&oldid=142784)**, as of 2012-08-26. And of course **[the independent discovery by Daniel Fischer, here](http://stackoverflow.com/a/12482407/849891)** (2012-09-18).

Re-written slightly, that code is:

    import Data.Function (fix)

    hamm = 1:foldl (\s n->fix (merge s.(n:).map (n*))) [] [5,3,2]

with the usual implementation of merge,

    merge a@(x:xs) b@(y:ys) | x < y     = x:merge xs b
                            | otherwise = y:merge a ys
    merge [] b = b
    merge a [] = a

It gives about 2.0x - 2.5x a speedup, and slight improvement in the empirical orders of growth, vs. the classical version.