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

Recursively defined, Haskell-style infinite lists (Python recipe) by John Crichton
ActiveState Code (http://code.activestate.com/recipes/578119/)

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" [*].

[*] http://code.activestate.com/recipes/576961-technique-for-cyclical-iteration/

Python, 59 lines
Download
 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
Tags: decorator, functional, generator, infinite, itertools, lazy, recursive

1 comment

Paddy McCarthy 11 years, 6 months ago  # | flag

Thanks for this. I just referenced it from an old blog in the comments for completeness.