Fork me on GitHub

Sunday, October 25, 2009

Infinite lists in python

My first post from Uganda :)

As I am working in Django now I think I will post more on python. I had worked on python before but that was long time back and mostly on system admin stuff. So working on python now for developing web based applications and getting to understand things like object orientation, functional programming, TDD, Ruby and more I think it has changed my way of working with python a lot.

This post is mostly about creating infinite lists in python. Infinite lists are an example of lazy evaluation mostly rooted in functional programming. The idea is we don't construct elements of list but what we do is give a way to construct the next element of the list and let it construct the list when we need (we still need to stop construction of elements depending on some condition). Infinite lists are also rightly called streams. In python, it is easy to use develop infinite lists using generator as shown in the examples below.

Examples of infinite list in python

Increment Example -



Fibonacci Example -

6 comments:

Chris McMahon said...

idle question: can one handle a list of strings in some sort of similar fashion? (I don't know very much about Python)

Pekka Klärck said...

Chris, you can use Python iterators and generators with any data type. Do you have an example on what you'd like to accomplish?

Anyone interested about this kind of stuff should take a look at itertools module to avoid reimplementing too many wheels:
http://docs.python.org/library/itertools.html

Sai Venkatakrishnan said...

yeah.. itertool is more mature and so it will be advisable to use that. But it is good to know what is happening behind the scenes.

Chris are you trying to generate infinite list of test data using this? :)

Chris McMahon said...

For example, in Ruby one can do String#succ and generate all sorts of odd stuff that way.

Sai Venkatakrishnan said...

I will try this out in python.. Interesting problem. Thanks Chris :)

Pekka Klärck said...

I'd create a separate function and use it with itertools methods or custom generators. The example below illustrates this idea, but the simple succ method doesn't have all the same capabilities as Ruby's String#succ.

>>> from itertools import imap
>>> def succ(s):
... return s + chr(ord(s[-1])+1)
...
>>> for i in imap(succ, ['abc','123']):
... print i
...
abcd
1234