Classical FP problem in python : Hamming problem

[Francis Girard]

Hi,

First,

My deepest thanks to Craig Ringer, Alex Martelli, Nick Coghlan and Terry Reedy 
for having generously answered on the "Need help on need help on generator" 
thread. I'm compiling the answers to sketch myself a global pictures about 
iterators, generators, iterator-generators and laziness in python.

In the meantime, I couldn't resist to test the new Python features about 
laziness on a classical FP problem, i.e. the "Hamming" problem.

The name of the game is to produce the sequence of integers satisfying the 
following rules :

(i) The list is in ascending order, without duplicates
(ii) The list begins with the number 1
(iii) If the list contains the number x, then it also contains the numbers 
2*x, 3*x, and 5*x
(iv) The list contains no other numbers.

The algorithm in FP is quite elegant. Simply suppose that the infinite 
sequence is produced, then simply merge the three sequences (2*x,3*x,5*x) for 
each x in the infinite sequence we supposed as already produced ; this is 
O(n) complexity for n numbers.

I simply love those algorithms that run after their tails.

In haskell, the algorithm is translated as such :

-- BEGIN SNAP
-- hamming.hs

-- Merges two infinite lists
merge :: (Ord a) => [a] -> [a] -> [a]
merge (x:xs)(y:ys)
  | x == y    = x : merge xs ys
  | x <  y    = x : merge xs (y:ys)
  | otherwise = y : merge (x:xs) ys

-- Lazily produce the hamming sequence
hamming :: [Integer]
hamming 
  = 1 : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming))
-- END SNAP


In Python, I figured out this implementation :

-- BEGIN SNAP
import sys
from itertools import imap

## Merges two infinite lists
def imerge(xs, ys):
  x = xs.next()
  y = ys.next()
  while True:
    if x == y:
      yield x
      x = xs.next()
      y = ys.next()
    elif x < y:
      yield x
      x = xs.next()
    else: # if y < x:
      yield y
      y = ys.next()

## Lazily produce the hamming sequence 
def hamming():
  yield 1 ## Initialize the machine
  for n in imerge(imap(lambda h: 2*h, hamming()),
                  imerge(imap(lambda h: 3*h, hamming()),
                         imap(lambda h: 5*h, hamming()))):
    yield n
  print "Falling out -- We should never get here !!"
    
for n in hamming():
  sys.stderr.write("%s " % str(n)) ## stderr for unbuffered output
-- END SNAP


My goal is not to compare Haskell with Python on a classical FP problem, which 
would be genuine stupidity.

Nevertheless, while the Haskell version prints Hamming sequence for as long as 
I can stand it, and with very little memory consumation, the Python version 
only prints :

>>>>>> hamming.py
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 
80 81 90 96 100 108 120 125 128 135 144 150 160 162 180 192 200 216 225 240 
243 250 256 270 288 300 320 324 360 375 384 400 405 432 450 480 486 500 512 
540 576 600 625 640 648 675 720 729 750 768 800 810 864 900 960 972 1000 1024 
1080 1125 1152 1200 1215 1250 1280 1296 1350 1440 1458 1500 1536 1600 1620 
1728 1800 1875 1920 1944 2000 2025 2048 2160 2187 2250 2304 2400 2430 2500 
2560 2592 2700 2880 2916 3000 3072 3125 3200 3240 3375 3456 3600 3645 3750 
3840 3888 4000 4050 4096 4320 4374 4500 4608 4800 4860 5000 5120 5184 5400 
5625 5760 5832 6000 6075 6144 6250 6400 6480 6561 6750 6912 7200 7290 7500 
7680 7776 8000 8100 8192 8640 8748 9000 9216 9375 9600 9720 10000 10125 10240 
10368 10800 10935 11250 11520 11664 12000 12150 12288 12500 12800 12960 13122 
13500 13824 14400 14580 15000 15360 15552 15625 16000 16200 16384 16875 17280 
17496 18000 18225 18432 18750 19200 19440 19683 20000 20250 20480 20736 21600 
21870 22500 23040 23328 24000 24300 24576 25000 25600 25920 26244 27000 27648 
28125 28800 29160 30000 30375 30720 31104 31250 32000 32400 32768 32805 33750 
34560 34992 36000 36450 36864 37500 38400 38880 39366 40000 40500 40960 41472 
43200 43740 45000 46080 46656 46875 48000 48600 49152 50000 50625 51200 51840 
52488 54000 54675 55296 56250 57600
Processus arrêté

After 57600, my machine begins swapping like crazy and I do have to kill the 
python processus. 

I think I should not have this kind of behaviour, even using recursion, since 
I'm only using lazy constructs all the time. At least, I would expect the 
program to produce much more results before surrending.

What's going on ?

Thank you

Francis Girard
FRANCE