sieve is not guaranteed always to be productive, and could become stuck e.g. if called with [5,10..] as the initial stream. Here is another example in Haskell. The following definition produces the list of Fibonacci numbers in linear time: fibs = 0 : 1 : zipWith (+) fibs (tail fibs) This infinite list depends on lazy evaluation; elements are computed on an as-needed basis, and only finite prefixes are ever explicitly represented in memory. This feature allows algorithms on parts of codata to terminate; such techniques are an important part of Haskell programming. This can be done in Python as well: from itertools import tee, chain, islice, imap def add(x, y): return x + y def fibonacci(): def deferred_output(): for i in output: yield i result, c1, c2 = tee(deferred_output(), 3) paired = imap(add, c1, islice(c2, 1, None)) output = chain([0, 1], paired) return result for i in islice(fibonacci(), 20): print(i) The definition of zipWith can be inlined, leading to this: fibs = 0 : 1 : next fibs where next (a: t@(b:_)) = (a+b):next t This example employs a self-referential data structure. Ordinary recursion makes use of self-referential functions, but does not accommodate self-referential data. However, this is not essential to the Fibonacci example. It can be rewritten as follows: fibs = fibgen (0,1) fibgen (x,y) = x : fibgen (y,x+y) This employs only self-referential function to construct the result. If it were used with strict list constructor it would be an example of runaway recursion, but with non-strict list constructor this guarded recursion gradually produces an indefinitely defined list. Corecursion need not produce an infinite object; a corecursive queue is a particularly good example of this phenomenon. The following definition produces a breadth-first traversal of a binary tree in linear time: data Tree a b = Leaf a | Branch b (Tree a b) (Tree a b) bftrav :: Tree a b -> [Tree a b] bftrav tree = queue where queue = tree : gen 1 queue gen 0 p = [] gen len (Leaf _ : s) = gen (len-1) s gen len (Branch _ l r : s) = l : r : gen (len+1) s This definition takes an initial tree and produces a list of subtrees. This list serves dual purpose as both the queue and the result (gen len p produces its output len notches after its input back-pointer, p, along the