blogSome lazy data structures implemented in Eiffel - Part I - Iterating the Calkin-Wilf tree

colin-adams's picture

This is the first part of a series in which I intend to make some explorations of lazy, infinite data structures in Eiffel. If you want to compile the code in these articles, you will need EiffelStudio 15.11 or later.

In this first article, I am going to iterate an infinite data structure - the strictly-positive rational numbers, represented by an infinite tree - The Calkin-Wilf tree. The easiest way to follow the code is to view it directly on GitHub. An alternative is to checkout the repository and compile it in EiffelStudio. To do the latter (instructions are for Linux from a bash terminal, but should be similar for other O/S I think):

  1. git clone git@github.com:colin-adams/lazy_eiffel.git
  2. git checkout V1
  3. cd lazy_eiffel/examples/calkin_wilf/src
  4. estudio calkin_wilf.ecf &
  5. Press OK

The first class worth looking at briefly is  . This represents a single node in an infinite binary tree, together with a link to it's parent, and two  s to find the left and right children. Incidentally, you may be surprised at the syntax used for declaring these  s unless you have already read this thread. This is why 15.11 or later is needed to compile the code. I think it's worth showing one of those agents here:

 

This syntax is starting to look lightweight. Looking quite comparable to Haskell, for example ( ), and none of that horrible camelCase.

Then let's look at the   tree itself. The core of the class is a root node, two functions to navigate from any node in the tree to the left and right children (or to lazily build the tree structure, depending on how you want to look at it), and a creation procedure to initialize root to 1/1.

 

However, I muddled this nice little picture by inheriting from  . So the class   has a lazy tree of rationals, and is a linear iteration of them. In the root class   we simply print the first 100 rational numbers (I could have made the program take an argument) using a  . However, the iteration is not in numerical order. In a future post we'll see other ways of iterating the rationals.

The really interesting thing (to me) about the Calkin-Wilf tree is the way I did a breadth-first traversal of this infinite tree. It turns out that the index in the linear structure, when translated into binary, can be considered as a set of instructions to move through the tree. You ignore all leading zeros. At the first one, move to the root. Then every time you see a zero, you take the left child, and every time you see a one, you take the right child. Lovely!

Syndicate content