Welcome, guest | Sign In | My Account | Store | Cart

A decorator to simplify the creation of recursively defined, Haskell-style infinite lists -- ie. recursive generators -- inspired by Raymond Hettinger's "Technique for cyclical iteration" [*].

Python, 59 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59``` ```from itertools import imap, chain, count, islice, groupby, tee from operator import add, mul from heapq import merge class clone(object): '''A decorator to simplify the creation of recursively defined generators.''' def __init__(self, generator): self.clones = iter(tee(generator())) self.cache = None def __call__(self): try: self.cache = next(self.clones) return next(self.clones) except StopIteration: self.clones = iter(tee(self.cache)) return next(self.clones) # examples # # helper function def itail(iterable): return islice(iterable, 1, None) # Haskell -- fibonacci # fibs = 0 : 1 : zipWith (+) fibs (tail fibs) @clone def fibs(): for i in chain([0, 1], imap(add, fibs(), itail(fibs()))): yield i # Haskell -- factorial # facs = 1 : zipWith (*) [1 ..] facs @clone def facs(): for i in chain([1], imap(mul, count(1), facs())): yield i # Haskell -- http://rosettacode.org/wiki/Hamming_numbers # # hamming = 1 : map (2*) hamming `union` map (3*) hamming `union` map (5*) hamming # # union a@(x:xs) b@(y:ys) = case compare x y of # LT -> x : union xs b # EQ -> x : union xs ys # GT -> y : union a ys # hamming numbers generator adapted from Raymond Hettinger's algorithm # http://code.activestate.com/recipes/576961-technique-for-cyclical-iteration/ @clone def hamming(): for i in (k for k, v in groupby(chain([1], merge((2*x for x in hamming()), (3*x for x in hamming()), (5*x for x in hamming()))))): yield i ```

#### 1 comment

Paddy McCarthy 11 years, 6 months ago