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):
- git clone git@github.com:colin-adams/lazy_eiffel.git
- git checkout V1
- cd lazy_eiffel/examples/calkin_wilf/src
- estudio calkin_wilf.ecf &
- Press OK
The first class worth looking at briefly is LAZY_BINARY_TREE. This represents a single node in an infinite binary tree, together with a link to it's parent, and two FUNCTIONs to find the left and right children. Incidentally, you may be surprised at the syntax used for declaring these FUNCTIONs 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:
left_child_function: FUNCTION [LAZY_BINARY_TREE [G], LAZY_BINARY_TREE [G]]
This syntax is starting to look lightweight. Looking quite comparable to Haskell, for example (leftChildFunction :: LazyBinaryTree a -> LazyBinaryTree a), and none of that horrible camelCase.
Then let's look at the CALKIN_WILF 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.
feature {NONE} -- Initialization
make
-- Create `root'.
do
left_child_agent := agent left_child
right_child_agent := agent right_child
create root.make ((create {RATIONAL_NUMBER}.make (1, 1)), Void, left_child_agent, right_child_agent)
start
end
feature -- Access
root: LAZY_BINARY_TREE [RATIONAL_NUMBER]
-- 1/1
left_child_agent: FUNCTION [LAZY_BINARY_TREE [RATIONAL_NUMBER], LAZY_BINARY_TREE [RATIONAL_NUMBER]]
-- Function from a node to its left child
right_child_agent: FUNCTION [LAZY_BINARY_TREE [RATIONAL_NUMBER], LAZY_BINARY_TREE [RATIONAL_NUMBER]]
-- Function from a node to its left child
left_child (a_node: LAZY_BINARY_TREE [RATIONAL_NUMBER]): LAZY_BINARY_TREE [RATIONAL_NUMBER]
-- Left child of `a_node'
do
create Result.make (create {RATIONAL_NUMBER}.make (
a_node.item.numerator, a_node.item.numerator + a_node.item.denominator),
a_node, left_child_agent, right_child_agent)
end
right_child (a_node: LAZY_BINARY_TREE [RATIONAL_NUMBER]): LAZY_BINARY_TREE [RATIONAL_NUMBER]
-- Right child of `a_node'
do
create Result.make (create {RATIONAL_NUMBER}.make (
a_node.item.numerator + a_node.item.denominator, a_node.item.denominator),
a_node, left_child_agent, right_child_agent)
end
However, I muddled this nice little picture by inheriting from LINEAR [LAZY_BINARY_TREE [RATIONAL_NUMBER]]. So the class CALKIN_WILF has a lazy tree of rationals, and is a linear iteration of them. In the root class CALKIN_WILF_DEMO_ROOT we simply print the first 100 rational numbers (I could have made the program take an argument) using a LINEAR_ITERATOR [LAZY_BINARY_TREE [RATIONAL_NUMBER]]. 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!
