Home

Enumerating the Rationals

Jeremy Gibbons, David Lester and Richard Bird (2004). Enumerating the Rationals. May 2004.

In this paper,we explain an elegant technique for enumerating the positive rationals without duplicates. Moreover, we show how to do so as a simple iteration, generating each element of the enumeration from the previous one alone,with constant cost per element (assuming unit cost for simple operations on arbitrary-precision rationals). Best of all, the resulting program is extremely simple...

Cute. Nothing earth shattering, but fun none the less.

By Ehud Lamm at 2004-06-29 08:09 | Functional | other blogs | 11773 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

"Proofs from the Book"

The book that they say inspired this paper sounds very nice. I thought about this sort of book many times. Has anyone here read it?

By Ehud Lamm at Tue, 2004-06-29 22:45 | login or register to post comments

Re: "Proofs from the Book"

I have this one. I haven't read it cover to cover; it's more of a "grazing" book.

I would say that it is "math geek light reading". ;-)

It is definitely a tribute to the beauty and excitement of simple, elegant proofs.

By Marc Hamann at Tue, 2004-06-29 23:41 | login or register to post comments

Proofs Missing From the Book

Damn! Unfortunately the section that inpired this paper is new to the third edition. (I have the second edition)

I've been robbed! ;-)

By Marc Hamann at Wed, 2004-06-30 00:03 | login or register to post comments

Fourth Edition

Apparently, the fourth edition was recently released...

By Leon P Smith at Tue, 2010-01-19 07:04 | login or register to post comments

Python?

And now there's a Python version.

By Ehud Lamm at Sun, 2004-07-04 21:40 | login or register to post comments

Fun paper.

Heh, I just discovered this paper, and was just about to post it. But funnily enough, it's already here! :-)

Personally, I think the Stern-Brocot tree should be the "default" example of an infinite tree in the functional programming community. The Calkin-Wilf tree is new to me.

By Leon P Smith at Tue, 2010-01-19 02:22 | login or register to post comments