C++0x Lazy List

One of my favorite features of Haskell will always be lazy lists. When I first saw it I was blown away, it was the coolest thing I’ve ever seen a programming language do (with exception to prolog’s unification). Ever since I’ve been disappointed with c++ for not being able to do it as elegantly.

Basically, for those who don’t know, a lazy list is an infinite list in which elements are generated on the fly. Although this has been possible in C++ for a long time, with C++0x it really becomes beautiful.

For example, to represent the Fibonacci Numbers we can do:

LazyList<int> fibonacci([](unsigned int index, LazyList<int> *obj) -> int
{
	if(index < 2) return index;
	return (*obj)[index-1] + (*obj)[index-2];
});
 
/* Print the first 20 fibonacci numbers */
for(int i = 0; i < 20; i++)
	printf("%d ", fibonacci[i]);

And the code for class LinkedList (Note: I have not implemented a cache, to show how simple it is):

#include <functional>
template<typename T>
class LazyList 
{
public:
	typedef std::function<T(unsigned int, LazyList<T>*)> Generator;
 
	LazyList(Generator gen)
		: m_gen(gen)
	{
	}
 
	T operator [](unsigned int n) 
	{
		return m_gen(n, this);
	}
private:
	Generator m_gen;
};

Awesome.

Apr 03, 2010 | Categories: Programming | Tags: C++0x | Leave A Comment »