Pythonic Infinite Lists

[Glenton]

Hi All

I came across a Perl implementation of Infinite Lists the other day, and was wondering about implementing it in python.

The specific example was to generate the first 3000 Hamming numbers, that is numbers of the form 2**i*3**j*5**k for i,j,k>=0.

I implemented something similar to their approach as follows:

from time import time
startTime=time()

def getHeads(Hamming,prods,inds):
    "Returns heads of three streams"
    heads=[]
    for p,i in zip(prods,inds):
        heads.append(p*Hamming[i])
    return heads
    
def merge(heads,inds):
    "returns value to be added to hamming, and next set of inds"
    val=min(heads)
    for i in range(len(heads)):
        if heads[i]==val:
            inds[i]+=1
    return val,inds

Hamming=[1]

prods=[2,3,5]
inds=[0,0,0]
for k in range(1,3000):
    heads=getHeads(Hamming,prods,inds)
    val,inds=merge(heads,inds)
    Hamming.append(val)

print 3000,Hamming[3000-1]
print "time: ",time()-startTime

This works rather well, generating the 3000 hamming numbers in about 14ms. But I was wondering about a more general setup to solve this problem generally. Like a class structure for these streams.

I started with this:

class Stream(object):
    """Stream objects have a head (which is the front element), a
    tail (which can be another stream, or a function(n,head)"""
    def __init__(self,head,tail,n=0,tailIsStream=False):
        self.n=0
        self.tailStream=tailIsStream
        self.head=head
        self.tail=tail
        self.values=[head]
        
    def call(self):
        ans=self.head
        self.n+=1
        if self.tailStream:
            self.head=self.tail.call()
        else:
            self.head=self.tail(self.n,self.head)
        self.values.append(self.head)
        return ans
    
    def __mul__(self,other):
        return Stream(self.head*other,lambda n,head: head*other)
    
    
    
s=Stream(1,lambda n,head:n**2)
for i in range(10):
    print i, s.call()

which sort of works, but it's not obvious (at least to me) how to approach the coding of the hamming problem in this framework. And I wondered if there was a neater way anyway.

Thoughts?